Rozprawy doktorskie na temat „Stochastic local search”

This thesis focuses on constraints for membership in formal languages under both the systematic search and stochastic local search approaches to constraint programming (CP). Such constraints are very useful in CP for the following three reasons: They provide a powerful tool for user-level extensibility of CP languages. They are very useful for modelling complex work shift regulation constraints, which exist in many shift scheduling problems. In the analysis, testing, and verification of string-manipulating programs, string constraints often arise. We show in this thesis that CP solvers with constraints for membership in formal languages are much more suitable than existing solvers used in tools that have to solve string constraints. In the stochastic local search approach to CP, we make the following two contributions: We introduce a stochastic method of maintaining violations for the regular constraint and extend our method to the automaton constraint with counters. To improve the usage of constraints for which there exists no known constant-time algorithm for neighbour evaluation, we introduce a framework of using solution neighbourhoods, and give an efficient algorithm of constructing a solution neighbourhood for the regular constraint. In the systematic search approach to CP, we make the following two contributions: We show that there may be unwanted consequences when using a propagator that may underestimate a cost of a soft constraint, as the propagator may guide the search to incorrect (non-optimum) solutions to an over-constrained problem. We introduce and compare several propagators that compute correctly the cost of the edit-distance based soft-regular constraint. We show that the context-free grammar constraint is useful and introduce an improved propagator for it.

Graph colouring is a combinatorial optimisation problem consisting in colouring the vertices of a graph such that no vertices connected by an edge receive the same colour. The minimal number of colours for which such a colouring exists is an intrinsic property of the graph and is called chromatic number. Many real life situations, such as the frequency assignment in mobile networks or the scheduling of courses at a university, can be modelled in this way. Colouring planar graphs, such as maps can be easy, and four colours suffice, but real life systems are much more complex. When modelled by graph colouring, they entail general graphs of large size and include more sophisticated constraints than those representable by simple unweighted edges. Stochastic Local Search (SLS) methods are approximate techniques for efficiently solving these complex combinatorial optimisation problems. They typically consist of construction algorithms, iterative improvement algorithms, and meta-components, better known as metaheuristics. The first two are strongly problem dependent and require the exploitation of problem-specific knowledge, while the last are more general concepts to guide the first two components. The instantiation of SLS algorithms arises from the combination of concrete algorithmic components. This task is complex due to the many possible combinations and the need of determining a certain number of parameters. Empirical tests become then necessary to take the correct decisions. The starting point of this work is the definition of the statistical methods that are appropriate for the analysis of SLS algorithms. We argue that the assumptions for the application of parametric tests are often violated and opt for two alternative methods: permutation and rank-based tests. Our work contributes to the development of permutation tests and to their introduction in the analysis of SLS algorithms. In addition, we transfer a graphical representation of results through simultaneous confidence intervals from the parametric to the non-parametric cases. This representation has the advantage of conveying in one single graph both descriptive and inferential statistics. The developed statistical methods serve for the analysis of SLS algorithms on the graph colouring problem and one of its many possible generalisations, the set T-colouring problem. Several SLS algorithms have been proposed in the literature for the graph colouring problem but no ``unbiased'' comparison has been attempted. A similar situation holds for the set T-colouring problem. In both cases, we design new algorithms, re-implement the most prominent methods, and finally compare them in a rigorous experimental analysis. As the final step, we study SLS algorithms for solving a university course timetabling problem. The design of algorithm components stems from the knowledge gained on the graph colouring problems but the assemblage and configuration of these components is carried out with a systematic methodology. The focus in this context was on the selection of one single algorithm to submit to an algorithm competition. The methodology is presented as an engineering process characterised by the interaction of SLS components design and empirical tests. We deem that this methodological approach is appropriate for the application of SLS methods to complex real life problems. The main results are the following: on the graph colouring problem, the simple Tabu Search with one-exchange neighbourhood remains a very competitive approach and the use of a very large scale neighbourhood is not profitable; on the set T-colouring problem, the best overall algorithm is an Adaptive Iterated Greedy also based on Tabu Search with one-exchange neighbourhood which, under certain circumstances, can be further improved by a restricted exact reassignment of colours; the use of an engineering methodology based on sequential testing is particularly suitable for the application of SLS methods, as it led us to devise the algorithm whose solutions for course timetabling ranked the best out of 24 feasible submissions at the International Timetabling Competition held in 2003.

