V 213

Charles Prud'homme - Oct. 07th 2011

A new release with minor changes is now avalaible.

Main changes are:

If you have any suggestions, please let us know.

Refactoring

Charles Prud'homme - July 07th 2011

We are currently working on the new version of Choco, version 3.

This includes separation in modules of Model and Solver, restructuration of constraints, etc. But the main goal is to refactor of the propagation engine.

During this summer, we are going to prepare the new version, in three steps:

If you have any suggestions, please let us know.

New constraints

Narendra Jussien, Thierry Petit - June 28th 2011

We recently added two constraints to CHOCO.

increasingSum(IntegerVariable[] x, IntegerVariable s): Given a sequence of variables X = x0, x1, . . . , xn-1, the increasingSum constraint imposes that ∀ i ∈ [0, n-2], xi ≤ xi+1 and xi ∈ X xi = s, build on an O(n) bound-consistency algorithm.

inverseChannelingWithinRange(IntegerVariable[] x, IntegerVariable[] y): derived from inverseChanneling(x, y), "If the i^th variable of the collection X is assigned to j and if j is less than or equal to the number of items of the collection Y then the j^th variable of the collection Y is assigned to i. Conversely, if the j^th variable of the collection Y is assigned to i and if i is less than or equal to the number of items of the collection X then the ith variable of the collection X is assigned to j." See inverse_within_range.

CNF: boolean formulas framework

Charles Prud'homme - December 23th 2010

The actual way to define boolean formulas was a little bit obscure to us. That's why we have added a small framework, in the Model part of CHOCO, to help declaration of clauses. It is composed of 2 main objects: Literal and Node, each is an extension of ALogicTree abstract object.

A literal is an atomic formula, or its negation, build with a bolean variable.

A node is a formula build with a literals or nodes. Existing operators are: AND, IFONLYIF, IFTHENELSE, REIFIED, IMPLIES, OR, NAND, NOR, XOR.

One can add a formula to a Model object, using the Choco.clauses() API, which converts the current formula into CNF, a conjunction of clauses readable by the model. Using this framework and reification is a robust way to modelize problems.

Here is an example code of the SendMoreMoney problem with logging statements

CPModel mod = new CPModel();
CPSolver s = new CPSolver();
IntegerVariable b = Choco.makeBooleanVar("to be");
mod.addVariable(b);

ALogicTree or = Node.or(Literal.pos(b), Literal.neg(b));

mod.addConstraints(clauses(or));
s.read(mod);
s.solveAll();
                

CP-VIZ: An Open Source Visualization Platform for CP

Charles Prud'homme - December 13th 2010

We currently have the pleasure to welcome Helmut Simonis at Ecole des Mines. As part of the collaboration, the old OADymPAC-based tracer module has been replaced by a brand new one: CPVisu tracer. CPVisu allows the production of three data files: the tree search, the states of constraints and variables at different points of computations, and a configuration file. These files can be interpreted using the cpviz java library for post-mortem analysis.
As for now, the tree search data file is available and can be exploited. Most of the declared states of constraints and variables are defined and can be used safely (some few are missing).
The CPVisu tracer module uses AOP (Aspect-Oriented Programming), weaves the choco-solver class files to produce a modified JAR for logging. Thus, you need to add the followin jars to your classpath: AspectJ andLogback.

Here is an example code of the SendMoreMoney problem with logging statements

Model model;
IntegerVariable S, E, N, D, M, O, R, Y;
IntegerVariable[] SEND, MORE, MONEY;

model = new CPModel();

S = makeIntVar("S", 0, 9);
E = makeIntVar("E", 0, 9);
N = makeIntVar("N", 0, 9);
D = makeIntVar("D", 0, 9);
M = makeIntVar("M", 0, 9);
O = makeIntVar("0", 0, 9);
R = makeIntVar("R", 0, 9);
Y = makeIntVar("Y", 0, 9);
SEND = new IntegerVariable[]{S, E, N, D};
MORE = new IntegerVariable[]{M, O, R, E};
MONEY = new IntegerVariable[]{M, O, N, E, Y};

model.addConstraints(neq(S, 0), neq(M, 0));
model.addConstraint(allDifferent(S, E, N, D, M, O, R, Y));
model.addConstraints(
eq(plus(scalar(new int[]{1000, 100, 10, 1}, SEND),
scalar(new int[]{1000, 100, 10, 1}, MORE)),
scalar(new int[]{10000, 1000, 100, 10, 1}, MONEY))
);

Solver solver = new CPSolver();
solver.read(model);

// Creation of the visualization wrapper
Visualization visu = new Visualization("SendMoreMoney", solver, "./out");

visu.createTree(); // declare tree tool
visu.createViz(); // declare viz tool

// declare of specialized visualizer for variables states
Vector visualizer = new Vector(solver.getVar(S,E,N,D,M,O,R,Y), "expanded", 0, 0, 8, 10, "SENDMORY",
0, 9);

// add the vector visualizer to the viz tool
visu.addVisualizer(visualizer);

solver.solve();

// close the XML files safely
visu.close();