CP-AI-OR'02 School on Optimization
powerpoint presentation | pdf file
Abstract: The term "integer programming" refers to a complicated collection of methods that have been developed over the last 40 years. We begin with the basic branch and bound algorithm and provide summaries of numerous extensions, including improved relaxations (such as lagrangean relaxation), cutting planes, polyhedral approaches, branch and price, and many other methods. Implications for modeling will also be addressed.
powerpoint presentation | pdf file | paper
Abstract: We discuss formulations of integer programs with a huge number of variables and their solution by column generation methods, i.e., implicit pricing of non basic variables to generate new columns or to prove LP optimality at a node of the branch and bound tree. We present classes of models for which this approach decomposes the problem, provides tighter LP relaxations, and eliminates symmetry. We then discuss computational issues and implementation of column generation, branch and bound algorithms, including special branching rules and efficient ways to solve the LP relaxation. We also discuss the relationship with Lagrangian duality.
powerpoint presentation | pdf file | paper
Abstract: We introduce branch-and-infer, a unifying framework for integer linear programming and finite domain constraint programming. We use this framework to compare the two approaches with respect to their modeling and solving capabilities, to introduce symbolic constraint abstractions into integer programming, and to discuss possible combinations of the two approaches.
powerpoint presentation | pdf file
Abstract: In the recent past, many examples of hybrid applications have been described and the adopted hybrid algorithms shown to provide better results than pure algorithms based on only one technology. Generally speaking, we have to consider the classical compromise between efficiency and flexibility, and the elements of cooperative strategies that impact this compromise. "Efficiency" is the capacity to solve a problem faster: find the optimal solution to a problem and a proof of optimality in less CPU time, or find a better sub-optimal solution in a limited amount of time. "Flexibility" is the ability to reuse the same code or large parts of the same code for different variants of the same problem. In particular, it shall in most cases be easy to include additional constraints without re-designing the overall problem-solving strategy. The goal of hybridization (and, in particular, of the integration of operations research algorithms in a constraint programming framework) is to improve either efficiency or flexibility (or both) without sacrificing the other. Three different effects of hybridization can be distinguished: (1) the effect of decomposing a problem into sub-problems which are efficiently solvable by different techniques; (2) the effect of allowing different techniques to exchange information (lower bounds for the optimization criterion or criteria, domain reductions, cuts, optimal solutions of sub-problem relaxations) on a given problem instance; (3) the effect of organizing search in a manner that allows different techniques to bring about their own advantages in terms of efficiency and flexibility. The talk will illustrate these three effects through examples taken from the literature, mostly from the scheduling and vehicle routing domains.
powerpoint presentation | pdf file | paper 1 | paper 2
Abstract: The benefits of a tight hybridization of Constraint Programming (CP) and Operations Research (OR) are increasingly recognized in tackling large scale combinatorial optimization problems. Building hybrid solving algorithms requires a single modelling and solution environment which exploits the complimentary strengths of CP and OR and cooperates their solution methods. ECLiPSe is a constraint logic programming platform for the development of hybrid solving algorithms. During the first part of the course, we show how ECLiPSe supports the integration of different cooperative solvers. We outline the language features which enable the co-ordination and the control of the solvers as well as the information-passing between them during the search. The second part of the course presents a CP-OR hybridization scheme developed in ECLiPSe and called probe backtrack search which is a repair-based extension of conventional backtrack search: the CP engine is supported by a lookahead OR algorithm which derives value suggestions to drive the search into potentially feasible regions. The third part of the presentation focuses on the application of the scheme to solve a commercial scheduling problem with piecewise linear optimization. We report a systematic evaluation and analysis of the hybrid solver under different strategies.
powerpoint presentation | pdf file | paper
Abstract: Both the Artificial Intelligence (AI) community and the Operations Research (OR) community are interested in developing techniques for solving hard combinatorial problems. OR has built heavily on mathematical programming formulations such as integer and linear programming, while AI has developed constrained-based search and inference methods. Recently, we have seen a convergence of ideas, drawing on the individual strengths of these paradigms. Problem structure and randomization are overarching themes in the study of these approaches. In this lecture I'll discuss how the study of the structure of combinatorial search problems and related phenomena is changing the way we characterize the computational complexity of combinatorial problems, beyond the worst-case complexity notion. Topics covered will include constrainedness, phase transition phenomena, backbone structure, and small world topology. In the second part of the tutorial I'll talk about randomized algorithms, the best current methods for solving computationally hard problems. In particular, I'll describe recent results on the characterization of the probability distributions of complete randomized search methods that have led to novel strategies to dramatically boost combinatorial search methods, with applications in planning and scheduling.
Filippo Focacci* and Andrea Lodi**
powerpoint presentation | pdf file | paper
Abstract: Real-world combinatorial optimization problems have two main characteristics that make them difficult: they are usually large and they are not pure, i.e., they involve a heterogeneous set of side constraints. Hence, in most cases, exact approaches cannot be applied to solve real-world problems, whereas Local Search (LS) methods have been proved to obtain very good results in practice. In the last decade Constraint Programming (CP) has shown its effectiveness in modeling and solving real-world combinatorial optimization problems. One main advantage of using CP systems is flexibility: CP supports the design of declarative, compact and flexible models where the addition of new constraints is straightforward and does not affect the previous model. Thus, many real-world combinatorial optimization problems may benefit from the efficiency of LS as well as from the flexibility of CP. In this tutorial, we review hybrid methods that combine principles from both methods. A first set of such hybrids belongs to the family of local search methods (going from one solution to a neighbor one) and use CP as a way to efficiently explore large neighborhoods with side constraints. A second set belongs to the family of global search (tree search) methods and use LS as a way to improve some of the nodes of the search tree or to explore a set of paths close to the path selected by a greedy algorithm in the search tree. In short, LS may use ideas from CP in order to make large neighborhoods more tractable, while CP may use ideas from LS to explore a set of solutions close to the greedy path in a tree search and converge more quickly towards the optimum. The goal of the tutorial is twofold. On the one hand it aims at presenting the state of the art of the research on Constraint Programming and Local Search, and to discuss some possible avenue of future research. On the other hand it aims at showing how different techniques can, in practice, be used to improve the performance of optimization applications for real-world problems.