The Boolean Satisfiability Problem (SAT) is a prototypical NP-complete problem, and is central in computer science and artificial intelligence. Given a formula over a set of Boolean variables, the SAT problem tests whether an interpretation that satisfies the formula exists. Stochastic Local Search (SLS) is a simple but effective approach to SAT. In this thesis, we proposed new SLS techniques for SAT solving and developed new SLS algorithms. Using empirical evaluations, we showed that at the time they were designed our algorithms performed better than the existing state-of-the-art solvers. Moreover, our algorithms have been established as the latest state-of-the-art algorithms for several types of instances. The first idea is configuration checking (CC) for SAT. A typical CC technique is to forbid flipping a variable if since the last time it was flipped, none of its neighbouring variables has been flipped. Based on this strategy, we developed several solvers, including Swcca and CCAnr. In particular, CCAnr performed very well on crafted instances, and a hybrid solver CCAnr+glucose won the silver prize of Hard-combinatorial track in SAT Competition 2014. The second idea is the notion of multilevel properties which consider the satisfaction degree of clauses. Using the CC strategy and the second level score, we developed the CCASat solver, which won the 2012 SAT Challenge random track. We also proposed several new scoring functions, which were used to design CScoreSAT and HScoreSAT. These two solvers are particularly efficient in solving random SAT instances with long clauses, and show one to two orders of magnitude improvement than previous solvers. Thirdly, we proposed a linear make function for tie-breaking in the famous algorithm WalkSAT, leading to the WalkSATlm algorithm. Our experiments demonstrate that WalkSATlm improves WalkSAT by orders of magnitudes on random k-SAT instances with k > 3.
Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
Institute for Integrated and Intelligent Systems
Science, Environment, Engineering and Technology
Full Text

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

In this thesis we focus on Stochastic combinatorial Optimization Problems (SCOPs), a wide class of combinatorial optimization problems under uncertainty, where part of the information about the problem data is unknown at the planning stage, but some knowledge about its probability distribution is assumed.

Optimization problems under uncertainty are complex and difficult, and often classical algorithmic approaches based on mathematical and dynamic programming are able to solve only very small problem instances. For this reason, in recent years metaheuristic algorithms such as Ant Colony Optimization, Evolutionary Computation, Simulated Annealing, Tabu Search and others, are emerging as successful alternatives to classical approaches.

In this thesis, metaheuristics that have been applied so far to SCOPs are introduced and the related literature is thoroughly reviewed. In particular, two properties of metaheuristics emerge from the survey: they are a valid alternative to exact classical methods for addressing real-sized SCOPs, and they are flexible, since they can be quite easily adapted to solve different SCOPs formulations, both static and dynamic. On the base of the current literature, we identify the following as the key open issues in solving SCOPs via metaheuristics:

(1) the design and integration of ad hoc, fast and effective objective function approximations inside the optimization algorithm;

(2) the estimation of the objective function by sampling when no closed-form expression for the objective function is available, and the study of methods to reduce the time complexity and noise inherent to this type of estimation;

(3) the characterization of the efficiency of metaheuristic variants with respect to different levels of stochasticity in the problem instances.

We investigate the above issues by focusing in particular on a SCOP belonging to the class of vehicle routing problems: the Probabilistic Traveling Salesman Problem (PTSP). For the PTSP, we consider the Ant Colony Optimization metaheuristic and we design efficient local search algorithms that can enhance its performance. We obtain state-of-the-art algorithms, but we show that they are effective only for instances above a certain level of stochasticity, otherwise it is more convenient to solve the problem as if it were deterministic.

The algorithmic variants based on an estimation of the objective function by sampling obtain worse results, but qualitatively have the same behavior of the algorithms based on the exact objective function, with respect to the level of stochasticity. Moreover, we show that the performance of algorithmic variants based on ad hoc approximations is strongly correlated with the absolute error of the approximation, and that the effect on local search of ad hoc approximations can be very degrading.

Finally, we briefly address another SCOP belonging to the class of vehicle routing problems: the Vehicle Routing Problem with Stochastic Demands (VRPSD). For this problem, we have implemented and tested several metaheuristics, and we have studied the impact of integrating in them different ad hoc approximations.

Doctorat en sciences appliquées
info:eu-repo/semantics/nonPublished

We present solution methodologies for vehicle routing problems (VRPs) with stochastic demand, with a specific focus on the vehicle routing problem with stochastic demand (VRPSD) and the vehicle routing problem with stochastic demand and duration limits (VRPSDL). The VRPSD and the VRPSDL are fundamental problems underlying many operational challenges in the fields of logistics and supply chain management. We model the VRPSD and the VRPSDL as large-scale Markov decision processes. We develop cyclic-order neighborhoods, a general methodology for solving a broad class of VRPs, and use this technique to obtain static, fixed route policies for the VRPSD. We develop pre-decision, post-decision, and hybrid rollout policies for approximate dynamic programming (ADP). These policies lay a methodological foundation for solving large-scale sequential decision problems and provide a framework for developing dynamic routing policies. Our dynamic rollout policies for the VRPSDL significantly improve upon a method frequently implemented in practice. We also identify circumstances in which our rollout policies appear to offer little or no benefit compared to this benchmark. These observations can guide managerial decision making regarding when the use of our procedures is justifiable. We also demonstrate that our methodology lends itself to real-time implementation, thereby providing a mechanism to make high-quality, dynamic routing decisions for large-scale operations. Finally, we consider a more traditional ADP approach to the VRPSDL by developing a parameterized linear function to approximate the value functions corresponding to our problem formulation. We estimate parameters via a simulation-based algorithm and show that initializing parameter values via our rollout policies leads to significant improvements. However, we conclude that additional research is required to develop a parametric ADP methodology comparable or superior to our rollout policies.

This thesis is concerned with identifying the best decision among a set of possible decisions in the presence of uncertainty. We are primarily interested in situations where the objective function value at any feasible solution needs to be estimated, for example via a ``black-box' simulation procedure. We develop adaptive random search methods for solving such simulation optimization problems. The methods are adaptive in the sense that they use information gathered during previous iterations to decide how simulation effort is expended in the current iteration. We consider random search because such methods assume very little about the structure of the underlying problem, and hence can be applied to solve complex simulation optimization problems with little expertise required from an end-user. Consequently, such methods are suitable for inclusion in simulation software. We first identify desirable features that algorithms for discrete simulation optimization need to possess to exhibit attractive empirical performance. Our approach emphasizes maintaining an appropriate balance between exploration, exploitation, and estimation. We also present two new and almost surely convergent random search methods that possess these desirable features and demonstrate their empirical attractiveness. Second, we develop two frameworks for designing adaptive and almost surely convergent random search methods for discrete simulation optimization. Our frameworks involve averaging, in that all decisions that require estimates of the objective function values at various feasible solutions are based on the averages of all observations collected at these solutions so far. We present two new and almost surely convergent variants of simulated annealing and demonstrate the empirical effectiveness of averaging and adaptivity in the context of simulated annealing. Finally, we present three random search methods for solving simulation optimization problems with uncountable feasible regions. One of the approaches is adaptive, while the other two are based on pure random search. We provide conditions under which the three methods are convergent, both in probability and almost surely. Lastly, we include a computational study that demonstrates the effectiveness of the methods when compared to some other approaches available in the literature.

Recent research has shown that it is often preferable to encode real-world problems as propositional satisfiability (SAT) problems and then solve using a general purpose SAT solver. However, much of the valuable information and structure of these realistic problems is flattened out and hidden inside the corresponding Conjunctive Normal Form (CNF) encodings of the SAT domain. Recently, systematic SAT solvers have been progressively improved and are now able to solve many highly structured practical problems containing millions of clauses. In contrast, state-of-the-art Stochastic Local Search (SLS) solvers still have difficulty in solving structured problems, apparently because they are unable to exploit hidden structure as well as the systematic solvers. In this thesis, we study and evaluate different ways to effectively recognise, model and efficiently exploit useful structures hidden in realistic problems. A summary of the main contributions is as follows: 1. We first investigate an off-line processing phase that applies resolution-based pre-processors to input formulas before running SLS solvers on these problems. We report an extensive empirical examination of the impact of SAT pre-processing on the performance of contemporary SLS techniques. It emerges that while all the solvers examined do indeed benefit from pre-processing, the effects of different pre-processors are far from uniform across solvers and across problems. Our results suggest that SLS solvers need to be equipped with multiple pre-processors if they are ever to match the performance of systematic solvers on highly structured problems. [Part of this study was published at the AAAI-05 conference]. 2. We then look at potential approaches to bridging the gap between SAT and constraint satisfaction problem (CSP) formalisms. One approach has been to develop a many-valued SAT formalism (MV-SAT) as an intermediate paradigm between SAT and CSP, and then to translate existing highly efficient SAT solvers to the MV-SAT domain. In this study, we follow a different route, developing SAT solvers that can automatically recognise CSP structure hidden in SAT encodings. This allows us to look more closely at how constraint weighting can be implemented in the SAT and CSP domains. Our experimental results show that a SAT-based mechanism to handle weights, together with a CSP-based method to instantiate variables, is superior to other combinations of SAT and CSP-based approaches. In addition, SLS solvers based on this many-valued weighting approach outperform other existing approaches to handle many-valued CSP structures. [Part of this study was published at the AAAI-05 conference]. 3. Finally, we propose and evaluate six different schemes to encode temporal reasoning problems, in particular the Interval Algebra (IA) networks, into SAT CNF formulas. We then empirically examine the performance of local search as well as systematic solvers on the new temporal SAT representations, in comparison with solvers that operate on native IA representations. Our empirical results show that zChaff (a state-of-the-art complete SAT solver) together with the best IA-to-SAT encoding scheme, can solve temporal problems significantly faster than existing IA solvers working on the equivalent native IA networks. [Part of this study was published at the CP-05 workshop].

