The first part of the tutorial will review the use of linear programming within constraint programming approaches. The main focus of this tutorial will be about the use of the linear relaxation and reduced costs as bounding and filtering mechanisms. It is intended for an audience with some basic knowledge of the simplex algorithm and will go through a series of examples to illustrate reduced cost filtering. Additionally, we will try to review the various ways these techniques have been used together in the past and some successful applications.

The second part of the tutorial will review the use of dynamic programming as an algorithmic technique for filtering global constraints and in particular weakly NP-hard constraints. We will review existing global constraints relying on this technique such as knapsack, regular, shortest path, … but also show a number of dedicated cases related to routing and scheduling.

Generalizations of Benders decomposition have found a wide range of applications, often resulting in order-of-magnitude reductions in solution time. They are ideal for combining CP with other solution methods, such as mixed integer programming and heuristics. The talk will cover logic-based Benders decomposition (the most versatile generalization of Benders) and branch-and-check methods (which combine Benders with a branching strategy). It will illustrate the methods with several real-world applications.

Binary and multivalued decision diagrams have long been used for circuit design and product configuration but have recently been adapted to CP and optimization. In CP, they provide a richer medium for constraint propagation than the traditional domain store and can propagate stronger forms of consistency than domain consistency, such as projection. In optimization, they provide a relaxation that does not require linearity or convexity, and they can be combined with Benders decomposition. The talk will show how decision diagrams can outperform state-of-the-art CP and mixed integer solvers.

Within the context of global constraints the course focusses on the following aspects of automata constraints:

• types of automata
• reformulation of automata
• guideline for creating automata
• synthesising automata from transducers
• implied constraints related to automata constraints (e.g. abstracting the execution of several automata in the context of matrix models, glue matrices for reversible automata)
• using automata for describing specific sets of optimal solutions

For constraint problems and many other combinatorial search problems, there is often not only one, but multiple ways of solving it. Different algorithms exhibit vastly different performances on a given instance. We want to solve the problem as quickly as possible of course, but how do we find out which algorithm is the best? Even experts often struggle to make this decision. In addition, many solvers have parameters that need to be set to get the best performance. This is even harder to do for humans.

In this tutorial, we will learn how to tackle this automatically. Given some idea of how algorithms behave in practice, we can build models that make the decision which algorithm to choose for a given instance automatically. Similarly, we can explore the space of possible parameter settings and build a model of how the parameters affect performance. There will be hands-on exercises with state of the art tools.

In this course, we present different ways of using parallelism in constraint programming. First, we will recall some basic in parallelism (atomic operation, concurrency, distributed computing ...). In the second part, we will consider different possible uses of parallelism in CP: Distributed CSPs, parallelization of the propagation mechanism, portfolios methods and enumeration in parallel. Then, we will focus our attention on the latter point and consider three methods: the simple decomposition, the work stealing method and the embarassingly parallel search. We will show the advantages and drawbacks of these methods on present experimental results using different solvers on multicore machines and data centers. In the last part, we try to give some answer to the following question: "how can I solve a problem in less of one hour at the minimal". Notably, we will show how we can use cloud computing to speed up the resolution. We will give some experimental results for the Microsoft Azure cloud.

TBD

Constraint Programming is used in a number of application fields, ranging from producton planning and scheduling in aircraft manufacturing to blending wines for vineyards in the south of France. The key to its use is the simplicity of expressing the problem in a declarative form, and the ease of adding or modifying constraints of the problem as the environment changes. This talk gives an overview of the different types of problems solved with Constraint Programming, the methods that are used, and the specific advantages that Constraint Programming offers for application development.