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


The « Hybrid Methods for Combinatorial/Mixed Optimization » Master Class will take place at LAAS-CNRS (LAAS) and is part of the thematic semester « Optimization » organized by Labex CIMI.

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.

Confirmed speakers

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.

Laurent Simon (Computer Science Lab of Bordeaux -Labri- at University of Bordeaux)

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.

Detailed program

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.
Slides of the talk: here. Video of the talk: part 1, part 2.
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.

Talk : slides and video. PySAT solver and exercices: here.
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.

Slides of the talk: here. Video of the talk: part 1, part 2.

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.

Talk by Jean-Bernard Lasserre: slides and 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:

  • Constraint-based local search
  • Searching neighborhoods using constraint programming
  • Large Neighbourhood Search
  • Using local search for pruning and propagation

Slides of the talk : slides - Video of the talk: here

Organizing commitee

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).

Scientific commitee

  • 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