Charles Prud'homme, Philippe David

Sept. 2025

IMT Atlantique, LS2N, TASC

< press [N] / [P] to go the next / previous slide >

Powerful paradigm for solving combinatorial problems

Originated from AI and OR

Widely used in scheduling, planning, configuration, etc.

Linear Programming, Integer Programming, SAT, CP , …

Heuristics, Metaheuristics, Local Search, …

CP is an exact method, meaning it guarantees to find a solution if one exists or proves no solution is possible.

Typically it involves searching the solution space exhaustively but with intelligent pruning.

- Both CP and LP are used to solve optimization problems.
- They both define variables, domains, and constraints.
- Both use systematic search techniques for exploring solutions.

**LP**: Problems are expressed using linear constraints and an objective function.**CP**: Can handle non-linear and logical constraints without requiring an objective function.

CP is more flexible in expressing combinatorial relationships.

- A set of variables : X = {X1, X2, …, Xn}
- A domain for each variable: D = {D1, D2, …, Dn}
- A set of constraints: C = {C1, C2, …, Cm}

A variable represents an unknown value that needs to be determined.

- In a Sudoku puzzle, each cell can be a variable representing its value.
- In a scheduling problem, each task can be a variable representing its start time.
- In a routing problem, each node can be a variable representing its successor.
- In a packing problem, each item can be a variable representing its bin.

The domain of a variable is the set of possible values that the variable can take.

- For a Sudoku cell, the domain might be the set of possible values: {1, 2, 3, 4, 5, 6, 7, 8, 9}.
- For a scheduling task, the domain might be the set of possible start times: [1, 999].
- For a routing problem, the domain might be the set of possible successors: {A, B, C, D}.

A constraint defines a condition that must be satisfied by the variables in its scope.

- In Sudoku, “
*each row must contain all numbers from 1 to 9*” is a constraint. - In scheduling, “
*no two tasks can happen at the same time*” is a constraint. - In routing, “
*each node must be visited exactly once*” is a constraint. - In packing, “
*the sum of weights in each bin must not exceed the bin capacity*” is a constraint.

A solution is an assignment of values to all variables such that all constraints are satisfied.

CP problems may have one, many, or no solutions.

Constraint propagation is a core technique in CP to reduce the domain of variables.

- Propagates the impact of constraints throughout the problem, reducing search space.
- Pruning infeasible values from domains.

Consider two variables `X`

and `Y`

with domain `{1, 2, 3}`

and a constraint `X > Y`

.

After propagation:

- the domain of
`X`

becomes`{2,3}`

. - the domain of
`Y`

becomes`{1,2}`

.

*Global constraints* are used to capture common patterns and enable efficient propagation.

In real-world problems, propagation can significantly reduce the time it takes to find a solution.

CP solvers alternate between **Depth-First Search (DFS)** and constraint propagation to find a solution.

DFS explores one possible solution at a time and backtracks whenever a constraint is violated.

CP solvers explore possible assignments of values to variables.

Each node in the search tree represents a partial assignment, validated through constraint propagation.

When a conflict arises, CP solvers backtrack.

- This means undoing the most recent variable assignment and trying an alternative.
- This is crucial for ensuring that all potential solutions are explored.

**Expressive**: Can handle complex relationships and constraints.**Flexible**: Easily adapts to various domains like scheduling, routing, and resource allocation.

- Scheduling (e.g., airline crew scheduling).
- Resource allocation (e.g., production planning).
- Routing problems (e.g., vehicle routing).

Constraint Programming is a versatile and powerful tool for solving complex combinatorial problems.

Ideal for problems with rich, non-linear constraints.