3.7. Globalizer

Globalizer [1] analyses a model and set of data to provide suggestions of global constraints that can replace or enhance a user’s model.

3.7.1. Basic Usage

To use Globalizer simply execute it on a model and set of data files:

minizinc --solver globalizer model.mzn data-1.dzn data-2.dzn

Note: Globalizer may also be executed on a non-parameterised model with no data files.

The following demonstrates the basic usage of Globalizer. Below, we see a simple model for the car sequencing problem [2], cars.mzn.

列表 3.7.1 Model for the car sequencing problem (cars.mzn).
% cars.mzn
include "globals.mzn";

int: n_cars; int: n_options; int: n_classes;

set of int: steps = 1..n_cars;
set of int: options = 1..n_options;
set of int: classes = 1..n_classes;

array [options] of int: max_per_block;
array [options] of int: block_size;
array [classes] of int: cars_in_class;
array [classes, options] of 0..1: need;

% The class of car being started at each step.
array [steps] of var classes: class;

% Which options are required by the car started at each step.
array [steps, options] of var 0..1: used;

% Block p must be used at step s if the class of the car to be
% produced at step s needs it.
constraint forall (s in steps, p in options) (used[s, p]=need[class[s], p]);

% For each option p with block size b and maximum limit m, no consecutive
% sequence of b cars contains more than m that require option p.
constraint
    forall (p in options, i in 1..(n_cars - (block_size[p] - 1))) (
        sum (j in 0..(block_size[p] - 1)) (used[i + j, p])
            <= max_per_block[p]);

% Require that the right number of cars in each class are produced.
constraint forall (c in classes) (count(class, c, cars_in_class[c]));

solve satisfy; % Find any solution.

And here we have a data file cars_data.dzn.

列表 3.7.2 Data for the car sequencing problem (cars_data.dzn).
% cars_data.dzn
n_cars = 10;
n_options = 5;
n_classes = 6;
max_per_block = [1, 2, 1, 2, 1];
block_size =    [2, 3, 3, 5, 5];
cars_in_class = [1, 1, 2, 2, 2, 2];

need =  array2d(1..6, 1..5, [
    1, 0, 1, 1, 0,
    0, 0, 0, 1, 0,
    0, 1, 0, 0, 1,
    0, 1, 0, 1, 0,
    1, 0, 1, 0, 0,
    1, 1, 0, 0, 0
]);

Executing Globalizer on this model and data file we get the following output:

% minizinc --solver globalizer cars.mzn cars_data.dzn
cars.mzn|33|12|33|69 [  ] gcc(class,cars_in_class)
cars.mzn|33|35|33|68 [  ] count(class,c,cars_in_class[c])
cars.mzn|28|27|28|65;cars.mzn|29|9|30|32 [  ] sliding_sum(0,max_per_block[p],block_size[p],used[_, p])

Each line of output is comprised of three elements.

  1. Expression locations (separated by semicolon ‘;’) that the constraint might be able to replace.

  2. (Between square brackets ‘[’ ‘]’) the context under which the constraint might replace the expressions of 1.

  3. The replacement constraint.

From the example above we see that a gcc constraint and a sliding_sum constraint can replace some constraints in the model. Taking the sliding_sum case, we see that it replaces the expression cars.mzn|28|27|28|65 which corresponds to i in 1..(n_cars - (block_size[p] - 1)) and cars.mzn|29|27|28|65 which corresponds to the <= expression including the sum. The original constraint can be replaced with:

constraint forall (p in options) (
    sliding_sum(0, max_per_block[p], block_size[p], used[..,p]));

3.7.2. Caveats

MiniZinc syntax support. Globalizer was implemented with support for a subset of an early version of the MiniZinc 2.0 language. As a result there are some limitations. First, Globalizer does not support set variables or enum types. The array slicing syntax supported in MiniZinc was not decided upon when Globalizer was implemented so it uses an incompatible syntax. Globalizer uses _ instead of ... This can be seen above in the translation of used[_,p] to used[..,p].

New constraint. A special two argument version of the global_cardinality constraint called gcc has been added which is not in the standard library. It is defined as follows:

predicate gcc(array[int] of var int: x, array[int] of var int: counts) =
  global_cardinality(x,
                     [ i | i in index_set(counts) ],
                     array1d(counts));

3.7.3. Supported Constraints

Globalizer currently supports detection of the following constraints:

