2014 ACP Summer School on
Practical Constraint Programming
Bologna, Italy
June 2014

Practical Constraint Programming

Slides:

Slides of the lecturers and Python fragments.

OR Tools Documentation

  • Hadrien Cambazard (Grenoble Institute of Technology)
  • Pascal Van Hentenryck (NICTA)
  • Willem Jan Van Hoeve(Carnegie Mellon University)
  • Andrea Lodi (University of Bologna and IBM)
  • Michele Lombardi (University of Bologna)
  • Michela Milano (University of Bologna)
  • Laurent Perron (Google)
  • Louis-Martin Rousseau (CIRRELT, Polytechnique de MontrĂ©al)
  • Pierre Schaus (UCLouvain)

Summary of the topics

Hadrien Cambazard

This lecture will focus on the practical use of Constraint Programming on three applications related to routing and packing: the Travelling Purchaser Problem which is a generalization of the Traveling Salesman Problem; a variant of Bin-Packing occurring in energy optimization for data-centres; a matrix decomposition problem involved in the sequencing of multi-leaf collimators in radiotherapy. The three problems will be used to present and illustrate the Constraint Programming (CP) "methodology". We will explain illustrate the important choices that we face when tackling a problem using CP. Two elements will be highlighted in particular:

  • How to choose the granularity of the model and its importance for both propagation and search.
  • How to handle the objective function and especially the integration of costs in well known global constraints (such as NValue and Bin-Packing)

Pascal Van Hentenryck

This tutorial reviews the applications of constraint programming and hybrid optimisation to computational disaster management. These applications raise significant challenges for optimisation technology, given their modelling and computational complexity, their underlying operational constraints, and the need to cope with complex infrastructures and human behaviour. The tutorial will cover strategic, operational, and recovery applications in this space and highlights the critical role of constraint programming and hybrid optimisation.

Willem Jan Van Hoeve

Global constraints

Global constraints compactly represent combinatorial structures that often arise in practice.
For example, the `alldifferent' global constraint represents that a set of variables take distinct values, and it can be used, e.g., to model permutation problems.
Constraint programming systems make use of global constraints to ease the model representation and improve the solving process.
This lecture will introduce a number of global constraints, including alldifferent, cardinality, and sequencing constraints. Example applications as well as algorithmic details of the associated constraint propagation will be provided.

Hybrid methods

The integration of CP and IP technology has been shown to be a powerful combination, especially for solving problems that combine a highly combinatorial component with a (linear) objective function. This lecture will explain how CP and IP can be integrated, from the embedding of linear relaxations in global constraint propagation, to schemes such as column generation and Benders decomposition.

Andrea Lodi

Fundamentals of MILP and heuristics in MILP solvers. (More information will be available over time)

Michela Milano

This introductory course will provide some insights on the basic concepts behind constraint satisfaction and
constraint programming. Modeling and solving techniques will be described. The course will explain some basic
concepts such as of constraint modeling and constraint propagation leaving the details of global constraints to
a dedicated lecture. Search strategies will also be presented along with the most commonly used search heuristic
Running examples will be used to ground the described concepts on practical problems.

Laurent Perron

CP solver technology and internals

  • Domain & Constraint stores
  • Fix-point and propagation queues
  • Trailing mechanism (reversible values)
  • Search (how to implement, how )
  • Domain representations (+ trailing of domains)
  • Constraint Implementation API: what supports are available in solvers (delta, propagation events, etc)

Some hands-on exercises using OR-Tools in Python will be proposed (modeling, large neighborhood search, constraint implementation).

Louis-Martin Rousseau

This course will focus on the strength, weaknesses, opportunities and threats which faces Constraint Programming in practical settings. We show example where CP was quite useful in providing a first and acceptable solution for problem which either had a strong scheduling components, or that exhibit complex non linearities in their formulation. We will discuss decomposition approaches, which allows to take advantage of the strength of CP and mitigate some of its weaknesses. We will illustrate cover industrial applications in personnel scheduling, transportation (both people and wood), industrial packing for retail and bike sharing logistics.

Pierre Schaus

Search in CP:

  • search tree exploration algorithms
  • how to express search in a solver
  • dynamic symmetry breaking during search
  • default (back-box) search
  • restarts
  • large neighborhood search
  • experience on the importance of search for solving practical problems

Schedule