General routing problems deal with transporting some commodities and/or travelling along the axes of a given network in some optimal manner. In the modern world such problems arise in several contexts such as distribution of goods, transportation of commodities and/or people etc.In this thesis we focus on two classical routing problems, namely the Travelling Salesman Problem (TSP) and the Vehicle Routing Problem (VRP). The TSP can be described as a salesman travels from his home city, visits each of the other ( n - 1) cities exactly once and returns back to the home city such that the total distance travelled by him is minimised. The VRP may be stated as follows: A set of n customers (with known locations and demands for some commodity) is to be supplied from a single depot using a set of delivery vehicles each with a prescribed capacity. A delivery route starts from the depot, visits some customers and returns back to the depot. The VRP is to determine the delivery routes for each vehicle such that the total distance travelled by all the vehicles is minimised.These routing problems are simple to state in terms of describing them in words. But they are very complex in terms of providing a suitable mathematical formulation and a valid procedure to solve them. These routing problems are simple to state in terms of describing them in words. But they are very complex in terms of providing a suitable mathematical formulation and a valid procedure to solve them. These problems belong to the class of NP-hard (Non- deterministic Polynomial) problems. With the present knowledge, it is believed that the problems in NP-hard are unlikely to have any good algorithms to arrive at optimal solutions to a general problem. Hence researchers have focused their effort on; (i) developing exact algorithms to solve as large size problems as possible; (ii) developing heuristics to produce ++ / near optimal solutions.The exact algorithms for such problems have not performed satisfactorily as they need an enormous amount of computational time to solve moderate size problems. For instance, in the literature, TSP of size 225-city, 4461-city and 7397-city were solved using computational time of 1 year, 1.9 years and 4 years respectively (Junger et al., 1995). Thus heuristics, in particular the probabilistic methods such as tabu search, play a significant role in obtaining near optimal solutions. In the literature there is very little comparison between the various exact algorithms and heuristics. (Very often the real-life problems are too large and no optimal solution can be found in a reasonable time.)One of the problems with a probabilistic heuristic is that different implementations (runs) of the same probabilistic heuristic on a given problem may produce distinct solutions of different quality. Thus the desired quality and reproducibility of the solution cannot be ensured. Furthermore, the performance of the heuristics on the benchmark problems provide no Guarantee of the quality of solutions that can be obtained for the problem faced by a researcher. Most of the documentation on the performance of heuristics in literature problems provides no information regarding the computational effort (CPU time) spent in obtaining the claimed solution, reproducibility of the claimed solution and the hardware environment of the implementation. This thesis focuses on some of these deficiencies.Most of the heuristics for general combinatorial optimisation problems are based on neighbourhood search methods. This thesis explores and provides a formal setup for defining neighbourhood structures, definitions of local optimum and global optimum. Furthermore it highlights the dependence and drawbacks of such methods on the neighbourhood structure.It is necessary to emphasise ++ / the need for a statistical analysis of the output to be part of any such probabilistic heuristic. Some of the statistical tools used for the two probabilistic heuristics for TSP and VRP are developed. Furthermore, these heuristics axe part of a bigger class called tabu search heuristics for combinatorial optimisation problems. Hence it includes an overview of the TSP, VRP and tabu search methods in Chapters 2, 3 and 4 respectively. Subsequently in Chapters 5, 6, 7 and 8 ideas of neighbourhood structure, local optimum etc. are developed and the required statistical analysis for some heuristics on the TSP and VRP is demonstrated. In Chapter 9, the conclusion of this thesis is drawn and the direction of future work is outlined. The following is a brief outline of the contribution of this thesis.In Chapter 5, the ideas of neighbourhood structure, local optimum, global optimum and probabilistic heuristics for any combinatorial optimisation problem sare developed. The drawbacks of the probabilistic heuristics for such problems axe highlighted. Furthermore, the need to select the best heuristic on the basis of testing a statistical hypothesis and related statistical analysis is emphasised.Chapter 6 illustrates some of the ideas presented in Chapter 5 using the GENIUS algorithm proposed for the TSP. Statistical analysis is performed for 36 variations of GENIUS algorithm based on different neighbourhood parameters, different types of insertion methods used and two types of constructions of starting solutions. The analysis is performed on 27 literature problems with size ranging from 100 cities to 532 cities and 20 randomly generated problems with size ranging from 100 cities to 480 cities. In both cases the best heuristic is selected. Furthermore, the fitting of the Weibull Distribution to the objective function values of the heuristic solutions provides an estimate of the ++ / optimal objective function value and a corresponding confidence interval for both the literature and randomly generated problems. In both cases the estimate of the optimal objective function values are within 8.2% of the best objective function value known.Since the GENIUS algorithm proved to be efficient, a hybrid heuristic for the TSP combining the branch and bound method and GENIUS algorithm to solve large dimensional problems is proposed. The algorithm is tested on both the literature problems with sizes ranging from 575 cities to 724 cities and randomly generated problems with sizes ranging from 500 cities to 700 cities. Though problems could not be solved to optimality within the 10 hours time limit, solutions were found within 2.4% of the best known objective function value in the literature.In Chapter 7, a similar statistical analysis for the TABUROUTE algorithm proposed for the VRP is conducted. The analysis is carried out based on the different neighbourhood parameters and tested using 14 literature problems with sizes ranging from 50 cities to 199 cities and 49 randomly generated problems with sizes ranging from 60 cities to 120 cities. In both sets of the problems, the statistical tests accepted the hypothesis that there is no significant difference in the solution produced between the various parameters used for the TABUROUTE algorithm. By fitting the Weibull distribution to the objective function values of the local optimal solutions, the optimal objective function value and a corresponding confidence intervals for each problem is estimated. These estimates give values that are to within 6.1% and 18.3% of the best known values for the literature problems and randomly generated problems respectively.In Chapter 8, the general neighbourhood search method for a general combinatorial optimisation problem is presented. Very often, the neighbourhood structure ++ / can be defined suitably only on a superset S of the set of feasible solutions S. Thus the solutions in SS are infeasible. Several questions axe posed regarding the computational complexity of the solution space of a problem. These concepts are illustrated on the 199-city CDVRP, using the TABUROUTE algorithm.In addition, the idea of complexity of the solution space based on the samples collected over the 140 runs is explored. Some of the data collected include the number of solutions with distance and/or capacity feasible, the number of feasible neighbourhood solutions encountered for one run, etc. Questions such asHow many solutions are there for the 199-city problem ?How many numbers of local minima solutions are there for the 199-city problem?What is the size of the feasible region for the 199-city problem?are answered. Finally, the conclusion is drawn that this problem cannot be used as a benchmark based on the size of the feasible region and too many local minima.The conclusion of this thesis and directions of future work are discussed in Chapter 9. There are two appendices presented at the end of the thesis. Appendix A presents the details of the Friedman test, the expected utility function test and the estimation of the optimal objective function value based on the Weibull distribution. Appendix B presents a list of tables from Chapters 6, 7 and 8.

