Choco Solver



Problèmes ensemblistes dans Choco Solver 4.0


Création de variables ensemblistes

Au cours de ce tutoriel, on désire partitionner un ensemble (univers) en trois ensembles disjoints x, y, et z.

Nous aborderons d'abord la résolution du problème, puis l'élaboration de stratégies de recherche alternatives, permettant d'optimiser la résolution du problème.

            
/*
 * 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.Solver;
import org.chocosolver.solver.variables.SetVar;

/**
 * Simple Choco Solver example involving set variables
 * @author Jean-Guillaume FAGES (cosling)
 * @version choco-solver-4.0.4
 */
public class Partition {

    public static void main(String[] args) {
        // Create the model
        Model model = new Model();

        // partitions a set "universe" into three disjoint sets x, y and z
        // declare a constant set variable (LB = UB = {1, 2, 3, 5, 7, 8})
        SetVar universe = model.setVar("universe", 1, 2, 3, 5, 7, 8);

        // x initial domain
        // integers that MAY belong to A solution
        int[] x_UB = new int[]{1, 3, 2, 8};
        // integers that MUST belong to EVERY solution
        int[] x_LB = new int[]{1};
        // create a set variable x
        SetVar x = model.setVar("x", x_LB, x_UB);
        // same for set variable y and z
        SetVar y = model.setVar("y", new int[]{}, new int[]{2, 6, 7});
        SetVar z = model.setVar("z", new int[]{2}, new int[]{2, 1, 3, 5, 7, 12});

        // partition constraint : union(x,y,z) = universe and all_disjoint(x,y,z)
        model.partition(new SetVar[]{x, y, z}, universe).post();

        // find one partition
        if(model.getSolver().solve()){
            System.out.println("Partition found!");
            System.out.println(universe.getValue()+" = "+x.getValue()+" + "+y.getValue()+" + "+z.getValue());
        }
    }
}
            
        

L'exécution de la méthode main() donne le résultat suivant :

            
                Partition found!
                {1, 2, 3, 5, 7, 8} = {1, 3, 8} + {7} + {2, 5}
            
        


Création d'une stratégie de recherche personnalisée


Nous allons maintenant essayer d'influer sur la stratégie de recherche de Choco Solver en lui fournissant une heuristique. La recherche se base sur deux étapes consécutives:

  1. Sélection de l'ensemble : parmi les trois SetVar x, y et z, nous sélectionnons celui sur lequel nous allons concentrer nos recherches. Le cardinal de la borne supérieure de cet ensemble doit être strictement supérieur à celui de sa borne inférieure. Si un tel ensemble n'est pas présent dans le tableau, nous retournons null pour dire que l'heuristique est terminée : soit la solution est trouvée, soit on passe à l'heuristique suivante.
  2. Sélection d'une variable : nous cherchons ensuite à ajouter à la borne inférieure de notre SetVar un entier de sa borne supérieure.
            
import org.chocosolver.solver.Model;
import org.chocosolver.solver.Solver;
import org.chocosolver.solver.search.strategy.Search;
import org.chocosolver.solver.variables.SetVar;


public static void main(String[] args){
    // [...]
    // model.partition(new SetVar[]{x, y, z}, universe).post();

    // we specify a custom heuristic to the solver to change its search strategy
    Solver s = model.getSolver();
    s.setSearch(Search.setVarSearch(
            // find a set where card(ub) - card(lb) > 0
            variables -> {
                int max = Integer.MIN_VALUE;
                SetVar var = null;
                for(SetVar sv : variables) {
                    int diff = sv.getUB().size() - sv.getLB().size();
                    // In this simple heuristic, we take the set having a maximal card(up) - card(lb)
                    if (max < diff && diff >= 1) {
                        max = diff;
                        var = sv;
                    }
                }
                // null if no set where card(ub) - card(lb) is remaining
                return var;
            },
            // find an integer of the upper bound to add to the lower bound
            variable -> {
                // In this heuristic, we take the minimum integer of the set upper bound that is not in the lower bound yet
                int min = Integer.MAX_VALUE;
                for(int i : variable.getUB()) {
                    if(!variable.getLB().contains(i) && i < min) {
                        min = i;
                    }
                }
                return min;
            }
            , true, x, y, z)
        );

    // [...]
}
            
        
            
import org.chocosolver.solver.Model;
import org.chocosolver.solver.Solver;
import org.chocosolver.solver.search.strategy.Search;
import org.chocosolver.solver.search.strategy.selectors.values.SetValueSelector;
import org.chocosolver.solver.search.strategy.selectors.variables.VariableSelector;
import org.chocosolver.solver.variables.SetVar;


