Choco Solver



Approches Portfolio avec Choco Solver 4.0


Résolution parallèle avec communication de bornes

Nous allons maintenant illustrer la résolution parallèle avec l'objet ParallelPortfolio.

L'idée est de créer plusieurs modèles identiques d'un point de vue sémantique, mais avec des configurations différentes (heuristique de recherche, algorithmes de filtrage, explications, etc.). Ces différents modèles sont ensuite donné à un portfolio de solveurs qui va orchestrer la résolution en les exécutant simultanément en parallèle et en communiquant à chaque solution trouvée la valeur objectif aux différents solveurs afin qu'ils puissent profiter de cette information.

Nous prenons l'exemple d'un problème de coloration de grille. Dans cet exemple, nous comparons l'exécution d'un modèle avec deux heuristiques au choix et l'exécution d'un portfolio embarquant deux modèles, un pour chacune de ces heuristiques.

Modèle:

            
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)
 */
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;
    }
}
            
        

Sortie console:

            
%%%%%%%%%%%%%%%%%%%%%%%%%%
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
%%%%%%%%%%%%%%%%%%%%%%%%%%
            
        

Un travail d'équipe

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.

Comment expliquer cet écart?
En fait, les deux solveurs embarqués dans le portfolio vont s'aider mutuellement, pendant la recherche. Plus précisément, l'heuristique ABS va permettre de vite TROUVER la solution optimale, tandis que l'autre heuristique va permettre de vite PROUVER que cette solution est effectivement optimale. En d'autres termes, ces modèles sont complémentaires et forment ensemble une approche efficace. En contraintes comme dans la vie, on travaille mieux en équipe.