Thesis--Auburn University, 2010. / Abstract. Includes bibliographic references (p.28).

Access to abstract restricted until 05/2015. / Asscess to thesis restricted until 05/2015. / Department of Computer Science

Thesis (Ph.D)--Aerospace Engineering, Georgia Institute of Technology, 2010. / Committee Chair: Braun, Robert; Committee Member: Clarke, John-Paul; Committee Member: Russell, Ryan; Committee Member: Sims, Jon; Committee Member: Tsiotras, Panagiotis. Part of the SMARTech Electronic Thesis and Dissertation Collection.

Thesis (M. S.)--Aerospace Engineering, Georgia Institute of Technology, 2010. / Committee Chair: John-Paul Clarke; Committee Member: Ellis Johnson; Committee Member: Eric Feron. Part of the SMARTech Electronic Thesis and Dissertation Collection.

Understanding and characterizing the processes driving social interactions is one of the fundamental problems in social network research. A particular instance of this problem, known as link prediction, has recently attracted considerable attention in various research communities. Link prediction has many important commercial applications, e.g., recommending friends in an online social network such as Facebook and suggesting interesting pins in a collection sharing network such as Pinterest. This work is focused on the temporal link prediction problem: Given a sequence of graph snapshots G1, · ··, Gt from time 1 to t, how do we predict links in future time t + 1? To perform link prediction in a network, one needs to construct models for link probabilities between pairs of nodes. A temporal latent space model is proposed that is built upon latent homophily assumption and temporal smoothness assumption. First, the proposed modeling allows to naturally incorporate the well-known homophily effect (birds of a feather flock together). Namely, each dimension of the latent space characterizes an unobservable homogeneous attribute, and shared attributes tend to create a link in a network.

University of Macau / Faculty of Science and Technology / Department of Computer and Information Science

Agent-based models are computer simulations in which entities (agents) interact with each other and their environment according to local update rules. Local interactions give rise to global dynamics. These models can be thought of as in silico laboratories that can be used to investigate the system being modeled. Optimization problems for agent-based models are problems concerning the optimal way of steering a particular model to a desired state. Given that agent-based models have no rigorous mathematical formulation, standard analysis is difficult, and traditional mathematical approaches are often intractable. This work presents techniques for the analysis of agent-based models and for solving optimization problems with such models. Techniques include model reduction, simulation optimization, conversion to systems of discrete difference equations, and a variety of heuristic methods. The proposed strategies are novel in their application; results show that for a large class of models, these strategies are more effective than existing methods. / Ph. D.

