Fixing issues with large-domain variables from FlatZinc in toulbar2

[Alexander-Schiendorfer]

Hi,

this is a small pull request to improve the encoding of VarArrays from FlatZinc for toulbar2. Otherwise, the generated -MAXINT:MAXINT variables from fzn2py.awk make many models explode in toulbar2.

I used the Numberjack portfolio solver but only added the toulbar2 configuration (commented out the others in njportfolio.py - not part of this pull request).

Let's start with this small MiniZinc model:

var 5..10: x;
var 5..10: y; 
array[1..2] of var 5..10: xs = [x, y];

constraint x < y;
solve minimize x;

Compiled to FlatZinc for the Numberjack portfolio solver, we get

array [1..2] of int: X_INTRODUCED_0 = [1,-1];
var 5..10: x:: output_var;
var 5..10: y:: output_var;
array [1..2] of var int: xs = [x,y];
constraint int_lin_le(X_INTRODUCED_0,[x,y],-1);
solve  minimize x;

when processed by fzn2py, we get a NJ model that looks like this:

def get_model():
    model = Model()
    X_INTRODUCED_0 = [1,-1]
    x = Variable(5,10,'x')
    y = Variable(5,10,'y')
    xs = VarArray(2,-10000000,10000000,'xs')
    model.add(xs[0] == [x,y][0])
    model.add(xs[1] == [x,y][1])

for any classical constraint solver like Mistral2, this does not seem to be a problem as the domains of the variables introduced for 'xs' are immediately truncated to 5..10 due to the equality constraints. However, with toulbar2, we seem to try and build huge Cartesian products:

% Numberjack.ModelSizeError: ERROR: Model decomposition size too big 120000006 for solver None.

That's why I'm suggesting to build the VarArray slightly different (since we have the correct domain sizes in the FlatZinc already) with the original statments commented out:

def get_model():
    model = Model()
    X_INTRODUCED_0 = [1,-1]
    x = Variable(5,10,'x')
    y = Variable(5,10,'y')
#    xs = VarArray(2,-10000000,10000000,'xs')
#    model.add(xs[0] == [x,y][0])
#    model.add(xs[1] == [x,y][1])
    xs = VarArray([x,y])
    model.add( int_lin_le(X_INTRODUCED_0,[x,y],-1) )

After this change, toulbar2 is capable of solving the model. I have the impression that many models that would otherwise lead to ModelSizeErrors can now be solved.

For example, in the CP2013 paper "Solving Intensional Weighted CSPs by Incremental Optimization with BDDs" , the authors claim that (with respect to talent scheduling) "Unfortunately, in most of the instances of this problem, Toulbar2 reported an error saying that the model decomposition was too big." After the fix I can easily reproduce the experiments (with no model explosion)

I hope the fix is okay.

Cheers, Alex

[Alexander-Schiendorfer]

Btw. now the toolchain from MiniZinc to Toulbar2 via Numberjack absolutely rocks on some benchmark instances :) I'd like to add a little how-to on http://isse-augsburg.github.io/constraint-relationships/ which would guide people to Numberjack, of course.

[Alexander-Schiendorfer]

The following MWE illustrates the last bug fixed by commit 0681e91 in action:

from Numberjack import * 

x,y,z = VarArray(3,0,2)

model = Model(Minimise( 2 * (x + 1 != y)))                              
print model                
solver = model.load("Toulbar2", encoding=None)
solver.solve()

print "Solved with  x -> ",x.get_value(), ", y -> ",y.get_value(),", z -> ",z.get_value()

We want x+1 = y to hold as a soft constraint with weight 2, so we add the negation in the objective and minimize!

Before the fix, we get as answer

Solved with  x ->  0 , y ->  0 , z ->  0

which clearly violates x + 1 = y and should yield overall costs of 2.

After the fix, we get as answer

Solved with  x ->  0 , y ->  1 , z ->  0

[9thbit]

Excellent, thanks @Alexander-Schiendorfer! :+1: