/*
* Copyright (C) 2017 COSLING S.A.S.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
import org.chocosolver.solver.Model;
import org.chocosolver.solver.ParallelPortfolio;
import org.chocosolver.solver.Solver;
import org.chocosolver.solver.search.strategy.Search;
import org.chocosolver.solver.variables.IntVar;
import org.chocosolver.util.tools.ArrayUtils;
/**
* Simple example to see how to use parallelism with Choco Solver through portfolios
* @author Jean-Guillaume FAGES (cosling)
* @version choco-solver-4.0.4
*/
public class ParallelGridCol {
private final static int TIME_LIMIT = 30;
public static void main(String[] args){
// Grid colouring problem taken from the MiniZinc challenge 2015 at
// http://www.minizinc.org/challenge2015/mznc2015_probs/grid-colouring/GridColoring.mzn
// instance parameters
int n = 10;
int m = 5;
System.out.println("%%%%%%%%%%%%%%%%%%%%%%%%%%");
System.out.println("Solving GridColouring "+n+"_"+m);
System.out.println("%%%%%%%%%%%%%%%%%%%%%%%%%%");
System.out.println("Single thread using model search (min domain / min value)");
solve(n,m,0);
System.out.println("%%%%%%%%%%%%%%%%%%%%%%%%%%");
System.out.println("Single thread using Activity Based Search");
solve(n,m,1);
System.out.println("%%%%%%%%%%%%%%%%%%%%%%%%%%");
System.out.println("Portfolio using both model search and Activity Based Search");
solve(n,m,2);
System.out.println("%%%%%%%%%%%%%%%%%%%%%%%%%%");
}
private static void solve(int n, int m, int conf){
// solving
long time = System.currentTimeMillis();
if (conf<2) { // single thread solving (usual method)
Model ca = buildModel(n,m,conf==0);
while (ca.getSolver().solve()){
System.out.println("Solution found (objective = "+ca.getSolver().getBestSolutionValue()+")");
}
}else{ // portfolio optimization (uses bound sharing)
ParallelPortfolio portfolio = new ParallelPortfolio();
portfolio.addModel(buildModel(n,m,true));
portfolio.addModel(buildModel(n,m,false));
while (portfolio.solve()){
System.out.println("Solution found (objective = "+portfolio.getBestModel().getSolver().getBestSolutionValue()+")");
}
}
// print solver runtime
int runtime = (int)((System.currentTimeMillis()-time)/1000);
if(runtime < TIME_LIMIT) {
System.out.println("Optimality proved in " + runtime + "s");
}else{
System.out.println(TIME_LIMIT+"s timeout reached");
}
}
private static Model buildModel(int n, int m, boolean mznSearch) {
Model model = new Model("GridColouring "+n+"_"+m);
// decision variables x[i][j] = k means cell (i,j) takes color k
IntVar[][] x = model.intVarMatrix("x", n, m, 1, Math.min(n,m));
// flat representation of x
IntVar[] vars = ArrayUtils.flatten(x);
// objective variable
IntVar objective = model.intVar(1,Math.min(n,m));
// minimize the objective variable
model.setObjective(Model.MINIMIZE, objective);
// objective function : number of colors that are used (colors are symmetrical)
model.max(objective, vars).post();
// grid constraints
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
for(int k=0;k<m;k++){
for(int l=k+1;l<m;l++){
model.or(// at least one of these constraints must be satisfied
model.arithm(x[i][k],"!=",x[i][l]),
model.arithm(x[i][l],"!=",x[j][l]),
model.arithm(x[j][k],"!=",x[j][l]),
model.arithm(x[i][k],"!=",x[j][k])
).post();
}
}
}
}
// tuning search strategy
Solver s = model.getSolver();
s.limitTime(TIME_LIMIT+"s");
if(mznSearch) {
// use search strategy given in the minizinc model (first fail)
s.setSearch(Search.minDomLBSearch(vars));
}else{
// use activity-based search (classical black box search)
s.setSearch(Search.activityBasedSearch(vars));
}
return model;
}
}
%%%%%%%%%%%%%%%%%%%%%%%%%%
Solving GridColouring 10_5
%%%%%%%%%%%%%%%%%%%%%%%%%%
Single thread using model search (first fail)
Solution found (objective = 5)
Solution found (objective = 4)
30s timeout reached
%%%%%%%%%%%%%%%%%%%%%%%%%%
Single thread using Activity Based Search
Solution found (objective = 5)
Solution found (objective = 4)
Solution found (objective = 3)
30s timeout reached
%%%%%%%%%%%%%%%%%%%%%%%%%%
Portfolio using both model search and Activity Based Search
Solution found (objective = 5)
Solution found (objective = 4)
Solution found (objective = 3)
Optimality proved in 2s
%%%%%%%%%%%%%%%%%%%%%%%%%%
On observe donc qu'avec l'heuristique fournie dans le modèle (plus petit domaine et plus petite valeur, parfois appelée first fail), on ne parvient pas à la solution optimale dans le temps imparti. Avec l'heuristique Activity Based Search (ABS), une heuristique boite noire classique, on parvient à la trouver mais sans pour autant réussir à prouver qu'elle est optimale. En combinant les deux heuristiques, on pourrait s'attendre à obtenir des performances similaires à ABS qui semble mieux s'en sortir que first fail, avec un léger retard. En pratique, le portfolio parvient à trouver et prouver l'optimalité en quelques secondes. C'est nettement mieux que chacune des deux approches précédentes.