alldifferent               alldifferent_except_0      all_equal_int
bin_packing                bin_packing_capa           bin_packing_load
binaries_represent_int     binaries_represent_int_3A  binaries_represent_int_3B
binaries_represent_int_3C  channel                    channelACB
count_geq                  cumulative_assert          decreasing
gcc                        global_cardinality         inverse
lex_lesseq_int_checking    lex2_checking              maximum_int_checking
minimum_int_checking       member                     nvalue
strict_lex2_checking       subcircuit_checking        true
atleast                    atmost                     bin_packing_load_ub
circuit_checking           count                      diffn
distribute                 element                    increasing
lex_less_int_checking      sliding_sum                sort_checking
unary                      value_precede_checking

3.7.4. Using Globalizer in the MiniZinc IDE

To use the Globalizer in the MiniZinc IDE, open a model, and several data files. Select Globalizer from the solver configuration dropdown menu. Click the solve button (play symbol). If you did not select any data file, a dialog should pop up that allows you to select data files. To select multiple data files hold the Ctrl or Cmd key while clicking on each data file.

images/ide_select_data.png

Click run. While processing your model and data files the MiniZinc IDE will display a progress bar on the toolbar.

images/ide_globalized.png

Any discovered global constraints will be listed in the output pane of the IDE. Clicking on one of these constraints will highlight in the model the expressions that might be replaceable or strengthened by the constraint.

3.7.5. How it works

A summary of the algorithm is presented here. For a more detailed exploration of the approach see the Globalizing Constraint Models paper [1].

  • Normalize. In this step the model is transformed to make analysis easier.

    • Conjunctions of constraints are broken into individual constraints. For example: C1 /\ C2; becomes C1; C2;

    • Conjunctions under forall constraints are broken into individual forall constraints. For example: forall(...) (C1 /\ C2); becomes forall(...) (C1); forall(...) (C2)

  • Generate submodels. In this step all subsets containing 1 or 2 constraints (this can be configured using --numConstraints argument) are enumerated.

  • Instantiate and unroll into groups. Each submodel is instantiated with the provided data files. These instantiated submodels are further used to produce more submodels by unrolling loops. For example, a constraint such as forall(i in 1..n) (c(i)); will be used to produce the constraints: c(1) and c(n) for each instantiation of n in the data files. All instantiated submodels are then grouped together.

  • Process groups. For each submodel in a group a set of 30 random solutions are found. (configurable using the --randomSolutions argument). A template model with all of these random solutions is created.

    The different variables (including arrays and array accesses) and parameters used by a submodel are collected into a set of potential arguments along with the constant 0 and a special blank symbol representing an argument that can be inferred based on others used.

    The list of constraints above is filtered based on the arguments available. For example, the alldifferent constraint will be removed from the list of candidates if the submodel does not reference any arrays of variables.

    Finally the set of constraints are filtered by adding them to the template and solving it. If the template is satisfiable, the constraint accepts all of the random solutions.

    30 sample solutions for each candidate constraint are generated. (configurable using the --sampleSolutions argument). The candidate is then ranked based on how many of these solutions are also solutions to the original submodel. If its score is less than some threshold the candidate is removed from the set of candidates for this group and will not be tested on later submodels.

  • Report. The remaining candidates are presented to the user.

3.7.6. Performance tips

Globalizing constraint models can be a time consuming task. If

  • Use small or relatively easy instances. Globalizer solves many subproblems while processing your model and data files. Using easier instances can speed up the process considerably.

  • Disable the initial pass. As discussed above, Globalizer performs two passes. The first pass tries to detect alternate viewpoints that can be added to your model. If you are confident that this will not be useful we recommend disabling this first pass using the --no-initial-pass argument.

  • Narrow search using filters. Globalizer attempts to match a large selection of global constraints to subproblems in your model. If you wish to check if only a few specific constraints are present you can focus Globalizer using the --constraintFilter or -f arguments followed by a comma separated list of strings. Only global constraints where one of the strings is a substring will be included in the search.

  • Disable implies check. The implication check can also be disabled to improve performance. This results in less accurate results but may still help a user to understand the structure of their model.

  • Free-search. To improve accuracy and to avoid false positives, subproblems solved by Globalizer are solved using a random heuristic and restarts. If the subproblems are particularly difficult to solve a random heuristic may be prohibitive and the solver may not be able to produce enough samples within the solving time-limit. In these circumstances a user can either increase the solver timeout using the -t argument followed by the number of milliseconds a solver should be given to find samples. Alternatively the --free-search argument can be used to force Globalizer to use the solver’s free search to find samples. This has the downside of reducing the diversity of samples but allows enough samples to be found to allow suggested globals to be found.

3.7.7. Limitations / Future work

  • Globalizer supports only a subset of the MiniZinc language and as such cannot be executed on all MiniZinc models.

  • There are some relatively cheap syntactic approaches that should be performed before Globalization that currently is not implemented. For example, there are several common formulations of an alldifferent constraint that can be detected syntactically. This would be much cheaper than using Globalizer.