Recent research has shown that it is often preferable to encode real-world problems as propositional satisfiability (SAT) problems and then solve using a general purpose SAT solver. However, much of the valuable information and structure of these realistic problems is flattened out and hidden inside the corresponding Conjunctive Normal Form (CNF) encodings of the SAT domain. Recently, systematic SAT solvers have been progressively improved and are now able to solve many highly structured practical problems containing millions of clauses. In contrast, state-of-the-art Stochastic Local Search (SLS) solvers still have difficulty in solving structured problems, apparently because they are unable to exploit hidden structure as well as the systematic solvers. In this thesis, we study and evaluate different ways to effectively recognise, model and efficiently exploit useful structures hidden in realistic problems. A summary of the main contributions is as follows: 1. We first investigate an off-line processing phase that applies resolution-based pre-processors to input formulas before running SLS solvers on these problems. We report an extensive empirical examination of the impact of SAT pre-processing on the performance of contemporary SLS techniques. It emerges that while all the solvers examined do indeed benefit from pre-processing, the effects of different pre-processors are far from uniform across solvers and across problems. Our results suggest that SLS solvers need to be equipped with multiple pre-processors if they are ever to match the performance of systematic solvers on highly structured problems. [Part of this study was published at the AAAI-05 conference]. 2. We then look at potential approaches to bridging the gap between SAT and constraint satisfaction problem (CSP) formalisms. One approach has been to develop a many-valued SAT formalism (MV-SAT) as an intermediate paradigm between SAT and CSP, and then to translate existing highly efficient SAT solvers to the MV-SAT domain. In this study, we follow a different route, developing SAT solvers that can automatically recognise CSP structure hidden in SAT encodings. This allows us to look more closely at how constraint weighting can be implemented in the SAT and CSP domains. Our experimental results show that a SAT-based mechanism to handle weights, together with a CSP-based method to instantiate variables, is superior to other combinations of SAT and CSP-based approaches. In addition, SLS solvers based on this many-valued weighting approach outperform other existing approaches to handle many-valued CSP structures. [Part of this study was published at the AAAI-05 conference]. 3. Finally, we propose and evaluate six different schemes to encode temporal reasoning problems, in particular the Interval Algebra (IA) networks, into SAT CNF formulas. We then empirically examine the performance of local search as well as systematic solvers on the new temporal SAT representations, in comparison with solvers that operate on native IA representations. Our empirical results show that zChaff (a state-of-the-art complete SAT solver) together with the best IA-to-SAT encoding scheme, can solve temporal problems significantly faster than existing IA solvers working on the equivalent native IA networks. [Part of this study was published at the CP-05 workshop].
Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
Institute for Integrated and Intelligent Systems
Full Text

