We will see

• A short presentation of Choco-solver
• The key elements of modelling and solving
• Some ways of extending the library
• Playing with some problems

We will not see

• What is Constraint Programming
• How a constraint solver works, see this presentation instead
• High-level modelling languages like XCSP$^3$ / PyCSP3, MiniZinc, CPMpy, …

Choco-solver

Features

• Since the early 2000s
• Open-source (BSD-License)
• Java-based (jdk8)
• Python binding available (WIP)
• Available on MCR and pypi
• Hosted on Github

• Parsers for XCSP$^3$, MiniZinc and DIMACS CNF files
• Included in PyCSP3 (-solver=choco)
• As tier 3 solver in CPMpy (since 0.9.17)

• About 3 releases per year
• 4.10.14 is the current version
• $\approx5,860$ downloads per month, according to MCR
• 5 types of variable available
• $> 200$ propagators
• State-of-the-art search strategies
• Almost LCG-ready

Visit the website for more documentation, tutorials, javadoc , etc

Getting Started

• JRE 11+ installed (Oracle or OpenJDK)
• Easier with:
  • an IDE: IntelliJ IDEA, Eclipse IDE, Apache NetBeans or VSCode
  • a build automation tool: Apache Maven 3+ or Gradle 6+

A first example

int n = 8;
Model model = new Model(n + "-queens problem");
IntVar[] vs = model.intVarArray("Q", n, 1, n);
model.allDifferent(vs).post();
for(int i  = 0; i < n-1; i++){
    for(int j = i + 1; j < n; j++){
        model.arithm(vs[i], "!=", vs[j], "-", j - i).post();
        model.arithm(vs[i], "!=", vs[j], "+", j - i).post();
    }
}
Solution solution = model.getSolver().findSolution();
if(solution != null){
    System.out.println(solution.toString());
}

Modelling

Creation of a Model instance

Model is the central object in the Choco-solver library

• Creating a model is the first essential step in declaring and solving a problem.
• Variables are declared via the model
• Constraints too

In fact, almost anything can be done via a Model instance$^1$.

$1$: So you don’t have to know all the objects in advance.

Several builders

Model m = new Model();								 							 // 1
Model m = new Model(String name);					 					 // 2
Model m = new Model(settings settings);				 			 // 3
Model m = new Model(String name, Settings settings); // 4

Prefer choices 1 and 2 to start with.

package apetizer;



public class Example{

    public static void main(String[] args){

    }
}

package apetizer;

import org.chocosolver.solver.Model;

public class Example{

    public static void main(String[] args){
        Model myModel = new Model("My first model");
    }
}

Variables and domains

A variable

• is a symbolic representation of an unknown quantity/decision,
• comes with potential values that the solver can assign to it, a.k.a. its domain,
• to be determined/assigned during the problem-solving process.

In a scheduling problem

• Variables : the start time of various tasks
• Domains : the set of possible start time slots

In a packing problem

• Variables : the assignment of items to bins
• Domains : the set of possible bins

In a routing problem

• Variables : the nodes visited on a tour
• Domains : the potential successors of each node

Different types of variables are available:

• IntVar has its values in $\mathbb{Z}^1$
• IntViews relies on an IntVar
  • like IntAffineView
• BoolVar (and BoolView) has its values in {$0,1$}
  • sub-type of IntVar

• Task to manage with task/interval: $s+d = e$
• SetVar and SetView
• (Un)DirectedGraphVar and GraphView
• and also RealVar

Ways to declare integer variables

Model m = new Model();
IntVar x = m.intVar("x", 0, 4);
IntVar y = m.intVar("y", new int[]{1,3,5});
IntVar[] vs = m.intVarArray("v", 4, 1, 3);
IntVar[][] ws = m.intVarMatrix("w", 2, 2, 1, 2);

Ways to declare Boolean variables

Model m = new Model();
BoolVar b = m.boolVar("b");
BoolVar[] bs = m.boolVarArray("bs", 10);
BoolVar[][] bss = m.boolVarMatrix("bss", 4, 3);

Similar APIs for other types of variables.

Some views declaration

Model m = new Model();                        
IntVar x = m.intVar("x", 0, 5);               
IntVar v = m.intView(2, x, -3); // v = 2.x - 3
BoolVar b = m.isEq(x, 2); // b = (x == 2)     
BoolVar n = b.not(); // n = !b    

And also abs(x), mu(x, 2), neg(x), isLeq(x, 3), …

