Choco Solver



Set problems in Choco Solver 4.0


Create set variables

Through this tutorial, we will partition a set (the universe) in three smaller sets x, y, z.

First, we will see how to solve this problem. Then, we will se how to optimize the resolution by applying a custom search strategy.

            
import org.chocosolver.solver.Model;
import org.chocosolver.solver.Solver;
import org.chocosolver.solver.variables.SetVar;


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());
        }
    }
}
            
        

The execution of main() outputs the following result :

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


Creating a custom search strategy


We will now modify the Choco Solver search strategy by giving it a new heuristic. The search relies on two subsequent steps :

  1. Selecting a set : among the SetVar x, y and z, we select the item that we will next focus on. The cardinal of its upper bound must be strictly superior than its lower bound. If such a set does not exists in the array, we return null to tell that the heuristic is finished.
  2. Selecting a variable : then, we want to add to the SetVar lower bound an integer of its upper bound.
            
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
            (VariableSelector<SetVar>) variables -> {
                int max = Integer.MIN_VALUE;
                SetVar var = null;
                for(SetVar sv : variables) {
                    int diff = sv.getUB().getSize() - sv.getLB().getSize();
                    // 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
            (SetValueSelector) 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().contain(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().getSize() - sv.getLB().getSize();
                    // 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().contain(i) && i < min) {
                        min = i;
                    }
                }
                return min;
            }
        },
        true, x, y, z)
    );
    // [...]
}
            
        

The execution of main() now outputs the following results :

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

The result is not the same as the previous part because the heuristic is not the same. However, the solution set is the same (only the order in which they are explored is different).



Creating a custom constraint


Let's add a new constraint to our partition : one of the sets of must now be empty. To do this, we extend org.chocosolver.solver.constraints.Propagator. Two methods are required to implement it :

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


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;
    }
}

            
        

It is now possible to post this custom constraint before the solve() call :

            
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();

    // [...]
}

            
        

The execution of main() now outputs the following result :

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