Master Class in Hybrid Methods for Combinatorial/Mixed Optimization

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.

John Hooker : Hybrid Mixed-Integer Programming and Constraint Programming Methods (part 2)

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.

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.

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.

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