Winter school is cool, don’t be a fool!

Solver implementation
The aim of this workshop is to design, from scratch, a minimalist constraint solver in Python. We will code everything needed to model and automatically solve two standard problems.
Introduction to Choco Solver
In this workshop, we will see how to get to grips with the choco-solver constraint programming library. We'll try to apply the concepts we've learned directly to problems of varying complexity.

The practical sessions will illustrate the fondamentals ideas of the Filtering and Search classes. We will work on a number of problems related to car sequencing, traveling salesman problem and bin-packing to get of better understanding of local consistencies and search techniques. We propose to implement at least one propagator for a global constraint (AtMostSeqCard or WeightedAllDifferent) and one search heuristic. Additionaly, a number of fun quiz (reasoning by hand) are proposed to clarify two fondamental consistency notions: arc consistency and bound consistency.

This lecture explain the pivotal role of search strategies in Constraint Programming (CP). We start by unpacking the 'first fail' principle, a fundamental strategy shaping numerous advanced techniques in CP. Our focus then shifts to expert-designed search strategies, particularly in complex areas like scheduling and vehicle routing, highlighting their practical applications. We'll discuss strategies to accelerate searches, including dominance and symmetry breaking, essential for streamlining the search process. The lecture progresses to advanced successfull black box search methods like conflict-based, activity-based, impact-based, and weighted degree approaches, all derivatives of the first fail principle. We then cover restart-based methods addressing the heavy-tail phenomenon in CP searches and Large Neighborhood Search (LNS) for quickly finding high-quality solutions. Finally, we touch on search parallelization, exploring how multiple processors can be utilized for more efficient problem-solving in CP.

Search has been used for a long time and is present in multiple tools, including constraint programming, mixed integer programming, AI planning, branch-and-bounds of all sorts, and even shortest path algorithms.
While each tool has its own way of conceptualizing search, they also share many similar components. The goal of this lecture is to identify these similar components, and present how they can be combined with each other.
We will start with some simple examples (shortest path algorithms), then move on to some combinatorial optimization problems (a vehicle routing problem, a scheduling problem, and a 2D rectangle packing problem). For each of them, we will combine several search components and obtain state-of-the-art algorithms, showcasing how search can be used effectively.

Explainable constraint solving is concerned with explaining constraint (optimization) problems and their solutions. While having roots in the well-studied topic of explaining unsatisfiability, it is getting renewed attention as part of the wider eXplainable AI (XAI) field. This raises new challenges in terms of interpretability and actionability of explanations, as well as algorithmic challenges with regards to scalability, expressivity and preferences that must be considered.
We will review two general types of explanations in XCP: deductive explanations and contrastive explanations, and provide a deeper view on techniques in these categories, including well established techniques like minimal unsatisfiable subsets and correction subsets, as well as newer techniques such as step-wise explanations, feasibility corrections, inverse optimisation techniques and more. The talk is supported by working implementations on top of the CPMpy library and includes live Python notebook demo's on nurse rostering problems.

Introduction to Constraint Programming
This talk we will give an overview of the main ideas behind Constraint Programming, and show the basics of modelling and constraint solving. We will see how complex combinatorial problems can be easily described with Constraint Programming, while back-end constraint engines use different reasoning techniques to find solutions efficiently.
CP applications
In this session we will give an overview of the wide variety of applications that have been developed using Constraint Programming. We will present some recent projects in more detail, and show where one can find more information about specific application domains.

We will spread the good word about constraint propagation and local consistencies. The former is the prime procedure to prune prohibitively large search trees in constraint programming. The latter is the formal notion used to describe what propagation does, irrespective of how it is done, and is essential to designing, analyzing and comparing constraint propagation algorithms. We will use several examples to introduce some relevant terminology as well as a few important principles, and hopefully persuade you of the significance of constraint propagation.

Our planet has limits, and some people are lacking access to life’s essentials, as pointed out by Kate Raworth’s doughnut. Ensuring that planet and social limits are not over-passed may be viewed as a constraint satisfaction problem, and we may even add an objective function to maximize welfare or minimize resource consumption, for example. So, the question addressed in this talk is: can we use CP to model and solve these problems? In a first part, we study the direct impacts of ICTs (Information and Communication Technologies) on our planet’s boundaries, as CP widely uses ICTs. In a second part, we address the question of defining relevant CP model to ensure that planet and social boundaries are not overpassed. We first study the DICE model designed by William Nordhaus and for which he received the 2018 Nobel prize in economic science « for integrating climate change into long-run macroeconomic analysis ». We study the hypothesis underlying this constrained optimization model and discuss their relevancy. Then, we study rebound effects, that explain why total consumption often increases when improving efficiency, and we illustrate this on examples that involve solving constrained optimization problems.