Master Class in Hybrid Methods for Combinatorial/Mixed Optimization
Master Class in Hybrid Methods
for Combinatorial/Mixed Optimization
CIMI event, Toulouse, France
4 - 5 June 2018
This Master Class focuses on hybrid solution methods for Combinatorial Optimization Problems and Mixed Discrete/Continuous Optimization Problems. These problems, of high practical and theoretical relevance, are the subject of intensive research in several communities within Operations Research and Artificial Intelligence. Because they are very challenging problems, combining different approaches has often been the key in significant computational breakthrough. Many successful problem-specific methods or general-purpose solvers rely in hybridizing several components among Mixed-Integer Linear and Non-Linear programming, Constraint Programming, Dynamic Programming, Boolean Satisfiability, Local Search… This exceptional Master Class funded by the Labex CIMI gathers international experts that will share their experience in several classes hybrid methods.
Pierre Bonami (Laboratoire d'Informatique Fondamentale de Marseille at Aix Marseille University)
Mixed-Integer Linear and Nonlinear Programming Methods
Pierre Bonami is Researcher at LIF/Aix Marseille Université, currently on leave at IBM and developer of CPLEX. He is interested in the development of algorithmic techniques for finding optimal solutions of integer programs and proving their optimality. His research lies mainly in two areas: cuts for mixed integer linear programs (lift-and-project, MIG cuts, Chvatal cuts), and exact algorithms for mixed integer nonlinear programming. In his research he tries to study both theoretical and computational aspects by conducting extended computational experiments. He also tries to make available the codes he develops to conduct computational experiments. He is the project manager of the Bonmin solver and of the CglLandP cut generator. He is a permanent member of the COIN-OR foundation.
Willem Jan van Hoeve (Carnegie Mellon University)
Decision diagrams for Discrete Optimization, Constraint programming, and Integer Programming
Willem van Hoeve is Associate Professor of Operations Researchat Tepper School of Business, Carnegie Mellon University. He is interested in operations research, optimization, constraint programming, integer programming, hybrid solution methods, decision diagrams for optimization, and their application to vehicle routing, scheduling, network design, home care operations. Recently he developed new methodologies based on decision diagrams, that are are compact graphical representations of Boolean functions, to tackle discrete optimization problems.
John Hooker (Carnegie Mellon University)
Hybrid mixed-Integer Programming and Constraint Programming Methods
John Hooker is Professor of Operations Research and Holleran Professor of Business Ethics and Social Responsibility at Tepper School of Business, Carnegie Mellon University. He is a pioneer in the integration of optimization and constraint programming technologies, having written the first book and co-chaired the first conference on the subject. OR/CP integration is now an active research field and is the basis for leading software packages like IBM's OPL Studio and the popular award-winning solver SCIP. He also introduced logic-based Benders decomposition, which can reduce solution times by orders of magnitude and has found a wide variety of applications. More recently, he and T. Hadžić adapted decision diagrams to optimization, and several investigators are now pursuing this line of research.
Paul Shaw (IBM Research)
Combinations of local search and constraint programming
Paul Shaw is Development Manager of CP Optimizer at STSM, Optimization Technology, IBM. At IBM, he heads up constraint programming development, a technology for solving of complex highly combinatorial problems, in CP Optimizer, the CP solver of CPLEX Optimization Studio. My product focus is on product innovation, speed, quality and robustness. He has over twenty years of experience in combinatorial optimization. His technical interests vary over many aspects of science and technology. His specialties include Constraint Programming, Combinatorial Optimization, Local Search and Meta-Heuristics, Vehicle Routing, Packing.
Understanding, using and extending SAT solvers
Laurent Simon is Professor in the Formal Methods group of the Computer Science Lab of Bordeaux (Labri). He teaches at the Bordeaux Polytechnic National Institute (INP) in the computer Science department. He is also associate member of the LRI laboratory in the University of Orsay Paris 11, in the Artificial Intelligence and Inference System group (IASI) . His main research interests are on propositional-based reasoning, SAT solving and efficient Prime Implicates generation / Knowledge Base Compilation. He is also working on decentralized approaches of some of hese topics (reasoning on top of P2P and social networks) and how to push computer science to a real experimental science (especially search algorithms). He is also trying to apply those decentralized reasoning systems to diagnosis of (intrinsic) distributed systems.
The workshop will start on Monday June 4, at 10:00 and will end on Thuesday June 5 at 18:00. It will take place in Salle de conférence at LAAS-CNRS, see Practical Information here.
|Monday the 4th, June|
|10h00 - 10h30||Welcome coffee|
|10h30 - 12h00||
John Hooker : Hybrid Mixed-Integer Programming and Constraint Programming Methods (part 1)
Chair : Christian Artigues
This tutorial will cover basic strategies for integrating mixed-integer programming and constraint programming. Specific topics include: Design of an integrated solver - Combining propagation and relaxation - Mixed integer modeling and cutting planes - Lagrangian methods and domain filtering - Disjunctive programming - Dynamic programming and domain filtering - CP-based branch and price - CP-based Benders decomposition - Some integrated modeling systems and solver.
|12h00 - 13h30||Lunch|
13h30 - 15h00
John Hooker : Hybrid Mixed-Integer Programming and Constraint Programming Methods (part 2)
|15h00 - 15h30||Coffee break|
|15h30 - 18h15||
Laurent Simon : Understanding, using and extending SAT solvers
Chair : Thomas Schiex
Despite its apparent simplicity, the propositional logic is at the heart of a number of pragmatics solutions addressing questions beyond NP. In this tutorial, we will firstly describe the essential ingredients of "Modern" SAT solvers. We will also study how SAT solvers can be used to solve typical puzzle problems, thanks to a set of possible solutions incorporating SAT solvers with higher and higher levels of integration. We will also work on extending our SAT solver to incorporate additional constraints, beyond the initial input in propositional logic. Students will be asked to code their solutions and follow the tutorial illustration in Python.
|Thuesday the 5th, June|
|9h00 - 10h15||
Willem van Hoeve : Decision diagrams for Discrete Optimization, Constraint programming and Integer Programming (part 1)
Chair : Emmanuel Hébrard
Decision diagrams are widely used in computer science as an efficient data structure to represent Boolean functions. More recently, decision diagrams have been introduced to represent and solve optimization problems. In this tutorial we will first introduce the basics of decision diagrams for optimization and explain how restricted and relaxed decision diagrams can be used to generate primal and dual bounds for optimization problems, and can form the basis of a competitive stand-alone solver. We then discuss how decision diagrams can be integrated with other optimization technologies including constraint programming, integer programming, and Lagrangian relaxations.
|10h15 - 10h45||Coffee break|
|10h45 - 12h00||
Willem van Hoeve : Decision diagrams for Discrete Optimization, Constraint programming and Integer Programming (part 2)
|12h00 - 13h30||Lunch|
|13h30 - 15h30||
Pierre Bonami : Mixed-Integer Linear and Nonlinear Programming Methods
Chair : Sonia Cafieri
Mixed Integer Nonlinear Optimization is the optimization of a nonlinear function over a feasible set described by nonlinear functions and integrality constraints. We will review some of the main algorithmic techniques that are employed in commercial solvers. We will then focus on two recent works that are at the crossroad between MINO and combinatorial optimizations: cuts from the binary quadric polytope and max-clique inequalities.
This talk has been replaced by a 1 hour talk by John Hooker and a 1 hour talk by Jean-bernard Lasserre.
Talk by John Hooker: video.
|15h30 - 16h00||Coffee break|
Paul Shaw : Combinations of local search and constraint programming
Chair : Cédric Pralet
This lecture will take a somewhat personal look at combinations of local search and constraint programming in which I have been involved or with which I have experimented. The topics that I will look at include:
Link to the video of the talk: http://www.laas.fr/vod/public/wowza/Shaw_LS-CP.html
Christian Artigues (LAAS-CNRS), Olga Battaïa (ISAE), Sonia Cafieri (ENAC), Helène Fargier (IRIT), Georges Katsirelos (INRA), Cédric Pralet (ONERA), Aude Rondepierre (IMT).
- ENAC : Nicolas Barnier, Sonia Cafieri, Catherine Mancel, Marcel Mongeau, Mohand Sbihi.
- IMT : Aude Rondepierre.
- INRA : Georges Katsirelos, Simon de Givry, Thomas Schiex.
- IRIT : Hélène Fargier, Martin Cooper.
- ISAE : Olga Battaïa, Alain Haït, Emmanuel Rachelson.
- LAAS : Christian Artigues, Denis Arzelier, Cyril Briand, Emmanuel Hébrard, Laurent Houssin, Marie-José Huguet, Pierre Lopez, Julien Moncel, Sandra U. Ngueveu.
- ONERA : Cédric Pralet, Xavier Olive, Stéphanie Roussel.
For any questions, please contact Christian Artigues and Aude Rondepierre : send an email