Reading a variable

Model m = new Model();                                    
IntVar x = m.intVar("x", 0, 4);                           
System.out.printf("Variable : %s = [%d, %d]\n",           
        x.getName(), x.getLB(), x.getUB());               
System.out.printf("%s is %s instantiated\n",              
        x.getName(), x.isInstantiated() ? "" : "not");   

outputs

Variable : x = [0, 4]
x is not instantiated   

If instantiated, a variable can return its assignment value with x.getValue().

ABCDE x 4 = EDCBA

>>🥛<<

This clickable logo indicates that a workshop is available at Caseine

A Model

• variables
  • $\forall i \in \{a,b,c,d,e\}, l_i \in [ 0,9]$
• constraints
  • $\forall i\neq j \in \{a,b,c,d,e\}, l_i \neq l_j$
  • $39999l_a + 3990l_b + 300l_c - 960l_d - 9996l_e = 0$

Can you guess his year of birth?

>>🥛<<

A Model

• parameter
  • $input$: the current year
• variables
  • $\forall i \in \{th,hu,te,on\}, x_i \in [0,9]$
  • $age \in [0,99]$
• Constraints
  • $x_{th} + x_{hu} + x_{te} + x_{on} = {age}$
  • $1000x_{th} + 100x_{hu} + 10x_{te} + x_{on} + age = input$

Constraints

(and propagators)

A constraint

• represents a problem's requirements or limitations,
• defines a relationships among variables,
• expresses conditions that must be satisfied by the values assigned to the variables,
• is equipped with a filtering algorithm.

For example: $X < Y$

The goal of constraint programming is to find a combination of variable assignments that simultaneously satisfies all the specified constraints.

Basic constraints

Adding a constraint to the model

What if you want to express such a a non-linear constraint 🔋 ?

In extension

This can be achieved with a Table constraint

Model m = new Model();
IntVar c = m.intVar("SoC", 0, 100);
IntVar v = m.intVar("cV", 1140, 1280);
Tuples tuples = new Tuples();
tuples.add(100, 1273);
tuples.add(90, 1240);
tuples.add(80, 1235);
//...
tuples.add(20, 1195);
tuples.add(10, 1151);
m.table(c, v, tuples).post();

Types of Table constraints

Allowed tuples

Model m = new Model();
IntVar[] xs = m.intVarArray("x", 3, 1, 3);

// all equal
Tuples tuples = new Tuples();
tuples.add(1, 1, 1);
tuples.add(2, 2, 2);
tuples.add(3, 3, 3);

m.table(xs, tuples).post();

Forbidden tuples

Model m = new Model();
IntVar[] xs = m.intVarArray("x", 3, 1, 3);

// *not* all equal
Tuples tuples = new Tuples(false);
tuples.add(1, 1, 1);
tuples.add(2, 2, 2);
tuples.add(3, 3, 3);

m.table(xs, tuples).post();

Universal value

Like '*' symbol in regular expression.

Model model = new Model();
IntVar[] xs = m.intVarArray("x", 3, 0, 3);

Tuples ts = new Tuples();
int star = 99;
ts.setUniversalValue(star);
ts.add(3, star, 1);
ts.add(1, 2, 3);
ts.add(2, 3, 2);
model.table(xs, ts).post();

Hybrid tuples

Model model = new Model();
IntVar[] xs = m.intVarArray("x", 3, 1, 3);

HybridTuples tuples = new HybridTuples();
tuples.add(ne(1), any(), eq(3));
tuples.add(eq(3), le(2), ne(1));
tuples.add(lt(3), eq(2), ne(b));
tuples.add(gt(2), ge(2), any());

model.table(xs, tuples).post();

It is also possible to express a constraint from a variable

Expressions

Example

$(x = y + 1) \lor (x+2 \leq 6)$

IntVar x = //...
IntVar y = //...
x.eq(y.add(1)).or(x.add(2).le(6)).post();

Adding an expression to the model

Sujiko

>>🥛<<

A Model

• Parameters
  • $S_0, S_1, S_2, S_3$: the four circled number clues
  • $f_{i,j}$: some fixed cells
• Variables
  • $\forall i,j \in [0,2], x_{i,j} \in [0,9]$
• Constraints
  • $\forall i\neq i’, j\neq j’ \in [0,2], x_i \neq x_j$
  • $\forall i \in [0,3], k = \frac{i}{2}, \ell = i \mod 2,$ $x_{k,\ell} + x_{k + 1,\ell} + x_{k,\ell + 1} + x_{k + 1,\ell +1} = S_i$
  • +clues

