Orientador: Antonio Carlos Moretti / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-06T12:59:52Z (GMT). No. of bitstreams: 1 Sousa_VaniaNobrede_M.pdf: 984501 bytes, checksum: f58d5baf5c8e4dc8e704f4cb9aa47c6b (MD5) Previous issue date: 2006 / Mestrado / Matematica Aplicada / Mestre em Matemática Aplicada

The study of Stochastic Local Search (SLS) algorithms is becoming more pivotal these days, due to their vast number of applications in decision making. Prior to the implementation of algorithmic knowledge for decision making, many decisions were made based on manual calculation, on the fly, or even based on guts feeling. Nowadays, such an approach is more rarely seen, especially when the decisions that need to be made are high-risk, cost intensive, or time-consuming. The increasingly often used SLS algorithms are one of the options available to assist the decision making process these days.The work discussed in this thesis concerns the study of SLS algorithms for solving the Quadratic Assignment Problem (QAP), a prominent combinatorial optimization problem, which until today is very hard to solve. Our interest is to study the behavior and performance of SLS algorithms for solving QAP instances of different characteristics, such as size, sparsity, and structure. In this study, we have also proposed new variants of SLS algorithms, inspired by existing, well-performing SLS algorithms for solving the QAP. The new variants of SLS algorithms are then further extended for solving the bi-objective QAP (bQAP).One main focus in this study is to see how the performance of algorithms scales with instance size. We have considered instances that are much larger than the ones usually used in the studies of algorithms for solving the QAP. By understanding how the algorithms perform when the instance size changes, we might be able to solve other problems effectively by considering the similarity in their characteristics to the ones of the QAP, or by seeing common trends in the relative performance of the various available SLS methods. For single objective QAP instances we found that the structure and size of instances do have a significant impact on the performance of SLS algorithms. For example, comparisons between Tabu Search (TS) and Simulated Annealing (SA) on instances with randomly generated matrices show that the overall performance of TS is better than SA, irrespective the size of instances considered. The results on a class of structured instances however show that TS performs well on small-sized instances, while on the larger ones, SA shows better results. In another experiment, Hierarchical Iterated Local Search (HILS) has shown very good results compared to several Iterated Local Search (ILS) variants. This experiment was done on a class of structured instances of size from 100 to 500. An extensive experiment on a class of structured instances of size 30 to 300 using tuned parameter settings shows that population based algorithms perform very well on most of the instance classes considered. SA however, shows very good performance especially on large-sized instances with low sparsity level. For the bQAP, the correlation between the flow matrices does have a strong effect that determines the performance of algorithms for solving them. Hybrid Simulated Annealing (HSA) clearly outperforms Hybrid Iterative Improvement (HII). When compared to Multi Objective Ant Colony Optimization (MOACO) and Strength Pareto Evolutionary Algorithm 2 (SPEA2), HSA shows very good performance, where HSA outperforms MOACO and SPEA2, especially on instances of large size, thus, offering a better scaling behavior. Based the results obtained in this study, it is possible to come up with a general idea on the suitability of SLS algorithms for solving instances with a certain characteristic. Given an unknown QAP instance, one can guess the most suitable algorithm for solving it depending on the type, size, and sparsity of the instance, while for a bQAP instance the most suitable algorithm can be guessed based on its size and correlation between the flow matrices. / Doctorat en Sciences de l'ingénieur et technologie / info:eu-repo/semantics/nonPublished

Cette thèse porte sur la conception et l'implémentation d'algorithmes approchés pour l'optimisation en variables discrètes. Plus particulièrement, dans cette étude nous nous intéressons à la résolution de trois problèmes combinatoires difficiles : le « Bin-Packing », la « Réaffectation de machines » et la « Gestion des rames sur les sites ferroviaires ». Le premier est un problème d'optimisation classique et bien connu, tandis que les deux autres, issus du monde industriel, ont été proposés respectivement par Google et par la SNCF. Pour chaque problème, nous proposons une approche heuristique basée sur la recherche locale et nous comparons nos résultats avec les meilleurs résultats connus dans la littérature. En outre, en guise d'introduction aux méthodes de recherche locale mise en œuvre dans cette thèse, deux métaheuristiques, GRASP et Recherche Tabou, sont présentées à travers leur application au problème de la couverture minimale. / This Ph.D. thesis concerns algorithms for Combinatorial Optimization Problems. In Combinatorial Optimization Problems the set of feasible solutions is discrete or can be reduced to a discrete one, and the goal is to find the best possible solution. Specifically, in this research we consider three different problems in the field of Combinatorial Optimization including One-dimensional Bin Packing (and two similar problems), Machine Reassignment Problem and Rolling Stock Problem. The first one is a classical and well known optimization problem, while the other two are real world and very large scale problems arising in industry and have been recently proposed by Google and French Railways (SNCF) respectively. For each problem we propose a local search based heuristic algorithm and we compare our results with the best known results in the literature. Additionally, as an introduction to local search methods, two metaheuristic approaches, GRASP and Tabu Search are explained through a computational study on Set Covering Problem.

No description available.

Constraint-Based Local Search (CBLS) is a technology used to solve computationally hard optimisation problems. A model written in a solver-independent modelling language needs to be processed before it can be solved by a CBLS solver. In this processing step, it is necessary to identify invariants and create an invariant structure. How to best obtain such a structure, or even how to identify a good structure, is not clear. The purpose of this project is to develop a framework for evaluating invariant structures and structure identification schemes. To do this, we introduce a set of metrics, which are also evaluated. The evaluation shows that these metrics are useful for evaluating invariant structures and structure identification schemes. We introduce a notion of optimal invariant structures and show that these can in many cases be produced by simple structure identification schemes. Finally, we present a strategy that improves on these schemes and yields optimal invariant structures in even more cases.

Boolean Satisfiability (SAT) is a problem that holds great theoretical significance along with effective formulations that benefit many real-world applications. While the general problem is NP-complete, advanced solver algorithms and heuristics allow for fast solutions to many large industrial problems. In addition to SAT, many applications rely on generalizations of Satisfiability such as MaxSAT, and Satisfiability Modulo Theories (SMT). Much of the advancement in SAT solver performance has been in the realm of improved sequential solvers with advanced conflict resolution, learning mechanisms, and sophisticated heuristics. There have been some successful demonstrations of massively parallel and hardware-accelerated solvers for SAT, but these have failed to find their way into mainstream usage. This document first presents previous work in Hardware Acceleration of Satisfiability followed by an analysis of why these attempts failed to gain widespread acceptance. It then demonstrates an alternative, hardware-centric approach, based on distributed Stochastic Local Search (SLS) that is better suited to efficient hardware implementation. Then a parallel SLS/CDCL hybrid approach is proposed that is suitable for distributed search with minimal communication overhead while maintaining completeness. Finally the efficacy and flexibility of distributed local search is considered with an adaptation to Weighted Partial MaxSAT (WPMS) and a focused case study on converted Probabilistic Inference instances. / Ph. D. / The Boolean Satisfiability (SAT) problem is an important decision problem that asks whether there exists a solution that satisfies all given constraints over a set of variables that can assume values of either 0 or 1. May real-world decision problems can be translated into SAT, and there exist efficient sequential solvers that can quickly resolve many such instances. Less progress has been made in efficiently scaling SAT solvers to modern multi-core systems and massively parallel hardware accelerators such as GPUs and Field Programmable Gate Arrays (FPGAs). This thesis explore different approaches to solving SAT based decision and optimization problems with the goal of increasing concurrency.

No description available.

No description available.

No description available.

In this dissertation, the vehicle routing problem and one of its variants, the vehicle routing problem with simultaneous pick up and deliveries (VRPSPD) are studied. The traditional vehicle routing problem (VRP) consists of constructing minimum cost routes for the vehicles to follow so that the set of customers are visited only once. A lot of effort has been devoted to research on developing fast and effective solution methods for many different versions of this problem by different majors of engineering profession. Thus, a structuring effort is needed to organize and document the vast literature so far has accumulated in this field. Over its lifespan the VRP literature has become quite disjointed and disparate. Keeping track of its development has become difficult because its subject matter transcends several academic disciplines and professions that range from algorithm design to traffic management. Consequently, this dissertation begins with defining VRP's domain in its entirety, accomplishes an allencompassing taxonomy for the VRP literature, and delineates all of VRP's facets in a parsimonious and discriminating manner. Sample articles chosen for their disparity are classified to illustrate the descriptive power and parsimony of the taxonomy. Next, a more detailed version of the original problem, the VRPSPD is examined and a more abstract taxonomy is proposed. Additionally, two other existing classification methodologies are used to distinguish all published VRPSPD papers on their respective research strategies and solution methods. By using well-organized methods this study provides a solid multidimensional identification of all VRPSPD studies? attributes thus synthesizing knowledge in the filed. Finally, a hybrid metaheuristic solution algorithm for the VRPSPD problem is presented. To solve this NP-hard vehicle routing problem a GRASP initiated hybrid genetic algorithm is developed. The algorithm is tested on two sets of benchmark problems from the literature with respect to computational efficiency and solution quality. The effect of starting with a better initial population for the genetic algorithm is further investigated by comparing the current results with previously generated ones. The experimental results indicate that the proposed algorithm produces relatively good quality solutions and a better initial population yields a reduction in processing cycles.