" /> My Constraint Programming Blog: September 2011 Archives

« August 2011 | Main | October 2011 »

September 21, 2011

G12 MiniZinc version 1.4 released

G12 MiniZinc version 1.4 has been released. Download it here.

From the NEWS:
G12 MiniZinc Distribution 1.4
-----------------------------
Changes to the MiniZinc language:

* Input files are now encoded in UTF-8.

* A new built-in function, is_fixed/1, can be used to test whether a value is known to be fixed at flattening time.

* Two new built-in functions, iffall/1 and xorall/1, can be used to perform n-ary xor operations on arrays of Booleans. They are defined as follows:

iffall([a1, a2, ..., aN]) <=> a1 xor a2 xor ... xor aN xor true

xorall([a1, a2, ..., aN]) <=> a1 xor a2 xor ... xor aN xor false


Changes to the FlatZinc language:

* Variable and parameter names may now be optionally prefixed with one or more leading underscore. For example, the following are now valid FlatZinc variable names:

_A
__B
___D

The rationale for this change is to provide a way for mzn2fzn to name introduced variables in a way that is guaranteed not to clash with the variable and parameter names from the MiniZinc model.

Names for predicates, predicate parameters and annotations cannot have leading underscores.

* A new FlatZinc builtin has been added: array_bool_xor/1.


Changes to the MiniZinc evaluation driver:

* A new command line option, --random-seed, can be used to specify a seed for the FlatZinc implementation's random number generator. (The options -r and --seed are synonyms for this option.)

The evaluation driver will invoke FlatZinc implementations with the -r option if it is invoked with --random-seed. (See the description of the FlatZinc command line interface in the minizinc(1) manual page for details.)


Changes to the G12 FlatZinc interpreter:

* There is now a domain consistent version of the alldifferent/1 constraint for G12/FD. (The domain consistent version is selected by annotating the constraint with the domain/0 annotation.)

* The --random-seed (-r) command line option described above is now supported by the interpreter.


Other changes in this release:

* The global constraints value_precede/3 and value_precede_chain/2 have been added to the MiniZinc globals library. The existing precedence/1 global constraint has been deprecated in favour of these.

* The problems from the 2011 MiniZinc challenge are now included in the MiniZinc benchmark suite.


Bugs fixed in this release:

* A bug in G12/FD's cumulative/4 global constraint that caused poor runtime performance when (extended) edge finding filtering was enabled has been fixed. [Bug #221]

* A bug that caused mzn2fzn to abort instead of printing an error message if a variable had the same name as a built-in function has been fixed. [Bug #231]

* A bug that caused an abort in flatzinc's LazyFD backend if there was an application of the built-in int_lin_le_reif/4 constraint with a zero coefficient has been fixed. [Bug #232]

* A bug that caused mzn2fzn and solns2out to abort when processing array literals whose elements were all empty set literals has been fixed. [Bug #256]

* mzn2fzn and solns2out no longer abort on array5d and array6d expressions. [Bug #259]

* The incorrect default definition of the int_set_channel/2 global constraint has been fixed. [Bug #255]

* A bug that caused mzn2fzn to use the wrong predicate name when flattening an application of a bodyless reified predicate definition has been fixed.

* The incorrect default decomposition of the roots/3 global constraint has been fixed.

* mzn2fzn and solns2out no longer abort if they encounter an arrayNd cast containing an empty array of decision variables.

* A bug that caused mzn2fzn to abort if a model contained an array lookup where the array expression was a literal containing only anonymous variables has been fixed. [Bug #68]

* A bug that caused reified var array lookups to be incorrectly flattened has been fixed. [Bug #244]

* Assignments to annotation variables are no longer emitted in MiniZinc output specifications. [Bug #269]

* solns2out now prints trailing comments in the solution stream if search terminates before it is complete. [Bug #270]

* A bug that caused a stack overflow in solns2out has been fixed. [Bug #272]

* A bug that caused a stack overflow in mzn2fzn on Windows systems has been fixed. [Bug #228]

September 13, 2011

MiniZinc Challenge 2011 Results

The results of the MiniZinc Challenge 2011 has been published.

From the result page:
The entrants for this year (with their descriptions, when provided):

BProlog. A CLP(FD) solver.
Bumblebee. Translates to SAT, uses CryptoMiniSAT.
Gecode. A C++ FD solver.
JaCoP. A Java FD solver.
Fzn2smt . Translates to SMT, uses Yices.
SCIP. A CP/MIP solver.

In addition, the challenge organisers entered the following FlatZinc implementations:

Chuffed. A C++ FD solver using Lazy clause generation.
CPX. A C++ FD Solver using Lazy Clause Generation.
G12/FD. A Mercury FD solver (the G12 FlatZinc interpreter's default solver).
G12/LazyFD. A Mercury FD solver using Lazy Clause Generation.
G12/CBC. Translates to MIP, uses Cbc version 2.6.2.
G12/CPLEX. Translates to MIP, uses CPLEX version 12.1
. G12/Gurobi. Translates to MIP, uses Gurobi Optimizer version 4.5.

As per the challenge rules, these entries are not eligible for prizes, but do modify the scoring results. Furthermore, entries in the FD search category (BProlog, Gecode, JaCoP, Chuffed, CPX and G12/FD) were automatically included in the free search category, while entries in the free search category (Bumblebee, Fzn2smt, SCIP, CBC, CPLEX, Gurobi and promoted FD entries) were automatically included in the parallel search category.
The slides for the presentation of the results at CP2011 are here (PDF).

Summary of results

The results for the MiniZinc Challenge 2011 were

Fixed search:
* Gold medal: Gecode
* Silver medal: JaCoP
* Bronze medal: BProlog

Free search:
* Gold medal: Gecode
* Silver medal: fzn2smt
* Bronze medal: JaCoP

Parallel search:
* Gold medal: Gecode
* Silver medal: fzn2smt
* Bronze medal: JaCoP

Congratulations to all!

As in the MiniZinc Challenge 2010, the Chuffed solver did very well on the benchmarks (though not eligible for a price). More details in presentation and the result page (where the models and data instances are shown).

September 09, 2011

Summary of new developments in Google or-tools

Laurent Perron wrote the following summary of the developments in Google or-tools:
Here is what we have been doing in Q3.

Graph algorithms:
- a lot of work went into making the algorithms (min cost flow, max flow) incremental after small modifications.

Linear solver:
- Added utility of constraints, primal and dual tolerances.
- Basis status of variables.
- Added solving model from protobuf, outputting solutions as protobuf. Useful for having MP solvers in another process or machine for instance.

Constraint solver:
- Added complete model visitor
- Applications to pretty print the model or display special stats
- Main application is to implement model read/write to file. I will send another message to detail all this.
- Added model_util binary to query/test/modify exported models.
- Change the internal way of storing constraints and expressions in caches to avoid duplicating equivalent classes.
- Lots of cleanup for the reference manual. Size has been divided by nearly 4 by hiding all implementation classes: check http://or-tools.googlecode.com/svn/doc/full_reference_manual/or-tools/index.html

And of course the usual batch of bug fixes.

--Laurent (on behalf of the complete Operations Research team at Google).