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}
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:
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.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.
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 :
public void propagate(int evtmask) throws ContradictionException : cette méthode tente de forcer la valuation de variables afin de trouver une solution. Elle est appelée à chaque itération de l'heuristique de branchement. Si cette méthode ne force pas l'état d'une variable ou ne retourne pas de ContradictionException, il est nécessaire de continuer à appliquer la stratégie de branchement. Dans le cas où une ContradictionException est levée, Choco Solver apprend de cette contradiction, et tente un nouveau branchement.
public ESat isEntailed() : cette méthode vérifie si la contrainte est satisfaite en analysant l'état des variables sur lesquelles elle porte. Trois cas sont possibles : ESat.TRUE (la contrainte est satisfaite), ESat.FALSE (la contrainte n'est pas satisfaite) ou ESat.UNDEFINED (il n'est pas possible de statuer sur la satisfaction de la contrainte).
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}