Yuck

Yuck in a nutshell

• Yuck is a FlatZinc interpreter that integrates with the MiniZinc toolchain.
• Yuck's approach to problem solving is based in local search.
• Yuck implements Boolean, integer, and integer set variables, see FlatZinc support.
• Yuck implements many global constraints and their reified counterparts, see Global constraints.
• Yuck comes with support for vehicle routing, see Extending Yuck for Vehicle Routing.
• Yuck features a mechanism to turn Boolean MiniZinc expressions (including applications of global constraints) into soft constraints, see bool2costs.
• Yuck supports lexicographic multi-objective optimization, see Goal hierarchies.
• Yuck supports warm starting.
• Yuck is provided under the terms of the Mozilla Public License 2.0.
• Yuck has won several silver and gold medals at the MiniZinc Challenge.

Contact

When you are using Yuck or you are considering to use it, and you have a question, want to report an issue, request a feature, share a success story, give feedback, or even get involved in development, then there are two ways to get into contact: Either raise an issue on the Yuck issue tracker or send an email to yuck-solver@freenet.de.

Download and installation

Yuck packages are available from the Releases page; there are a Debian package (suitable for all Debian based systems, including Ubuntu and its offspring) and a ZIP package (suitable for all other systems). Moreover, a Docker image is available from DockerHub.

When you installed the Debian package, you are already good to go; the package registers Yuck as a backend for the MiniZinc toolchain and no further manual setup is required.

When you decided for the ZIP package, proceed as follows:

1. Make sure that a Java runtime environment is available on your system; Yuck requires at least version 11.
2. Unzip the package in a suitable location.
3. To register Yuck as a backend for the MiniZinc toolchain, define the MZN_SOLVER_PATH environment variable to point to the mzn subfolder of the Yuck distribution. (For other ways of providing a solver configuration file to the MiniZinc toolchain, see the section on Solver Configuration Files of The MiniZinc Handbook.)
4. If you want to use Yuck on MacOS, you have to install the coreutils package with the following Homebrew command: brew install coreutils

The Docker image contains an OpenJDK Java runtime, the MiniZinc compiler and Yuck itself; it neither contains the MiniZinc IDE nor other solvers.

Usage as MiniZinc backend

To apply Yuck to MiniZinc models, you need a working MiniZinc installation. This section assumes that you have at least version 2.9.3 installed and that Yuck has been properly registered as a MiniZinc backend (see above).

To use Yuck from inside the MiniZinc IDE, just select it from the menu of solver configurations before running your model.

To run MiniZinc models from the command line, use minizinc as follows:

minizinc --solver yuck zebra.mzn

zebra:
nation = [3, 4, 2, 1, 5]
colour = [3, 5, 4, 1, 2]
animal = [4, 1, 2, 5, 3]
drink  = [5, 2, 3, 4, 1]
smoke  = [3, 1, 2, 4, 5]
----------

Direct usage

To use Yuck directly, invoke it with the FlatZinc file on the command line, for example:

yuck zebra.fzn

animal = array1d(0..4, [4, 1, 2, 5, 3]);
colour = array1d(0..4, [3, 5, 4, 1, 2]);
drink = array1d(0..4, [5, 2, 3, 4, 1]);
nation = array1d(0..4, [3, 4, 2, 1, 5]);
smoke = array1d(0..4, [3, 1, 2, 4, 5]);
----------

Yuck's output complies to the requirements of the FlatZinc 1.6 specification (see section 6).

Use the --help option to obtain a list of all options.

In case you need Yuck's MiniZinc library, its location depends on how you installed Yuck:

• When you installed the Debian package, the library resides in /usr/share/yuck/mzn/lib.
• When you installed the universal package, the library resides in the mzn/lib subfolder of the Yuck distribution.

Using the Docker image

Say your home folder contains the directory workspace with the file zebra.mzn in it. To solve this problem by means of the Docker image, use the following command:

docker run -ti -v ~/workspace:/problems informarte/yuck:latest minizinc --solver yuck /problems/zebra.mzn

Setting the maximum heap size

The maximum heap size defaults to 2 GB.

To increase the maximum heap size to, say, 4GB, use the Java command line option -Xmx as follows:

env JAVA_OPTS=-Xmx4g minizinc --solver yuck zebra.mzn

or

env JAVA_OPTS=-Xmx4g yuck zebra.fzn

Under the hood