Continuous optimization problems are optimization problems where all variables<p>have a domain that typically is a subset of the real numbers; mixed discrete-continuous<p>optimization problems have additionally other types of variables, so<p>that some variables are continuous and others are on an ordinal or categorical<p>scale. Continuous and mixed discrete-continuous problems have a wide range<p>of applications in disciplines such as computer science, mechanical or electrical<p>engineering, economics and bioinformatics. These problems are also often hard to<p>solve due to their inherent difficulties such as a large number of variables, many<p>local optima or other factors making problems hard. Therefore, in this thesis our<p>focus is on the design, engineering and configuration of high-performing heuristic<p>optimization algorithms.<p>We tackle continuous and mixed discrete-continuous optimization problems<p>with two classes of population-based heuristic algorithms, ant colony optimization<p>(ACO) algorithms and evolution strategies. In a nutshell, the main contributions<p>of this thesis are that (i) we advance the design and engineering of ACO algorithms to algorithms that are competitive or superior to recent state-of-the-art<p>algorithms for continuous and mixed discrete-continuous optimization problems,<p>(ii) we improve upon a specific state-of-the-art evolution strategy, the covariance<p>matrix adaptation evolution strategy (CMA-ES), and (iii) we extend CMA-ES to<p>tackle mixed discrete-continuous optimization problems.<p>More in detail, we propose a unified ant colony optimization (ACO) framework<p>for continuous optimization (UACOR). This framework synthesizes algorithmic<p>components of two ACO algorithms that have been proposed in the literature<p>and an incremental ACO algorithm with local search for continuous optimization,<p>which we have proposed during my doctoral research. The design of UACOR<p>allows the usage of automatic algorithm configuration techniques to automatically<p>derive new, high-performing ACO algorithms for continuous optimization. We also<p>propose iCMAES-ILS, a hybrid algorithm that loosely couples IPOP-CMA-ES, a<p>CMA-ES variant that uses a restart schema coupled with an increasing population<p>size, and a new iterated local search (ILS) algorithm for continuous optimization.<p>The hybrid algorithm consists of an initial competition phase, in which IPOP-CMA-ES and the ILS algorithm compete for further deployment during a second<p>phase. A cooperative aspect of the hybrid algorithm is implemented in the form<p>of some limited information exchange from IPOP-CMA-ES to the ILS algorithm<p>during the initial phase. Experimental studies on recent benchmark functions<p>suites show that UACOR and iCMAES-ILS are competitive or superior to other<p>state-of-the-art algorithms.<p>To tackle mixed discrete-continuous optimization problems, we extend ACOMV <p>and propose CESMV, an ant colony optimization algorithm and a covariance matrix adaptation evolution strategy, respectively. In ACOMV and CESMV ,the decision variables of an optimization problem can be declared as continuous, ordinal, or categorical, which allows the algorithm to treat them adequately. ACOMV and<p>CESMV include three solution generation mechanisms: a continuous optimization<p>mechanism, a continuous relaxation mechanism for ordinal variables, and a categorical optimization mechanism for categorical variables. Together, these mechanisms allow ACOMV and CESMV to tackle mixed variable optimization problems.<p>We also propose a set of artificial, mixed-variable benchmark functions, which can<p>simulate discrete variables as ordered or categorical. We use them to automatically tune ACOMV and CESMV's parameters and benchmark their performance.<p>Finally we test ACOMV and CESMV on various real-world continuous and mixed-variable engineering optimization problems. Comparisons with results from the<p>literature demonstrate the effectiveness and robustness of ACOMV and CESMV<p>on mixed-variable optimization problems.<p>Apart from these main contributions, during my doctoral research I have accomplished a number of additional contributions, which concern (i) a note on the<p>bound constraints handling for the CEC'05 benchmark set, (ii) computational results for an automatically tuned IPOP-CMA-ES on the CEC'05 benchmark set and<p>(iii) a study of artificial bee colonies for continuous optimization. These additional<p>contributions are to be found in the appendix to this thesis.<p> / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

Portfolio selection is an example of decision making under conditions of uncertainty. In the face of an unknown future, fund managers make complex financial choices based on the investors perceptions and preferences towards risk and return. Since the seminal work of Markowitz, many studies have been published using his mean-variance (MV) model as a basis. These mathematical models of investor attitudes and asset return dynamics aid in the portfolio selection process. In this thesis we extend the MV model to include the cardinality constraints which limit the number of assets held in the portfolio and bounds on the proportion of an asset held (if any is held). We present our formulation based on the Markowitz MV model for rebalancing an existing portfolio subject to both fixed and variable transaction cost (the fee associated with trading). We determine and demonstrate the differences that arise in the shape of the trading portfolio and efficient frontiers when subject to non-cardinality and cardinality constrained transaction cost models. We apply our flexible heuristic algorithms of genetic algorithm, tabu search and simulated annealing to both the cardinality constrained and transaction cost models to solve problems using data from seven real world market indices. We show that by incorporating optimization into the generation of valid portfolios leads to good quality solutions in acceptable computational time. We illustrate this on problems from literature as well as on our own larger data sets.