Circulations and Flows in Learning Constraint Solvers

Nicholas Downing, Thibaut Feydy, Peter J. Stuckey

We give here the models (*.mzn) and instances (*.dzn) and all necessary support files to duplicate the experiments from the paper.

At top level: The files task_*_pre.txt give the command lines to the flattener (mzn2fzn version 1.6) and remaining task_*.txt the command lines to the solvers. These task files are generated by scripts/task_*.sh. There are also inst_*.txt and cols_*.txt which give the labels to each row and column of the tables in the paper and assist in the generation of the task files.

In the directories for each experiment, being car_sequence, etp, nurse_nina, personnel, social_golfer, there is a *.mzn.template file which contains the basic model annotated with optional sections to enable features like the circulation propagator or the decompositions of model constraints. The script m.sh generates all the *-*.mzn versions of these. The script n.sh generates all the *.dzn files for the given experiment, which are processed into Minizinc format from various sources. The *.mzn and *.dzn files are available directly from here, we just include the generator scripts for explanatory purposes.

The mzn directory contains some additional Minizinc files defining decompositions we use other than from the Minizinc library.

Support scripts for the NICTA cluster are seen in scripts/job.sh and scripts/sub.sh. We post process the results with some slight customizations for each experiment using scripts/data_*.sh which does the following:

• Extracts relevant features from any new solver output using grep and summarizes them into data_*.txt which we retain for our records and which can be seen here.
• Runs the analyzer scripts/data.py which understands the output format of each solver and extracts the data points using regular expressions, generating a solver-independent output data_*.csv with four columns per solver, being status, runtime, conflict count and optimal objective.
• Runs the table generator scripts/summary.py which extracts the relevant column (time or conflict count in these experiments) and formats them into a table time_*.csv or count_*.csv, with one column per solver (for ease of comparison between solvers), and with geometric means, etc, in the last line.
• Runs a lightweight scripts/csv_to_tex.sed converter.

For the comparison with Palm we checked out the code from svn://svn.code.sf.net/p/choco/code/trunk/choco-old_version/src/main/java revision 1194 (it is removed in later revisions after an effort at integration with a more recent Choco version — which does not compile), and applied the changes in palm.patch. These were quite extensive and involved adding missing code, fixing bugs, instrumenting for time and failure count, and adding graceful termination checks. See social_golfer/SocialGolfer.java for the driver we created to invoke this modified Choco package.

The comparisons with Chuffed and JaCoP were much easier as they are more modern and support a Minizinc front end, we just changed a few compile time constants in JaCoP to control their explicit arc testing algorithm.