Through this tutorial, we will partition a set (the universe) in three smaller sets x, y, z.
First, we solve this problem with default search of Choco Solver. Then, we apply a custom search strategy.
/*
* 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());
}
}
}
The execution of main() outputs the following result :
Partition found!
{1, 2, 3, 5, 7, 8} = {1, 3, 8} + {7} + {2, 5}
We will now modify the Choco Solver search strategy by giving it a new heuristic. The search relies on two subsequent steps :
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.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.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)
);
// [...]
}
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 solutions are the same (only the order in which they are explored is different).
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 :
public void propagate(int evtmask) throws ContradictionException : this method tries to force the values of the variables in order to find a solution. It's called at each iteration of the branching heuristic. If the method does not force the value of a variable or does throws ContradictionException, the branching strategy must be pursued at a higher level of the branching tree. If a ContradictionException is thrown, Choco Solver learns it and tries a new branch.
public ESat isEntailed() : this method checks whether the constraint can be satisfied or not by analysing the valuation of each variable. Three cases are psosible : ESat.TRUE (the constraint is satisfied), ESat.FALSE (the constraint cannot be satisfied), and ESat.UNDEFINED (we can't say nothing about the constraint's satisfaction)
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;
}
}
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}