« Helmut Simonis' blog: Constraint Applications Blog | Main | Minizinc version 1.1.4 released »

Some new MiniZinc models

Here are some new MiniZinc models. Some are completely new - or previously unannounced - but there are also some which has been implemented in some other constraint programming system before.

New models

Here are some new - or at least previously not announced - models:

Latin square card puzzle

latin_square_card_puzzle.mzn: Latin square card puzzle

I found this problem in Mario Livio's nice PopSci book about the development of group theory The Equation that couldn't be solved, page 22:
... Incidentally, you may get a kick out of solving this eighteenth century card puzzle: Arrange all the jacks, queens, kings, and aces from a deck of cards in a square so that no suit or value would appear twice in any row, column, or the two main diagonals.
My general approach is to use integers of the following form. n is the size of the matrix (here 4) and m is the number we use for modulo operation (here 10). These values are calculated automatically by the model depending on n. 
 % values: i mod 10 
  0, 1, 2, 3,  % suite 1: 0 div 10
 10,11,12,13,  % suite 2: 1 div 10
 20,21,22,23,  % suite 3: 2 div 10
 30,31,32,33   % suite 4: 3 div 10
What then want that the values divided by 10 (the suites) should be different in each row, column, and diagonals, and also the values by modulo 10 (the values) is different in each row, column, and diagonals.

With the symmetry breaking constraint that the value 0 must be in the upper leftmost cell, there are 72 solutions for n = 4. Here is one of them: 
 0 33 22 11
21 12  3 30
13 20 31  2
32  1 10 23
Note: There are solutions for n = 4 and n = 5 but not for n = 6. The n = 6 problem is the same as Euler's 36 officer's problem, which thus is not solvable. Also see MathWorld.

Investment problem

This problem is from ORMM (Operations Research Models and Methods):
A portfolio manager with a fixed budget of $100 million is considering the eight investment opportunities shown in Table 1. The manager must choose an investment level for each alternative ranging from $0 to $40 million. Although an acceptable investment may assume any value within the range, we discretize the permissible allocations to intervals of $10 million to facilitate the modeling. This restriction is important to what follows. For convenience we define a unit of investment to be $10 million. In these terms, the budget is 10 and the amounts to invest are the integers in the range from 0 to 4.
Here are two implementations:

Arg max

argmax.mzn

argmax/argmin predicate
  • argmax_ge(pos, x)
    pos is the index x for the maximum value(s). There can be many maximum values.
  • argmax_gt(pos, x)
    pos is the index x for the maximum value. There can be only one maximum value.
  • argmin_le(pos, x)
    pos is the index x for the minimum value(s). There can be many minimum values.
  • argmin_lt(pos, x)
    pos is the index x for the minimum value. There can be only one maximum value.

Permutation number

permutation_number.mzn

A permutation number is the number of transpositions in a permutation, see Wikipedia Permutation.

Sicherman dice

sicherman_dice.mzn

From Wikipedia Sicherman_dice:
Sicherman dice are the only pair of 6-sided dice which are not normal dice, bear only positive integers, and have the same probability distribution for the sum as normal dice.

The faces on the dice are numbered 1, 2, 2, 3, 3, 4 and 1, 3, 4, 5, 6, 8.
I read about this problem in a book/column by Martin Gardner long time ago, and got inspired to model it now by the recent WolframBlog post Sicherman Dice

Here is the vital part of the code: 
array[2..12] of int: standard_dist = 
       array1d(2..12, [1,2,3,4,5,6,5,4,3,2,1]);
% the two dice
array[1..n] of var 1..m: x1 :: is_output;
array[1..n] of var 1..m: x2 :: is_output;
constraint
forall(k in 2..12) (
  standard_dist[k] = 
    sum(i,j in 1..n) ( 
       bool2int(x1[i]+x2[j] == k)
    )
)
% symmetry breaking
/\ increasing(x1) 
/\ increasing(x2)

/\ % x1 is less or equal to x2
forall(i in 1..n) (
   x1[i] <= x2[i]
)
% /\ lex_lesseq(x1, x2)
This model gets the two different solutions, first the standard dice and then the Sicherman dice: 
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]

--

[1, 2, 2, 3, 3, 4]
[1, 3, 4, 5, 6, 8]
Extra: If we also allow that 0 (zero) is a valid value then the following two solutions are also shown. The only thing we have to do is to change the domains of x1 and x2: 
% the two dice
array[1..n] of var 0..m: x1 :: is_output;
array[1..n] of var 0..m: x2 :: is_output;
Here here are the two new solutions: 
[0, 1, 1, 2, 2, 3]);
[2, 4, 5, 6, 7, 9]);

--

[0, 1, 2, 3, 4, 5]);
[2, 3, 4, 5, 6, 7]);
These two extra cases are mentioned in MathWorld SichermanDice.

Translations of other models

The following MiniZinc models is ports from models written in at least one other constraint programming system before, mostly Comet:

Posted by hakank on July 18, 2010 09:12 AM |