« Constraint programming in ECLiPSe Constraint Programming System | Main | MiniZinc version 1.0.1 released »

Some new ECLiPSe models, e.g. Minesweeper

Since I wrote Constraint programming in ECLiPSe Constraint Programming System the other day, I have published about 15 new ECLiPSe models on My ECLiPSe page.

Here these new models are, with some comments or reflections. All of the models are translations of my MiniZinc or Comet models.

Assignment problems

Model: assignment.ecl
This program contains some examples of the assigment problems from Winston's "Operations Research" and GLPK (and some other source).

Data is represented as a matrix of arrays: 
% 
% Winston "Operations Research", page 398, swimming team example
% (original version)
% See http://www.hakank.org/minizinc/assignment2.mzn 
% 
cost(2, minimize, []([](54, 54, 51, 53), 
                     [](51, 57, 52, 52),
                     [](50, 53, 54, 56),
                     [](56, 54, 55, 53))).
The second argument is the "mode" of operations, i.e. if it is a maximization or minimization problem.

The main constraints are the following: 
%
% exacly one assignment per row, all rows must be assigned
%
( for(I,1,Rows), param(X,Cols) do
   sum(X[I,1..Cols]) #= 1
),

%
% zero or one assignments per column
%
( for(J,1,Cols), param(X,Rows) do
     sum(X[1..Rows,J]) #=< 1
),

Bin packing problems

Model: bin_packing.ecl
Contains some small examples of bin packing from some sources.

Global constraint bin_packing

Model: bin_packing2.ecl
This is (a decomposition of) the global constraint bin_packing, related to but not the same as the common usage of bin packing (see the above).

It was also a study of translating a predicate from MiniZinc (using bool2int for reification) to ECLiPSe. Here is the MiniZinc code that was to be converted; n is the size of the weights and bins: 
   forall(b in 1..n) (
      sum(j in 1..n) ( weights[j]*bool2int(bins[j] = b)) <= capacity
   )
Here are three variants of the same for loop in ECLiPSE, where N is the number of bins.

Using the same approach as MiniZinc, I (right now) prefer version 2 to version 1, since it is more succint, and prefer version 2 to version 3 since it is clearer. These preferences probably will change over the time. Update some days later: And it already did, see below.

Note that both the MiniZinc version and this ECLiPSe version are fully multidirectional, i.e. we can let either (or all) of the variables be free and it still work. Note: If we let Bins free in ECLiPSe, we ought to fix the length of it (to 3 in the program) otherwise it will not work as excepted.

