/*
* 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
%%%%%%%%%%%%%%%%%%%%%%%%%%
Se observa por tanto que con la heurística proporcionada en el modelo (dominio más pequeño y valor más pequeño, a veces llamada first fail), no se llega a la solución óptima en el tiempo asignado. Con la heurística Activity Based Search (ABS), una heurística caja negra clásica, se consigue encontrarla pero sin lograr probar que es óptima. Combinando las dos heurísticas, podríamos esperar obtener prestaciones similares a ABS que parece desenvolverse mejor que first fail, con un ligero retraso. En la práctica, el portfolio consigue encontrar y probar la optimalidad en algunos segundos. Es claramente mejor que cada uno de los dos enfoques precedentes.