/*
* 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());
}
}
}
La ejecución del método main() da el resultado siguiente:
Partition found!
{1, 2, 3, 5, 7, 8} = {1, 3, 8} + {7} + {2, 5}
Vamos ahora a intentar influir en la estrategia de búsqueda de Choco Solver proporcionándole una heurística. La búsqueda se basa en dos etapas consecutivas:
SetVar x, y y z, seleccionamos aquella sobre la cual vamos a concentrar nuestras búsquedas. El cardinal de la cota superior de este conjunto debe ser estrictamente superior al de su cota inferior. Si tal conjunto no está presente en el array, devolvemos null para decir que la heurística ha terminado: o bien la solución ha sido encontrada, o bien pasamos a la siguiente heurística.SetVar un entero de su cota superior.
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)
);
// [...]
}
La ejecución del método main() devuelve esta vez el resultado siguiente:
Partition found!
{1, 2, 3, 5, 7, 8} = {1, 8} + {7} + {2, 3, 5}
El resultado no es el mismo que en la parte precedente, porque la heurística de búsqueda ya no es la misma. Sin embargo, los dos resultados satisfacen las restricciones dadas al solucionador. Solicitando la totalidad de las soluciones al problema (reemplazar el if por un while), el resultado habría sido el mismo, en un orden diferente.
Añadamos ahora una nueva restricción a nuestra partición: uno de los conjuntos de esta partición debe ahora estar vacío.
Para esto, extendemos la clase org.chocosolver.solver.constraints.Propagator. Dos métodos son necesarios para su implementación:
public void propagate(int evtmask) throws ContradictionException : este método intenta forzar la valuación de variables para encontrar una solución. Se llama en cada iteración de la heurística de ramificación. Si este método no fuerza el estado de una variable o no devuelve una ContradictionException, es necesario continuar aplicando la estrategia de ramificación. En el caso en que se lance una ContradictionException, Choco Solver aprende de esta contradicción, e intenta una nueva ramificación.
public ESat isEntailed() : este método verifica si la restricción se satisface analizando el estado de las variables sobre las cuales recae. Tres casos son posibles: ESat.TRUE (la restricción se satisface), ESat.FALSE (la restricción no se satisface) o ESat.UNDEFINED (no es posible pronunciarse sobre la satisfacción de la restricción).
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;
}
}
Sólo queda publicar esta restricción personalizada antes de la llamada a 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();
// [...]
}
La ejecución del método main() da entonces el resultado siguiente:
Partition found!
{1, 2, 3, 5, 7, 8} = {1, 3, 8} + {} + {2, 5, 7}