Version 1, straightforward use of for and fromto and a condition 
( for(B,1,N),
  param(Weights,Bins,N,Capacity) do
  ( for(J,1,N),
    fromto(0,In,Out,Sum),
    param(Weights,Bins,B) do
       Bins[J] #= B 
     -> 
      Out #= In + Weights[J] 
    ; 
      Out = In
  ),
  Sum #=< Capacity
)
Version 2, using reification like bool2int. 
( for(B,1,N),
  param(Weights,Bins,N,Capacity) do
  ( for(J,1,N),
    fromto(0,In,Out,Sum),
    param(Weights,Bins,B) do
    %                        reification (0 or 1)
    Out #= In + Weights[J] * (Bins[J] #= B)
 ),
 Sum #=< Capacity
)
Version 3
Here we put the calculation in the fromto call (instead of the do body). With this change, eval(Sum) is now needed, and the param with the variables in the J loop is still needed. 
( for(B,1,N),
   param(Weights,Bins,N,Capacity) do
     ( for(J,1,N),
       fromto(0,In,In + Weights[J]*(Bins[J] #= B),Sum),
       param(Weights,Bins,B) do
         true
     ),
     eval(Sum) #=< Capacity
).
Later update: Joachim Schimpf (from the ECLiPSe team) kindly remarked that it probably better to use eval since it will just create one constraint instead of many small constraints using inside the inner loop.

Joachim also mentioned a fourth version:
Version 4
Use foreach to collect S and then use sum. 
 for(B,1,N),
    param(Weights,Bins,N,Capacity) do
        (for(J,1,N),
         foreach(S,Sum),
         param(Weights,Bins,B) do
              S = Weights[J]*(Bins[J] #= B)
        ),
         sum(Sum) #=< Capacity
).
Thanks Joachim. (End of update)

Calculs d'enfer

Model: calculs_d_enfer.ecl
This is a alphametic problem taken from Jianyang Zhou "The Manual of NCL version 1.2", page 33. It was quite straightforward to translate from MiniZinc.

Curious set of integers

Model: curious_set_of_integers.ecl
From Martin Gardner (February 1967)
The integers 1,4,9, and 120 form a set with a remarkable priperty: the product of any two integers is one less than a perfect square. Find a fifth number that can be added to the set without destroying this property.


Heterosquare problem

Model: heterosquare.ecl
This is yet another "grid and sum" problem. See Heterosquare for an explanation of the problem.

Minesweeper

Model: minesweeper.ecl
This is a general Minesweeper solver given problem instances of the following format: 
problem(0,[]([](_,_,2,_,3,_),
             [](2,_,_,_,_,_),
             [](_,_,2,4,_,3),
             [](1,_,3,4,_,_),
             [](_,_,_,_,_,3),
             [](_,3,_,3,_,_))).
There are 14 examples, among them the 10 examples from Gecode's minesweeper.cpp.

The main constraints are implemented in the following loop. It took quite long to realize that multifor([A,B]...) was needed for the summing of the cells (in the Sum variable) for it to work, instead of two nested for(A) ... for(B)-loops. It was also quite late in the programming phase when I switched the representation of unknowns from -1 (as was used in the MiniZinc model minesweeper.mzn and other implementations) to the anonymous variable _. Now it use ground for checking if it is a hint or not. 
%
% Game[I,J] = _ means that it is unknown from start, may be a mine.
% Games[I,J] >= 0 means that the value is known and that it is not a mine.
%
%
% Note: the A,B loop below must be a multifor, otherwise the Sum
%       don't work.
%
( for(I,1,R), param(Game, Mines, C, R) do
      ( for(J,1,C), param(Game, Mines, R, C, I) do
            GameIJ is Game[I,J],
            MinesIJ is Mines[I,J],

            % some reasoning about this cell
            (ground(GameIJ) -> MinesIJ #= 0 ; true),
            (MinesIJ #= 1 -> ground(GameIJ) ; true),

            % we check only those cells we are unsure of, i.e.
            % GameIJ >= 0
            ground(GameIJ)
      ->                      
            % sum the number of neighbors of this cell
            Sum :: 0..8,
            ( multifor([A,B],-1,1),  % must be a multifor
              fromto(0, In, Out, Sum), 
              param(Mines, R, C, I, J) do
                      I+A #>  0, J+B #>  0,
                      I+A #=< R, J+B #=< C
            -> 
              MinesIAJB is Mines[I+A,J+B],
              Out #= In + MinesIAJB
            ; 
              Out = In
            ),

            % all sums must sum up to Game[I,J]
            Sum #= GameIJ
      ;
        true

      )
),

Photo problem

Model: photo_problem.ecl
This is a problem from the Mozart/Oz tutorial:
Betty, Chris, Donald, Fred, Gary, Mary, and Paul want to align in one row for taking a photo. Some of them have preferences next to whom they want to stand: 1. Betty wants to stand next to Gary and Mary. 2. Chris wants to stand next to Betty and Gary. 3. Fred wants to stand next to Mary and Donald. 4. Paul wants to stand next to Fred and Donald. Obviously, it is impossible to satisfy all preferences. Can you find an alignment that maximizes the number of satisfied preferences?
The preferences are coded as an array of arrays of size 2, but there is also a (commented) variant using adjacency matrix.

This program is not very fast.

Remarkable sequence (Langford problem)

Model: remarkable_sequence.ecl
This problem (and the solution approach I use) is from R. Apt, J. Brunekreef, V. Partington and A. Schaerf Alma-0: An imperative language that supports declarative programming (1997, PDF). It is the Langford problem with 3 occurrences of each digit 0..9.

In my approach I use some nth1(J,A,I) predicate to access the J'th element in the sequence A (the decision variable), since the construct A[J] don't seems to work (see "Who killed Agatha?" for a related problem).

Set covering (and set partitioning)

Models:
set_covering.ecl
set_covering2.ecl
set_covering3.ecl
set_covering4.ecl

These are different versions of the set covering, with examples from Winston's "Operations Resear ch", Taha's "Operations Research - An Introduction", etc.

The example 2, 3, and 4 first finds the optimal value, and then finds all the solutions with that value, and it was quite easy implement this in ECLiPSe. set_covering4.ecl implements both set covering and set partitions.

Set covering deployment

Model: set_covering_deployment.ecl
This program implements the Mathword's example in Set covering deployment where the objective is to places armies in the Roman Empire.

Who killed Agatha?

Model: who_killed_agatha.ecl
This is a standard benchmark for theorem proving, originally from F. J. Pelletier: Seventy-five problems for testing automatic theorem provers., Journal of Automated Reasoning, 2: 191 216, 1986.

The problem is states:
Someone in Dreadsbury Mansion killed Aunt Agatha. Agatha, the butler, and Charles live in Dreadsbury Mansion, and are the only ones to live there. A killer always hates, and is no richer than his victim. Charles hates noone that Agatha hates. Agatha hates everybody except the butler. The butler hates everyone not richer than Aunt Agatha. The butler hates everyone whom Agatha hates. Noone hates everyone. Who killed Agatha?
I wrote about this problem in Learning Constraint Programming IV: Logical constraints: Who killed Agatha? revisited and compared the implementation in other constraint systems (MiniZinc, JaCoP, Choco, Choco, Comet, and Gecode). One of the problem I had in some of these systems was with the Element constraint when the decision variables where a matrix (or array) and the index was also a decision variable.

I have the same problem with my ECLiPSe solution. The following do not seems to work, where Hates (a matrix of 0/1 varibales), Killer, and Victim are all decision variables: 
Hates[Killer,Victim] #= 1,
which states that the killer always hates the victim. However, the following works, where we loops through all the indices and use the proper one (the one that "happens to represent" Killer): 
( for(I,1,N), param(Killer,Victim,Hates,Richer) do
      Killer #= I => Hates[I, Victim] #= 1,
      Killer #= I => Richer[I, Victim] #= 0
)
Other than that, the modeling was quite simple.

As noted before, this problem can be solved in many ways, as most problems can. Here I wanted to implement it the same way as the other CP systems, just to check how ECLiPSe handles Element.

Young tableaux and partitions

Model: young_tableaux.ecl
See the entries in MathWorld, and Wikipedia for more about this problem.

Posted by hakank on July 3, 2009 10:41 AM |