public static void main(String[] args){
    // [...]
    // model.partition(new SetVar[]{x, y, z}, universe).post();

    // we specify a custom heuristic to the solver to change its search strategy
    Solver s = model.getSolver();
    s.setSearch(Search.setVarSearch(
        // find a set where card(ub) - card(lb) > 0
        new VariableSelector<SetVar>() {
            @Override
            public SetVar getVariable(SetVar[] variables) {
                int max = Integer.MIN_VALUE;
                SetVar var = null;
                for (SetVar sv : variables) {
                    int diff = sv.getUB().size() - sv.getLB().size();
                    // In this simple heuristic, we take the set having a maximal card(up) - card(lb)
                    if (max < diff && diff >= 1) {
                        max = diff;
                        var = sv;
                    }
                }
                // null if no set where card(ub) - card(lb) is remaining
                return var;
            }
        },
        // find a value from the SetVar which we can add to the lower bound
        new SetValueSelector() {
            @Override
            public int selectValue(SetVar v) {
                // In this heuristic, we take the minimum integer of the set upper bound that is not in the lower bound yet
                int min = Integer.MAX_VALUE;
                for(int i : v.getUB()) {
                    if(!v.getLB().contains(i) && i < min) {
                        min = i;
                    }
                }
                return min;
            }
        },
        true, x, y, z)
    );
    // [...]
}
            
        

L'exécution de la méthode main() retourne cette fois le résultat suivant :

            
                Partition found!
                {1, 2, 3, 5, 7, 8} = {1, 8} + {7} + {2, 3, 5}
            
        

Le résultat n'est pas le même que dans la partie précédente, car l'heuristique de recherche n'est plus la même. Cependant, les deux résultats satisfont les contraintes données au solveur. En demandant la totalité des solutions au problème (remplacer le if par un while), le résultat aurait été le même, dans un ordre différent.



Création d'une contrainte personnalisée


Ajoutons maintenant une nouvelle contrainte à notre partition : l'un des ensembles de cette partition doit désormais être vide.
Pour ceci, nous étendons la classe org.chocosolver.solver.constraints.Propagator. Deux méthodes sont nécessaires à son implémentation :

            
import org.chocosolver.solver.constraints.Propagator;
import org.chocosolver.solver.exception.ContradictionException;
import org.chocosolver.solver.variables.SetVar;
import org.chocosolver.util.ESat;

/**
 * Simple Choco Solver propagator to ensure that at most one set variable is empty
 * @author Jean-Guillaume FAGES (cosling)
 * @version choco-solver-4.0.4
 */
public class PropAtLeastOneEmptySet extends Propagator<SetVar> {

    public PropAtLeastOneEmptySet(SetVar... vars) {
        super(vars);
    }

    @Override
    public void propagate(int evtmask) throws ContradictionException {
        SetVar toEmpty = null;
        for (SetVar var : vars) {
            if (var.getUB().isEmpty()) {
                // the constraint is always satisfied, no matter what happens next
                // setPassive() avoids the Propagator to be called next time
                setPassive();
                return;
            } else {
                // if the lower bound is empty, that set COULD be empty
                if (var.getLB().isEmpty()) {
                    if (toEmpty == null) {
                    toEmpty = var;
                    } else {
                        // two variables probably empty -> we can't know which one must be empty
                        return;
                    }
                }
            }
        }
        if (toEmpty != null) {
            // We remove all the elements from the upper bound to make this SetVar empty
            for (int v : toEmpty.getUB()) {
                toEmpty.remove(v,this);
            }
        } else {
            // the constraint cannot be satisfied if all the sets can't be empty
            fails();
        }
    }

    @Override
    public ESat isEntailed() {
        // number of non empty sets
        int nbNE = 0;
        for (SetVar var : vars) {
            // if this set is instantiated and has no element, it is empty
            if (var.getUB().isEmpty()) {
                return ESat.TRUE;
            }
            // if the lower bound of the variable is not empty, the SetVar can't be empty
            if (!var.getLB().isEmpty()) {
                nbNE++;
            }
        }
        // If ALL the SetVars cannot be empty, the constraint cannot be satisfied
        if (nbNE == vars.length) {
            return  ESat.FALSE;
        }
        // Otherwise we cannot state about the satisfaction
        return ESat.UNDEFINED;
    }
}

            
        

Il ne reste plus qu'à poster cette contrainte personnalisée avant l'appel à solve():

            
import org.chocosolver.solver.Model;
import org.chocosolver.solver.Solver;
import org.chocosolver.solver.search.strategy.selectors.SetValueSelector;
import org.chocosolver.solver.search.strategy.selectors.VariableSelector;
import org.chocosolver.solver.variables.SetVar;


public static void main(String[] args){
    // [...]
    SetVar[] vars = new SetVar[]{x, y, z};
    model.partition(vars, universe).post();

    new Constraint("AtLeastOneEmptySet", new PropAtLeastOneEmptySet(vars)).post();

    // [...]
}

            
        

L'exécution de la méthode main() donne alors le résultat suivant :

            
                Partition found!
                {1, 2, 3, 5, 7, 8} = {1, 3, 8} + {} + {2, 5, 7}