• Yuck's approach to problem solving is comparable to Comet [HM05] and OscaR/CBLS [BMFP15].
• Yuck implements simulated annealing along with some basic annealing schedules and some schedule combinators.
• Yuck implements a generalized version of the Feasibility Jump heuristic (inspired by [DDL24]).
• Yuck supports lexicographic cost functions with both minimization and maximization goals.
• Yuck allows to timebox and parallelize solvers by means of solver combinators.
• Yuck allows solvers to share bounds on the objective value.
• Yuck supports the interruption and the resumption of solvers to facilitate the presentation of intermediate results.
• Yuck supports implicit solving by means of constraint-specific neighbourhoods.
• Yuck is written in Scala and exploits the Scala library's immutable collection classes for implementing global constraints.

FlatZinc support

Yuck's FlatZinc front end supports all of FlatZinc except for float variables and float constraints.

Integers in Yuck are 64 bits wide.

Integer domains are represented as ranges or range lists.

If all integer-set variables are constrained to take their values from the powerset of [0, 63], values of integer-set variables are represented as 64-bit integers, otherwise they are represented as ranges or range lists.

When used as a FlatZinc interpreter, Yuck proceeds as follows:

• It eliminates variables by exploiting equality constraints.
• It identifies and exploits functional dependencies to reduce the number of decision variables.
• It prunes the search space by performing a limited amount of constraint propagation.
• It prunes the constraint network by removing useless constraints.
• It uses an annealing schedule that interleaves adaptive cooling with geometric reheating.
• In move generation, it concentrates on variables that are involved in constraint violations.
• When Yuck is configured to use multiple threads, each thread runs a solver with solvers sharing bounds on the objective value.

Global constraints

Yuck provides dedicated solvers for the following global MiniZinc constraints and their reified counterparts:

• all_different, all_different_except, all_different_except_0
• bin_packing, bin_packing_capa, bin_packing_load
• circuit
• count_eq, count_geq, count_gt, count_leq, count_lt, count_neq
• cumulative
• diffn, diffn_nonstrict
• disjunctive, disjunctive_strict
• global_cardinality, global_cardinality_closed, global_cardinality_low_up, global_cardinality_low_up_closed
• increasing, strictly_increasing
• inverse
• lex_less, lex_lesseq
• maximum
• member
• minimum
• nvalue
• regular
• table

Yuck provides dedicated neighbourhoods for the following global MiniZinc constraints:

• all_different, all_different_except, all_different_except_0
• circuit
• inverse
• increasing, strictly_increasing
• regular
• table: By default, only table constraints with not more than three columns are eligible for implicit solving. To disable this limitation for a particular table constraint, include yuck.mzn and annotate the constraint with implicit.

MiniZinc extensions

bool2costs

bool2costs is a function which measures how much the current assignment of values to problem variables violates a given Boolean MiniZinc expression. The smaller the violation, the lower the result and 0 means that the expression is satisfied.

bool2costs can be used to turn Boolean MiniZinc expressions into soft constraints, for example:

include "disjunctive.mzn";
include "yuck.mzn";

array [1..4] of var int: o;
array [1..4] of var int: d;

constraint o[1] in 2..5 /\ d[1] in 2..4;
constraint o[2] in 2..4 /\ d[2] in 1..6;
constraint o[3] in 3..6 /\ d[3] in 4..4;
constraint o[4] in 2..7 /\ d[4] in 1..3;

var int: overlap = bool2costs(disjunctive(o, d));

solve minimize(overlap);

output ["o = ", show(o), "\n", "d = ", show(d), "\n", "overlap = ", show(overlap)];

Applying Yuck to this problem results in:

o = [2, 4, 5, 2]
d = [2, 6, 4, 3]
overlap = 7
----------
o = [2, 4, 5, 7]
d = [2, 4, 4, 3]
overlap = 6
----------
o = [2, 4, 5, 7]
d = [2, 2, 4, 3]
overlap = 3
----------
o = [2, 4, 6, 4]
d = [2, 1, 4, 3]
overlap = 2
----------
o = [2, 4, 6, 4]
d = [2, 1, 4, 1]
overlap = 1
----------
o = [4, 2, 6, 3]
d = [2, 1, 4, 1]
overlap = 0
----------
==========

bool2costs is defined for every constraint implemented by Yuck, including all the global constraints listed above. Please see the section on cost models for the technical details.

To use bool2costs, you have to include yuck.mzn.

Keep in mind, though, that bool2costs is a non-standard MiniZinc extension which is not supported by other MiniZinc backends.

Goal hierar