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

Alt text.

⚠️ 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

>>🏭<<