Constraint Programming Winter School
Topic outline
-
General
-
If you continue to work on the labs and you have questions, you can push your code in the lab so we can access it and contact us:
- Hadrien: hadrien.cambazard@grenoble-inp.fr
- Arnaud: arnaud.malapert@univ-cotedazur.fr
- Charles: charles.prudhomme@imt-atlantique.fr
-
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.Quiz: 1 File: 1 -
In this tutorial, we're going to take over the choco-solver library.
Choco-solver is a constraint programming library designed to solve combinatorial problems with ease and efficiency. Developed in Java, it offers a comprehensive set of tools for modeling and solving constraint satisfaction problems (CSPs) and constraint optimization problems (COPs).
Its intuitive and flexible API allows developers to express problem constraints in a declarative manner, enabling rapid prototyping and experimentation. Choco-solver employs state-of-the-art algorithms and search strategies to efficiently explore the solution space, providing optimal or near-optimal solutions for a wide range of real-world problems.
Whether you're solving scheduling conflicts, resource allocation, or configuration problems, Choco-solver offers a reliable and scalable solution for tackling complex optimization challenges.
Page: 1 -
Constraint propagandaWe 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.Files: 6 Text and media areas: 2 Quizzes: 4
-
Search in Focus: The Yang to Modeling's Yin in Constraint Programming (P. Schaus, UCLouvain)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 algorithms for combinatorial optimization: a guided tour (Luc Libralesso, AlmaSCOP)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.Files: 2 -
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.Files: 2 -
Explainable Constraint Programming
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.
Files: 2 -
In this tutorial, we are going to code a minimalist constraint solver.
Such a minimalist constraint solver is designed with simplicity in mind, focusing on essential functionalities to solve constraint satisfaction problems (CSPs) with the aim of understanding how it works.
Its design revolves around a lightweight architecture, implemented in Python, a compact programming language. The solver prioritizes fundamental constraint propagation techniques and basic search algorithms to efficiently explore the solution space without consideration about memory or computational requirements.
By eschewing unnecessary features and optimizations, the minimalist constraint solver offers a lightweight and easy-to-understand solution for solving a variety of combinatorial problems, making it suitable for applications where simplicity and speed are paramount.
-
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.
File: 1 -
The school will be evaluated by the CNRS. The purpose of this questionnaire is to understand the background of the participants and their expectations in order to evaluate the school, in regard to its scientific objectives and methods.