My Constraint Programming Blog: Miscellaneous news

Here are some miscellaneous news.

Choco

Version 2.1

I have forgot to mention that Choco have released version 2.1 . Download this version via the download page. The Sourceforge download page is here.

Changed models for version 2.1

I have changed some of my Choco models for version 2.1. The biggest change was the use of cumulative in FurnitureMoving.java where the call to the cumulative constraint have changed and now use TaskVariable.

I added the following

// Create TaskVariables
TaskVariable[] t = new TaskVariable[starts.length];
   for(int i = 0; i < starts.length; i++){
      t[i] = makeTaskVar("", starts[i], ends[i], durations[i]);
   }

and changed the call to cumulative to:

 
m.addConstraint(cumulative(null, t, constantArray(_heights), constant(NumPersons)));

Also, the line

durations[i] = makeConstantVar("durations" + i, durationsInts[i]);

was changed to

durations[i] = makeIntVar("durations" + i, durationsInts[i], durationsInts[i]);

For some of the other models (compiled for version 2.0.*), I just recompiled the source and it worked without any change in the code.

MiniZinc

List of global constraints

At the MiniZinc site, there is now a list of the supported global constraints in MiniZinc: MiniZinc: Global Constraints.

MiniZinc Library

MiniZinc Library is a great collections of problems, examples, and tests. (For some reason is not linked from the main MiniZinc site.)

Output in Minizinc

I wrote here about the change of output in MiniZinc version 1.0 . Only the distributed solver minizinc supports the output statement (for some kind of "pretty printing" of the output), but the solvers using the FlatZinc format has no such support. Since I want to see matrices presented in a normal way for all solvers, I wrote a simple Perl program to show matrices more pretty than just a single line. Also, single arrays are shown without array1d(...).

The Perl program is mzn_show.pl and it simply takes the result from a solver and reformats the result.

An example: The output from the debruijn_binary.mzn from a solver using FlatZinc file, such as Gecode/FlatZinc and MiniZinc's fdmip is:

bin_code = array1d(1..8, [0, 0, 0, 0, 1, 0, 1, 1]);
binary = array2d(1..8, 1..4, [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0]);
x = array1d(1..8, [0, 1, 2, 5, 11, 6, 12, 8]);

When filtering this with mzn_show.pl it will be shown as:

bin_code: 0 0 0 0 1 0 1 1
% binary = array2d(1..8, 1..4, [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0]);
binary:
  0 0 0 0
  0 0 0 1
  0 0 1 0
  0 1 0 1
  1 0 1 1
  0 1 1 0
  1 1 0 0
  1 0 0 0
x: 0 1 2 5 11 6 12 8

Very simple, but quite useful.

Somewhat related: The NEWS file of the latest ROTD (Release of The Day) states the following:

FlatZinc output processing tool

We have added a new tool, solns2dzn, that can be used to process the output of FlatZinc implementations in various ways. For example, it can extract each individual solution and write it to a separate file.

This program is distributed as source (Mercury), not as an executable, so I have not been able to test it.

Hidato and exists

In the hidato.mzn model I have changed the exists construct

forall(k in 1..r*c-1) (
  exists(i in 1..r, j in 1..c) (
    k = x[i, j] % fix this k
    /\
    exists(a, b in  {-1, 0, 1} where
      i+a >= 1 /\ j+b >=  1 /\
      i+a <= r /\ j+b <= c
      /\ not(a = 0 /\ b = 0)
    )
     (
       % find the next k
       k + 1 = x[i+a, j+b]
     )
  )
)

to a a version using just var ints:

forall(k in 1..r*c-1) (
    let {
       var 1..r: i,
       var 1..c: j,
       var {-1,0,1}: a,
       var {-1,0,1}: b
    }
    in
    k = x[i, j] % fix this k
    /\
    i+a >= 1 /\ j+b >=  1 /\
    i+a <= r /\ j+b <= c
    /\ not(a = 0 /\ b = 0)
    /\
    % find the next k
    k + 1 = x[i+a, j+b]
)

This replacement of exists with int vars, if possible, seems to always be more effective.

However, there is one use of exists where it is harder to replace in this way. As an example, take Pandigital numbers in any base (the model includes a presentation of the problem) where - among other things - we want to find some array indices of the integer array x in order to find the positions of three numbers num1, num2 and res (the result of num1 * num2).

% num1. 
exists(j in 1..x_len) (
   j = len1 /\
   toNum([x[i] | i in 1..j], num1, base)
)

/\  % num2
exists(j, k in 1..x_len) (
   j = len1+1 /\ 
   k = len1+len2 /\ k > j  /\
   toNum([x[i] | i in j..k], num2, base)
)

/\ % the product
exists(k in 1..x_len) (
   k = len1+len2+1 /\
   toNum([x[i] | i in k..x_len], res, base)
)

Using this approach, we have to use exists since indices in a range (e.g. j in 1..j) must not be an int var.

Also

Both Choco and MiniZinc sites now have links to my site, which is quite fun:
* Choco, Users (last)
* MiniZinc and FlatZinc (also last)

Work related page in english

The page Håkan Kjellerstrand, CV and work related interests is a english version of my work related page. (The original, swedish, version is here.)