Das Konzept von aktiven Brownschen Teilchen kann benutzt werden, um das Verhalten einfacher biologischer Organismen oder künstlicher Objekte, welche die Möglichkeit besitzen sich von selbst fortzubewegen zu beschreiben. Als Bewegungsgleichungen für aktive Brownsche Teilchen kommen Langevin Gleichungen zum Einsatz. In dieser Arbeit werden aktive Teilchen mit konstanter Geschwindigkeit diskutiert. Im ersten Teil der Arbeit wirkt auf die Bewegungsrichtung des Teilchen weißes alpha-stabiles Rauschen. Es werden die mittlere quadratische Verschiebung und der effektive Diffusionskoeffizient bestimmt. Eine überdampfte Beschreibung, gültig für Zeiten groß gegenüber der Relaxationszeit wird hergleitet. Als experimentell zugängliche Meßgröße, welche als Unterscheidungsmerkmal für die unterschiedlichen Rauscharten herangezogen werden kann, wird die Kurtose berechnet. Neben weißem Rauschen wird noch der Fall eines Ornstein-Uhlenbeck Prozesses angetrieben von Cauchy verteiltem Rauschen diskutiert. Während eine normale Diffusion mit zu weißem Rauschen identischem Diffusionskoeffizienten bestimmt wird, kann die beobachtete Verteilung der Verschiebungen Nicht-Gaußförmig sein. Die Zeit für den Übergang zur Gaußverteilung kann deutlich größer als die Zeitskale Relaxationszeit und die Zeitskale des Ornstein-Uhlenbeck Prozesses sein. Eine Grenze der benötigten Zeit wird durch eine Näherung der Kurtosis ermittelt. Weiterhin werden die Grundlagen eines stochastischen Modells für lokale Suche gelegt. Lokale Suche ist die Suche in der näheren Umgebung eines bestimmten Punktes, welcher Haus genannt wird. Abermals diskutieren wir ein aktives Teilchen mit unveränderlichem Absolutbetrag der Geschwindigkeit und weißen alpha-stabilem Rauschen in der Bewegungsrichtungsdynamik. Die deterministische Bewegung des Teilchens wird analysiert bevor die Situation mit Rauschen betrachtet wird. Die stationäre Aufenthaltswahrscheinlichkeitsdichtefunktion wird bestimmt. Es wird eine optimale Rauschstärke für die lokale Suche, das heißt für das Auffinden eines neuen Ortes in kleinstmöglicher Zeit festgestellt. Die kleinstmögliche Zeit wird kaum von der Rauschart abhängen. Wir werden jedoch feststellen, dass die Rauschart deutlichen Einfluß auf die Rückkehrwahrscheinlichkeit zum Haus hat, wenn die Richtung des zu Hauses fehlerbehaftet ist. Weiterhin wird das Model durch eine an das Haus abstandsabhängige Kopplung erweitert werden. Zum Abschluß betrachten wir eine Gruppe von Suchern.
Active Brownian particles described by Langevin equations are used to model the behavior of simple biological organisms or artificial objects that are able to perform self propulsion. In this thesis we discuss active particles with constant speed. In the first part, we consider angular driving by white Levy-stable noise and we discuss the mean squared displacement and diffusion coefficients. We derive an overdamped description for those particles that is valid at time scales larger the relaxation time. In order to provide an experimentally accessible property that distinguishes between the considered noise types, we derive an analytical expression for the kurtosis. Afterwards, we consider an Ornstein-Uhlenbeck process driven by Cauchy noise in the angular dynamics of the particle. While, we find normal diffusion with the diffusion coefficient identical to the white noise case we observe a Non-Gaussian displacement at time scales that can be considerable larger than the relaxation time and the time scale provided by the Ornstein-Uhlenbeck process. In order to provide a limit for the time needed for the transition to a Gaussian displacement, we approximate the kurtosis. Afterwards, we lay the foundation for a stochastic model for local search. Local search is concerned with the neighborhood of a given spot called home. We consider an active particle with constant speed and alpha-stable noise in the dynamics of the direction of motion. The deterministic motion will be discussed before considering the noise to be present. An analytical result for the steady state spatial density will be given. We will find an optimal noise strength for the local search and only a weak dependence on the considered noise types. Several extensions to the introduced model will then be considered. One extension includes a distance dependent coupling towards the home and thus the model becomes more general. Another extension concerned with an erroneous understanding by the particle of the direction of the home leads to the result that the return probability to the home depends on the noise type. Finally we consider a group of searchers.

Dans cette thèse nous développons de nouvelles techniques pour résoudre les problèmes d'optimisation multi-critère. Ces problèmes se posent naturellement dans de nombreux domaines d'application (sinon tous) où les choix sont évalués selon différents critères conflictuels (coûts et performance par exemple). Contrairement au cas de l'optimisation classique, de tels problèmes n'admettent pas en général un optimum unique mais un ensemble de solutions incomparables, aussi connu comme le front de Pareto, qui représente les meilleurs compromis possibles entre les objectifs conflictuels. La contribution majeure de la thèse est le développement d'algorithmes pour trouver ou approximer ces solutions de Pareto pour les problèmes combinatoires difficiles. Plusieurs problèmes de ce type se posent naturellement lors du processus de placement et d'ordonnancement d'une application logicielle sur une architecture multi-coeur comme P2012, qui est actuellement développé par STMicroelectronics.