Global Constraints

Definition(s)

an expressive and concise condition involving a non-fixed number of variables

[GCCAT]

allDifferent($x_1,x_2,\dots$)

Definition(s)

a constraint C is often called “global” when “processing” as a whole gives better results than “processing” any conjunction of constraints that is “semantically equivalent” to C

[BvH03]

allDifferent($x_1,x_2,x_3$) $\iff (x_1\neq x_2) \land (x_2\neq x_3) \land (x_3\neq x_1)$

Example of constraints

cumulative(starts, durations, heights, capacity)

Example of constraints

binpacking(bins, weigths, capacity)

Example of constraints

circuit(successors)

Some cardinality constraints

Some connection constraints

Some Packing and Scheduling constraints

Some Graph-based constraints

Magic Sequence

>>🥛<<

Solving

CSP

The solving process is managed by a unique Solver instance attached to a model.

Model model = new Model();

// ... problem description ...

Solver solver = model.getSolver();
if(solver.solve()){
	// here you can read the variables' value
	System.out.printf("%s is fixed to %d\n",
						x.getName(), x.getValue());
}

A call to solver.solve() returns true if a solution exists, false otherwise.

CSP

The solving process is managed by a unique Solver instance attached to a model.

Model model = new Model();

// ... problem description ...

Solver solver = model.getSolver();
if(solver.solve()){
	// here you can read the variables' value
	System.out.printf("%s is fixed to %d\n",
						x.getName(), x.getValue());
}

Since the solver stops on a solution,
all the variables are fixed and their value can be read.

CSP

The solving process is managed by a unique Solver instance attached to a model.

Model model = new Model();

// ... problem description ...

Solver solver = model.getSolver();
while(solver.solve()){
	// here you can read the variables' value
	System.out.printf("%s is fixed to %d\n",
						x.getName(), x.getValue());
}

Enumerating solutions can be done in a while-loop.

Solution

We can capture the current state of variables in a Solution.

List<Solution> solutions = new ArrayList<>();
while(solver.solve()){
	solutions.add(new Solution(model).record());
}

Solution

This can also be achieved in one line of code

Solution solution = solver.findSolution();

List<Solution> solutions = solver.findAllSolutions();

COP

An IntVar to maximize/minimize .

Solution bSol = solver.findOptimalSolution(obj, maximize);
List<Solution> bSols = solver.findAllOptimalSolutions(obj, max);

Solving is reducing

Backtracking algorithm

• recursive traversal of the search tree
• make/cancel decisions
• backtrack on failure
• incremental construction of a solution

Branch and Propagate

⚠️ 2-way branching

Making decisions

Can't we just leave it to the solver?

Bring business knowledge

Help moving towards a solution

but Yes, we can

Making decisions

• choose a free variable (how?)
• select an operator (very often $=$)
• determine a value (how?)

Continue as as long as necessary

Select the next variable

• input_order, first_fail, smallest,…
• dom/wdeg, FBA, CHS, ABS, …

Choose a value

• min, max, med, …

Topping

• Combining searches
• Restarting: geo, luby
• Meta-strategy: lc, cos
• Phase saving,
• Best

Define your own

solver.setSearch(Search.intVarSearch(
    variables -> Arrays.stream(variables)
          .filter(v -> !v.isInstantiated())
          .min((v1, v2) -> closest(v2, map) - closest(v1, map))
          .orElse(null),
    v -> closest(v, map),
    DecisionOperator.int_eq,
    planes
));

[aircraft landing]

Turnkey enumeration strategies

// Override the default search strategy
solver.setSearch(
	Search.lastConflict(
		Search.domOverWDegSearch(vars)));
// possibly combined with restarts
solver.setLubyRestart(2, new FailCounter(model, 2), 25000);
solver.findSolution();

Have a look at the Search factory.

Monitoring

Information on research

It is possible to have insights on the search process

solver.showShortStatistics();
while(solver.solve()){};

Or to execute code on solutions using monitors:

solver.plugMonitor((IMonitorSolution) () -> {
    // do something here
});

Limits

The search space exploration can be limited.

solver.limitTime("10s");
solver.limitSolution(5);
solver.findAllSolutions();

The first limit reached stops the search.

Warehouse Location

>>🥛<<

Next steps

Thank you