In this thesis, we study three supply chain planning problems. The first two problems fall in the tactical planning level, while the third one falls in the strategic/tactical level. We present a direct application for the first two planning problems in the wind turbines industry. For the third problem, we show how it can be applied to supply chains in the food industry. Many countries and localities have the explicitly stated goal of increasing the fraction of their electrical power that is generated by wind turbines. This has led to a rapid growth in the manufacturing and installation of wind turbines. The globally installed capacity for the manufacturing of different components of the wind turbine is nearly fully utilized. Because of the large penalties for missing delivery deadlines for wind turbines, the effective planning of its supply chain has a significant impact on the profitability of the turbine manufacturers. Motivated by the planning challenges faced by one of the world’s largest manufacturers of wind turbines, we present a comprehensive tactical supply chain planning model for manufacturing of wind turbines in the first part of this thesis. The model is multi-period, multi-echelon, and multi-commodity. Furthermore, the model explicitly incorporates backorder penalties with a general cost structure, i.e., the cost structure does not have to be linear in function of the backorder delay. To the best of our knowledge, modeling-based supply chain planning has not been applied to wind turbines, nor has a model with all the above mentioned features been described in the literature. Based on real-world data, we present numerical results that show the significant impact of the capability to model backorder penalties with general cost structures on the overall cost of supply chains for wind turbines. With today’s rapidly changing global market place, it is essential to model uncertainty in supply chain planning. In the second part of this thesis, we develop a two-stage stochastic programming model for the comprehensive tactical planning of supply chains under supply uncertainty. In the first stage, procurement decisions are made while in the second stage, production, inventory, and delivery decisions are made. The considered supply uncertainty combines supplier random yields and stochastic lead times, and is thus the most general form of such uncertainty to date. We apply our model to the same wind turbines supply chain. We illustrate theoretical and numerical results that show the impact of supplier uncertainty/unreliability on the optimal procurement decisions. We also quantify the value of modeling uncertainty versus deterministic planning. Supplier selection with quantity discounts has been an active research problem in the operations research community. In this the last part of this thesis, we focus on a new quantity discounts scheme offered by suppliers in some industries. Suppliers are selected for a strategic planning period (e.g., 5 years). Fixed costs associated with suppliers’ selection are paid. Orders are placed monthly from any of the chosen suppliers, but the quantity discounts are based on the aggregated annual order quantities. We incorporate all this in a multi-period multi-product multi-echelon supply chain planning problem and develop a mixed integer programming (MIP) model for it. Leading commercial MIP solvers take 40 minutes on average to get any feasible solution for realistic instances of our model. With the aim of getting high-quality feasible solutions quickly, we develop an algorithm that constructs a good initial solution and three other iterative algorithms that improve this initial solution and are capable of getting very fast high quality primal solutions. Two of the latter three algorithms are based on MIP-based local search and the third algorithm incorporates a variable neighborhood Descent (VND) combining the first two. We present numerical results for a set of instances based on a real-world supply chain in the food industry and show the efficiency of our customized algorithms. The leading commercial solver CPLEX finds only a very few feasible solutions that have lower total costs than our initial solution within a three hours run time limit. All our iterative algorithms well outperform CPLEX. The VND algorithm has the best average performance. Its average relative gap to the best known feasible solution is within 1% in less than 40 minutes of computing time.

Combinatorial optimisation problems are an important and well-studied class of problems, with applications in most areas of the computing sciences. Because of their prominence, combinatorial optimisation problems and their related decision problems have been the focus of extensive research for several decades. The propositional satisfiability problem (SAT), in particular, has been the focus of a vast amount of research, and a class of algorithms known as stochastic local search (SLS) algorithms has emerged as the state-of-the art on a variety of SAT problem classes. Much of the recent progress in algorithm development has been facilitated by an improved understanding of the properties of SAT instances and of high-performance SAT algorithms. This thesis studies the search space features underlying the behaviour of stochastic local search algorithms for SAT, extending existing results from the literature and providing novel contributions. Search space features such as plateaus and the interconnectivity between plateaus are defined and studied on a variety of SAT instances, and it is empirically demonstrated that features such as these are responsible for the wide range in instance hardness observed in distributions of syntactically identical SAT instances. Furthermore, the novel concept of the performance criticality of variables in SAT instances is introduced, and the connections between search space structure and performance criticality are investigated. Finally, methods for practically exploiting the knowledge gained by this search space analysis are briefly explored, with the goal of improving the state-of-the-art in SAT solving.
Science, Faculty of
Computer Science, Department of
Graduate