January 04, 2011

Antoni Niederliński: A Quick and Gentle Guide to Constraint Logic Programming via ECLiPSe

In March last year I wrote about Antoni Niederliński's book about Constraint Programming in ECLiPSe: New book: Antoni Niederliński: Programowanie w logice z ograniczeniami ("Programming in Logic with Constraints"). Since the book was in Polish I could not read more than very small excerpts.

Now he has published an English translation of this book: A Quick and Gentle Guide to Constraint Logic Programming via ECLiPSe, and is downloadable as PDF from the site (there is also a way of order a paper version):
The book is an introductory and down-to-earth presentation of Constraint Logic Programming (CLP), an exciting software paradigm, more and more popular for solving combinatorial as well as continuous constraint satisfaction problems and constraint optimization problems. It is based on the popular, intensively supported and documented ECLiPSe platform, freely available under Cisco-style Mozilla Public License. The Author aims at teaching modeling i.e. translating verbal problem statements into Prolog or CLP programs. This has been dealt with by a series of problems of increasing complexity, translated into Prolog or CLP programs and running under ECLiPSe. The theoretical background has been minimized while stressing intuitive understanding. Presented constraint satisfaction problems deal with finding feasible/optimal states, and feasible/optimal state-space trajectories, starting with simple puzzles and proceeding to advanced ones, like graph coloring problems, scheduling problems with particular attention to job-shop problems (including the famous MT10 benchmark), and Traveling Salesman Problems. The last chapter is concerned with Continuous Constraints Satisfaction and Constraint Optimization Problems.
I read a draft of this book some month ago and really like the approach of the book of presenting a lot of fun examples/puzzles which are first translated to rather "plain" Prolog and then later to CLP together with many explanations of what is done. I especially like Chapter 6, CLP with global constraints for optimal solutions, where some global constraints (disjunctive cumulative) are discussed. Great work Antoni!

May 14, 2010

A modulo propagator for ECLiPSe/ic

The ECLiPSe program mentioned in this post: modulo_propagator.ecl which defines an modulo propagator for lib(ic) and includes some simple tests.


In Some 40 new ECLiPSe models I mentioned some 40 models that where translated from SICStus Prolog to ECLiPSe. For two problems, however, I became very aware of that the where no support for the modulo operator in ECLiPSe's ic library. (These models has now been "patched" using the propagator version of modulo, but the older version is kept in comments.)

"Trickery" versions of modulo

In these models, I tried some different approaches ("trickeries"), including using the suspend library, which works for some problems, but not for these two.
  :- lib(suspend).
  % ....
  modulo_suspend(X,M,Y) :-  
       suspend(M is X mod M, 3, [X,Y]->inst).
One way that did worked with the Averbach & Chein Seating puzzle, was to use an auxilliary variable C1:
C1 :: 0..1,
PDyer+C1*5 #= (Hosier - 2),
and similar for the four other modulo constraints.

For the Divisible by 9 through 1 problem, I wanted this construct (which don't work since T[Base_I] is a decision variable and not bound which is required by mod)
 T[Base_I] mod I #= 0
The working version was using the lib(ic_kernel) predicate get_max for getting the maximal domain of T[Base_I]:
   % ...
   TBase_I is T[Base_I],
   % get max domain value for [Base_I]
   get_max(TBase_I, TBase_IMax), 
   MaxLimit is TBase_IMax // I,
   Q :: 1..MaxLimit,
   TBase_I #= Q*I
   % ...

A modulo propagator for ECLiPSe

However, I wasn't really satisfied with these solutions and first tried to write a modulo propagator based on the example in the Comet Tutorial (included in the Comet distribution). However, I didn't manage to translate it into working ECliPSe code.

Yesterday I recalled that the MiniZinc gang had implemented a modulo predicate for testing the new policy of modulo in MiniZinc. See Division and Modulus Functions. The predicate int_mod along with int_div_mod is defined in div_mod.mzn (written by Peter Stuckey, September 2009).

It was then surprisingly easy to translate this to ECLiPSe code, probably since both MiniZinc and ECLiPSe are so declarative (which for example Comet - albeit very high level - is not).

So, here (modulo_propagator.ecl) is my translation of this predicate to ECLiPSe:
% syntactic sugar
:- op(500,xfy,'modulo').

% ...
modulo(X1,Y1,R1) :-
   X #= eval(X1),
   Y #= eval(Y1),
   R #= eval(R1),
       nonvar(X),nonvar(Y) -> 
           R is X mod Y
           Y #\= 0,
           UBXNeg is -UBX,
           LBXNeg is -LBX,
           D :: MinX..MaxX,
           X #= Y * D + R,
           -abs(Y) #< R, R #< abs(Y),
           MinX #=< D,
           D #=< MaxX
The lib(ic_kernel is for the low level predicates get_min and get_max for getting the min/max domain of a decision variable. The three eval at the beginning is to be able to use expressions in the arguments, e.g. as (as in averbach_1.4.ecl):
PDyer #= (Hosier-2) modulo 5,
The corresponding part in the Divisible by 9 .. 1 problem is just as I wanted it.
T[Base_I] modulo I #= 0
Well, I don't really know if this is the best (or even a good) implementation of the modulo operator in ECLiPSe, and I assume that it can be improved upon. However, it seems to work well for my purposes.

May 06, 2010

Some 40 new ECLiPSe models

During the last days I have published about 40 new ECLiPSe models on my ECLiPSe page. They are all listed below.

A major part are ports from my SICStus Prolog models that I wrote some months ago, and I have not changed much from the SICStus models. Also, most of them - in turn - was first written in MiniZinc (see my MiniZinc page).

However, some small puzzles are completely new. By a freaky coincidence two are some kind of weighting problems (for comparison, the corresponding MiniZinc model are also linked):

The new models

Here is all the new ECLiPSe models.


I think I have forgot to mention Helmut Simonis' great ECLiPSE ELearning Website, which includes 20 interesting chapters, most with video lectures. Even if the code examples are in ECLiPSe, the material is definitely of general interest for anyone who want to learn more about Constraint Programming.

March 07, 2010

New book: Antoni Niederliński: Programowanie w logice z ograniczeniami ("Programming in Logic with Constraints")

Some weeks ago Antoni Niederliński wrote to the ECLiPSe mailing list about his new book (in Polish) about constraint logic programming with ECLipSe: Programowanie w logice z ograniczeniami ("Programming in Logic with Constraints"), PKJS, Gliwice 2010, 308 pages. ISBN: 9788360716953.

The author was kind enough to send the book to me and I received it yesterday. Since I don't understand Polish, I have now just browsed the book and tried some of the examples. It is a challenge to read code where all variable names and comments are in a unknown language, however many of the them are standard examples or variations .

It is a beautiful book with nice color plates of the problem's solutions as well as the principles of constraints such as propagators, etc. There are also many examples that seems to be well explained in the text, and there are 69 accompanying ECLiPSe models which can be downloaded (see below). It would be nice if this book is translated to English, it would be a welcome addition to other introduction books to constraint (logic) programming since it contains many different examples with explanations. However, I don't know if the author have any such plans.

The book is presented in the (Polish) site: Translated to English by Google Translate: Logic programming with constraints - Gentle introduction to Eclipse:

[N]ew book: Anthony Niederliński, "Programming in logic with constraints. Gentle introduction to Eclipse," PKJS, Gliwice 2010, 308 + XVIII of the parties. The book contains:
* accessible lecture bases logic programming with constraints (CLP) for a free Eclipse Constraint Programming System, available through the Cisco-style Mozilla Public License
* descriptions and examples of basic methods of CLP with an emphasis on their intuitive understanding, and without the theoretical justification
* commented on a series of sample programs of increasing difficulty;

The book is intended for all those who want to quickly begin to set limits and optimal solutions for combinatorial and continuous problems using the mechanisms of CLP.

The contents of the book is Google translated here. It is slightly edited, and I have not been able to find a translation for some of the words.

Contents book "Programming in logic with constraints. Gentle introduction to the Eclipse"

Introduction, i
0.1 What is the book?, i
0.2 What is the logic programming with constraints?, Ii
0.3 Programming in logic with constraints and artificial intelligence, v
0.4 Programming in logic with constraints and knowledge engineering, vii
0.5 Programming in logic with constraints and operational research, viii
0.6 How was the book?, Ix
0.7 What the book contains?, Ix
0.8 How to use the book?, Xiii
0.9 A inconvenience Eclipse, xvi
0.10 Credits, xviii
1 In the beginning was the Prologue, 1
1.1 Elements of the Prologue, 1
1.2 Setting System 3-element, 8
1.2.1 Setting up a complete review of the method, 9
1.2.2 Setting method of searching the depths with standard relapses, 9
1.2.3 Setting the optimum, 15
1.3 Golfers, 18
1.4 Three balls, 21
1.5 Who killed him?, 24
1.6 Hetmani [n-queens problem] - a complete overview, 26
1.7 Hetmani [n-queens problem] - searching the depths of the standard recurrences, 28
1.8 Examination - searching the depths of the standard recurrences, 31
1.9 Incorrect wheel in the prologue, 36
1.10 How to become his own grandfather?, 37
1.11 Maze, 39
1.12 Field of mine, 42
1.13 The man-wolf-goat-cabbage, 46
1.14 Missionaries and cannibals, 49
1.15 Towers of Hanoi, 54
1.16 Decanting [3-jugs problem], 57
2 CLP restrictions for elementary feasible solutions (63
2.1 Limitations and areas of elementary variables, 63
2.2 What languages are different from Prolog CLP?, 63
2.2.1 n-Queens Problem in the CLP, 64
2.2.2 Exploration and Forward Checking method of propagation, 65
2.2.3 Exploration and propagation method of Forward Looking Ahead + Checking, 68
2.3 heuristic search, 69
2.4 Techniques zgodnościowe [about consistency], 72
2.5 Propagation of the failure of limitations, 73
2.6 Propagation of constraints gives a solution, 76
2.7 Who was with whom? - Propagation, 81
2.8 Students and languages - propagation, 83
2.9 Propagation of exploration: three equations in whole numbers, 89
2.10 Golfers again, 91
2.11 The guards - search and propagation, 93
2.12 Examination - search and propagation, 94
2.13 Hetman - search and propagation, 96
2.14 Setting - search and propagation, 97
2.15 collaborators and undercover Etosowcy The opposition, 99
3.1 Declarations module, 103
3.2 Limitation 'alldifferent (?Lists)', 104
3.3 Limitation 'element (?Index, ++List,?Value), 106
3.4 Send More Money, 106
3.5 Who was with whom?, 107
3.6 Golfers once again, 110
3.7 Three bullets once again, 113
3.8 Hetman [n-queens], 116
3.9 Five halls, 117
3.10 The ten classrooms, 120
3.11 All for All, 126
3.12 Seven of machinery - the seven operations, 131
3.13 Three machines - three of the five operations, 134
3.14 Three machines - five operations, 135
3.15 Using the data, 138
3.15.1 Structures and arrays, 138
3.15.2 Recursion and iteration, 141
3.16 Scalar product, 147
3.17 Hetman [n-queens] again, 148
3.18 Sudoku, 149
3.19 Hetman [n-queens] again, 152
4 CLP restrictions for elementary optimal solutions, 153
4.1 General, 153
4.2 Improved Branch and Bound, 154
4.2.1 The optimal position commanders - a standard Branch and Bound, 155
4.2.2 The optimal position commanders - Branch and Bound & Forward Checking, 156
4.2.3 The optimal position commanders - Branch and Bound + Forward Looking Ahead Checking, 157
4.3 The fundamental predicates, 158
4.3.1 The predicate 'bb min()', 158
4.3.2 The predicate 'search()', 160
4.4 Setting the optimal, 162
4.5 Optimizing load seven machines 165
4.6 Plan of the transport of coal 1, 168
4.7 Plan of the transport of coal 2, 171
4.8 Plan of the transport of coal 3, 173
4.9 Coloring maps, 176
4.10 knapsack problem 1, 177
4.11 Urzeczowione limitations, 180
4.12 Restrictions on the harvest, 181
4.13 knapsack problem 2, 185
4.14 Wholesale and consumers - 1, 186
4.15 Wholesale and consumers - 2, 191
4.16 Elementary scheduling, 194
4.16.1 resource constraints - the crew, 195
4.16.2 Lights and misery optimization, 199
4.16.3 Limitations kolejnośsciowe - building a house, 202
4.16.4 Limitations [disjunctive] - limited resources, 206
4.17 Optimization constraints and contradictions - photo, 209
4.18 shall appoint a parliamentary committee, 213
4.19 We are fighting for even udeszczowienie, 216
4.20 How to cut optimally?, 220
4.21 Most Send Money, 222
5 CLP restrictions for global optimal solutions, 225
225 5.1 Limitation of 'cumulative ()', 225
5.2 Cumulative scheduling 1, 227
5.3 Cumulative Scheduling 2, 228
5.4 Limitation of 'disjunctive ()', 230
5.5 [Disjunctive] scheduling 1, 231
5.6 We read newspapers 1, 232
5.7 We read newspapers 2, 238
5.8 We read newspapers 3, 242
5.9 Mount bicycles, 247
5.10 unloads and loads the ship, 262
5.11 An example of a very difficult - benchmark MT10, 269
6 CLP for continuous variables, 287
6.1 The curse and blessing of compound interest, 288
6.1.1 On retirement as a millionaire - 1, 289
6.1.2 On retirement as a millionaire - 2, 290
6.1.3 Ah, those mortgages!, 292
6.2 Wholesalers - suppliers, 293
6.3 Mixing oils, 297
6.4 How do I earn and not narobić?, 299

The examples can be downloaded here here.

End note

The book contain at least one reference to my own ECLiPSe page (attributed as "Constraint Programming Blog" in the reference section) which is quite fun since it is the first time my constraint programming blog/sites are referenced in a book. The example that starts on page 222 is attributed to my send_most_money.ecl model.

Here is the original text in Polish, as far as I have been able to type the different accents and strikes:

Popularna łamigłówka Send More Money (patrz rozdzial 3.4) ma rowniez swą wersje optymalizacyjna o nazwie Send Most Money, ktorej celem jest maksymalizacja wartosci zmiennej Money. Odpowiedni program 4_20_smm.ecl, zaczerpnięty z witryny [Kjellerstrand-10], jest postaci:

Google Translate translates the text as:

The popular puzzle Send More Money (see Chapter 3.4) also has its version of optimization, called Send Money Bridge, whose objective is to maximize the value of the variable Money. 4_20_smm.ecl appropriate program, taken from the site [Kjellerstrand-10], is of the form:


July 21, 2009

24 new ECLiPSe models

Here are 24 new ECLiPSe models, converted from my Comet or MiniZinc models. As always, the models contains more information about the problem. As of writing, My ECLiPSe page contains about 110 models.

3_jugs.ecl: 3 jugs problem, MIP model, eplex
a_round_of_golf_propia.ecl: A round of golf puzzle (Dell Logic Puzzles), Propia version
blending.ecl: Blending problem (OPL example)
crypta.ecl: crypta, alphametic problem (standard Prolog/CLP benchmark)
crypto.ecl: crypto, alphametic problem (standard Prolog/CLP benchmark)
distribute.ecl: (Decomposition of) global constraint distribute.
donald_gerald.ecl: Alphametic puzzle DONALD + GERALD = ROBERT
four_islands.ecl: Four islands puzzle (Dell Logic Puzzles)
langford.ecl: Langford's number problem (CSPLib problem 24)
langford_propia.ecl: Langford's number problem (CSPLib problem 24), Propia version
pigeon_hole.ecl: Pigeon hole problem
place_number_puzzle.ecl: Place number puzzle
rabbits.ecl: Rabbits problem (Van Hentenryck, OPL book)
spreadsheet.ecl: Simple "spreadsheet" example (Apt)
square_root_of_wonderful.ecl: Square Root of Wonderful (Martin Gardner)
stable_marriage.ecl: Stable marriage problem (examples from Van Hentenryck's OPL book, and MathWorld)
subset_sum.ecl: Subset sum problem (Murty)
talisman_square.ecl: Talisman square
traffic_lights.ecl: Traffic lights problem (CSPLib problem 16)
tunapalooza.ecl: Tunapalooza puzzle (Dell Logic Puzzles)
volsay1.ecl: Volsay production problem (Van Hentenryck, The OPL Book), eplex model
volsay2.ecl: Volsay production problem (Van Hentenryck, The OPL Book), eplex model, slightly different from volsay1.ecl
volsay3.ecl: Volsay production problem (Van Hentenryck, The OPL Book), eplex model, more general than volsay1.ecl and volsay2.ecl
warehouse.ecl: Warehouse location problem (OPL example)

July 13, 2009

26 new ECLiPSe models, and some changed

Here are my new ECLiPSe models. Almost all are more direct ports of my MiniZinc and Comet models, or at least, they use the same principal approach to the problem. In these ECLiPSe models I have experimented quite a lot, since I like to play with all the bells & whistles in ECLiPSe.

When I started to program in ECLiPSe I tend to use arrays (and arrays of arrays) dominantly since I wanted to access elements via the syntactic sugar of [] (to mimic MiniZinc/Comet) . But accessing elements via arrays is not always possible, e.g. when both the index variable and the array/matrix contains decision variables, and - as far as I know - the only possible way of accessing these structures are via listut:nth1 on lists. Therefore later models tend to use lists (and nth1) more.

Update: A comment about this. Some days later (2009-07-16) I found that often (but not always) array access using [] on an array of decision variables and index values also decision variables works when lib(propia) is just loaded (lib(propia)), even if it is not actually used (i.e. there is not explicit goal such as Goal infers most). I have already published some variants which is then called _propia.ecl (maybe _array would have been better...). For example a_round_of_golf_propia.ecl is so changed. Also, I did a stable marriage model (stable_marriage.ecl) with array access in this way which is much easier to model and understand, than a list/nth1 version..

New ECLiPSe models

a_round_of_golf.ecl: A Round of Golf (Dell Logic Puzzles)
a_round_of_golf_propia.ecl: A Round of Golf (Dell Logic Puzzles) (arrays and Propia)
added_corner.ecl: Added corner puzzle
all_interval.ecl: All interval problem (series), (CSPLib problem 7)
among.ecl: (Decomposition of) global constraint among
among_seq.ecl:(Decomposition of) global constraint among_seq
building_blocks.ecl: Building blocks puzzle (for a more general solution see labeling_dice.ecl
circuit.ecl: (Decomposition of) global constraint circuit
clique.ecl: (Decomposition of) global constraint clique
covering_opl.ecl: Set covering, selecting workers (from OPL example covering.mod)
crossword2.ecl: Crossword solving (standard constraint programming example)
cumulative_test.ecl: Test of the built in cumulative constraint
eq10.ecl: Standard benchmark problem
eq20.ecl: Standard benchmark problem
game_theory_taha.ecl: Game theory, zero sum game using eplex (from Taha, Operations Research)
global_cardinality.ecl: (Decomposition of) global constraint global cardinality count (somewhat limited)
global_contiguity.ecl: (Decomposition of) global contiguity
hidato.ecl: Hidato puzzle
inverse.ecl: (Decomposition of) global constraint inverse
kenken2.ecl: KenKen, a grid puzzle
labeled_dice.ecl: Labeled dice puzzle (contains building_blocks.ecl as a problem instance)
safe_cracking.ecl: Safe cracking problem
set_covering_skiena.ecl: Set covering problem (Skiena)
set_partition.ecl: Set partition problem
ski_assignment.ecl: Ski assignment problem
sliding_sum.ecl: (Decomposition of) global constraint sliding sum
stable_marriage.ecl: Stable marriage model (using arrays) sudoku_gcc.ecl: Sudoku, comparison of using ic_global:alldifferent and my decompositions of global cardinality and alldifferent (the rest of the code is from ECLiPSe's Sudoku example)

Some changed models

Here are some changed models.

Who killed Agatha? - now using suspend
Model: who_killed_agatha.ecl

Last I wrote about the problem with accessing for the variable matrices (as arrays):
Hates[Killer,Victim] #= 1,
Richer[Killer, Victim] #= 0
When using this syntax where Hates, Killer, and Victim are all decision variables, an instantiation fault error was thrown. Earlier I tried some remedies for this (see the cited post).

The updated version uses suspend instead:
suspend(Hates[Killer,Victim] #= 1, 2, Killer->inst),
suspend(Richer[Killer, Victim] #= 0, 2, Killer->inst),
This means that the solver suspends the constraints until Killer is instantiated. And in this case it actually works.

suspend is very powerful and is normally used for creating constraints (propagators). I haven't done this very much yet, but it's in the plans.

for loops: bin_packing2
As noted in the updates of Some new ECLiPSe models, e.g. Minesweeper I added a 4'th version of the foreach loop:
Version 4
Use foreach to collect S and then use sum.

    param(Weights,Bins,N,Capacity) do
         param(Weights,Bins,B) do
              S = Weights[J]*(Bins[J] #= B)
         sum(Sum) #=< Capacity
Again, thanks to Joachim Schimpf for reminding me that one larger constraint sum(Sum) #=< Capacity is probably better than more small constraints, such as alot of S #= Weights[J]*(Bins[J] #= B) (note the #= here).

ECLiPSe now support MiniZinc version 1.0

Since ECLiPSe release 6.0_92 (or later) there is now support for MiniZinc version 1.0. This is great since the ic solver has in some cases been the only solver for some of the my MiniZinc models, e.g. when there is multiplication of float variables. This solver is also often very fast.

It is actually three solvers, each with its special strength: See the following modules for more about how to use these solvers: My usage
As indicated in MiniZinc/FlatZinc support in SICStus Prolog version 4.0.5, when running a MiniZinc with an ECLiPSe solver, the following is created inside a general Perl program with the variables:
$model: the MiniZinc model
$solver: one of ic, fz, or eplex
$num_solutions: number o f solutions (0 for all solutions)

go :-
  minizinc:mzn_run('$model', zn_options{solver:fzn_$solver, solutions:$num_solutions}).
It is then saved as a file (e.g. model.ecl or something like that) and is then run from the shell with
eclipse  -b model.ecl -e go
See also
My ECLiPSe Page for my "real" ECLiPSe models.

July 03, 2009

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 
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),
    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),
    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
     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.
    param(Weights,Bins,N,Capacity) do
         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.


Model: minesweeper.ecl
This is a general Minesweeper solver given problem instances of the following format:
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
            % 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


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)


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.

June 29, 2009

Constraint programming in ECLiPSe Constraint Programming System

This last few weeks I have programmed in ECLiPSe Constraint Logic Programming system more systematically than before. For example, many of my "learning models" has now been implemented in ECLiPSe. These and other ECLiPSe models is now collected at My ECLiPSe Page.


ECLiPSe is very well documented system with a couple of online books for different aspects of the system. For more info see:
  • Documentation
  • Examples
  • The book Constraint Programming using ECLiPSe by Krzysztof R. Apt and Mark Wallace, Cambridge University Press, 2006, ISBN: 9780521866286.
  • Mailing lists

My ECLiPSe page

There is now a My ECLiPSe Page with so far 46 ECLiPSe models (see below). Expect that this number will increase.

Arrays and loops

In these models I have almost exclusively used the following two really great features of ECLiPSe, which are extensions to Prolog proper: For logical loops, also see Logical loops by Joachim Schimpf (2002). A quite recent discussion in comp.lang.prolog, foreach for Prolog discussed this more.

Arrays are very handy to use, especially in combinations with loops, see below for an example. Using loops and arrays means that I have been able to port my models quite easy, often directly from the MiniZinc and/or Comet models. This means that there are very few traditional Prolog recursive predicates in these models. Note that loops don't require arrays, they are as powerful with plain old lists, and ECLiPSe has of course also support for traditional Prolog logic programming.

As I understand it, SICStus Prolog will soon support logical loops (inspired by the ECLiPSe approach). That's great!

Example: Diet problem

For a starter, let's implement a simple diet's problem, where we want to minimize the cost of different food given that the nutrition constraints is met. This problem is in diet.ecl and is shown below.
:- lib(ic).
:- lib(branch_and_bound).

go :-
        % fetch the data
        data(Price, Limits, Calories, Chocolate, Sugar, Fat),

        % Xs is the decision variable containing the number
        % of nutrition to buy
        length(Calories, Len), % for setting the length of Xs
        length(Xs, Len),       % set the same length for Xs 
 	Xs :: 0..10,           % domains for Xs
        % convert Limits to LimitArray (so we can use LimitArray[i] below)
        length(Limits, LimitLength),
        dim(LimitArray, [LimitLength]),
        collection_to_list(LimitArray, Limits),

        % these constraints calculates: sum(Xs[i]*Y[i]) >= limit 
        Xs * Calories  #>= LimitArray[1], % 500,
        Xs * Chocolate #>= LimitArray[2], %   6,
        Xs * Sugar     #>= LimitArray[3], %  10,
        Xs * Fat       #>= LimitArray[4], %   8,

        % search: minimize the sum of Xs * Price
        XSum #= Xs * Price, 


        writeln([XSum, Xs]).

% data
        [ 50, 20, 30, 80], % price in cents for each nutrition
        [500,  6, 10,  8], % limits, requirements for each nutrition
                           % type

        % nutrition for each product
        [400, 200, 150, 500], % calories
        [3,2,0,0],            % chocolate
        [2,2,4,4],            % sugar
        [2,4,1,5]             % fat
Note especially the construct Total = List1 * List2 which is a syntactical sugar for following (using MiniZinc/Comet syntax):
Total = sum(i from 1..n) (List1[i]*List2[i])

Using loops and arrays: Quasigroup completion

Quasigroup completion is a problem where starting from a not fully completed Latin square, and the object is to complete this square. quasigroup_completion.ecl is a model for this problem.

The model has two principal parts: * stating the problem instances, which I have done as a matrix using an array of arrays. The [](....) is used for declaring arrays. Here is the first problem:
problem(1, []([](1, _, _, _, 4),  
              [](_, 5, _, _, _),
              [](4, _, _, 2, _),
              [](_, 4, _, _, _),
              [](_, _, 5, _, 1))).
* the model
Below is the code for solving the problem and filling out the squares, as well as keep the Latin square condition (for all rows and all columns there must be unique numbers):
solve(ProblemNum) :-
        problem(ProblemNum, Problem),
        dim(Problem, [N,N]), % get the size of the problem
        Problem[1..N,1..N] :: 1..N,
        (for(I, 1, N), param(Problem, N) do
Here the loop (for(I,1,N)...) is used for looping through all the rows of the matrix. Note how easy it is to use "slices" of the matrix, e.g. Problem[I,1..N].

Comment: This problem is really a subset of solving a Sudoku. The ECLiPSe distribution has an example for solving these problems: sudoku.ecl.txt.

Another example: XKCD knapsack problem

The xkcd knapsack problem is implemented in xkcd.ecl. The models show some different approaches.

Using "plain" lists and the syntactic sugar for multiplying two lists is is quite short:
go4 :-
        Prices = [215, 275, 335, 355, 420, 580],
        Total = 1505,
        length(Prices, Len),
        length(Xs, Len),
        Xs :: [0..10],
        Total #= Xs * Prices,
        writeln([Total, Xs]).
The multiplication syntactic sugar don't work with arrays, but we can convert the array (a "collection") to a list with collection_to_list/2. This version also minimize the number of dishes:
go3 :-
        Prices = [](215, 275, 335, 355, 420, 580), % Prices for the dishes
        Total = 1505,       % multiply 15.05 with 100 for integer usage
        dim(Prices, [Len]), % get length of Prices
        dim(Xs, [Len]),     % same length of Xs 
        Xs :: [0..10],      % domain of Xs
        % get all solutions
        knapsack(Prices, Total, Xs),

        collection_to_list(Xs, XsList),
        sum(XsList, NumDishes),
        writeln([Total, Xs, NumDishes]).
Another approach when using arrays is to use for loops which is shown in the knapsack predicate below. Here for(I,1,Len) is used for incrementing the index counter, and then fromto does the actual summation. Note that fromto is very versatile and can be used for other things. See the documentation for more info.
% Sum the totals: Total = Prices * Xs
knapsack(Prices, Total, Xs) :-
        dim(Prices, [Len]), % get the length of the array
        ( for(I, 1, Len), fromto(0, S1, S2, Total), param(Prices, Xs) do
              S2 #= S1+Prices[I]*Xs[I]

% simple version: Total = 1505
% This use the array representation
go :-
        Prices = [](215, 275, 335, 355, 420, 580), % Prices for the dishes
        Total = 1505,       % multiply 15.05 with 100 for integer usage
        dim(Prices, [Len]), % get length of Prices
        dim(Xs, [Len]),     % same length of Xs 
        Xs :: [0..10],      % domain of Xs
        findall(Xs, knapsack(Prices, Total, Xs), L),
        length(L, LLen),    % length of solutions
        writeln([total:Total, num_solutions:LLen, solutions:L]).

Some more comments about ECLiPSe

Here are some more comments of ECLiPSe
  • ECLiPSe is based on Prolog, which is a programming language that has fascinated me for a long time.
    struct (records) is another great extension, but I have just used it for a map coloring example map.ecl.
  • There are not very many built in global constraints in ECLiPSe (compared to SICStus Prolog) which is a pity. I have plans to implement decompositions for some global constraints from Global Constraint Catalog.
  • Almost all of the implemented model has used the ic library. I have yet to study (and use) the other libraries, eplex, suspend, propia, and repair which all seem very interesting.
  • there are many useful examples, almost all of them use loops and arrays. A wish: More examples of how to use the eplex library would be nice.
  • MiniZinc/FlatZinc: ECLiPSe has a great support for MiniZinc/FlatZinc, but unfortunately it - as of writing - don't support the recent version of MiniZinc (version 1.0).
  • tkECLiPSe: This is a GUI in TclTk, but I have not used it much (I'm a Emacs guy). There are some visualizations libraries that should be tested more.
  • ECLiPSe is a large system, see the Documentation for the full story.

My ECLiPSe models

I have implemented most of my "learning models" in ECLiPSe. Some are not yet done and will hopefully come later. Also, there are some older experiments in recreational mathematics. See My ECLiPSe Page.

As indicated above, most of these models use arrays and logical loops instead of the traditional Prolog recursion technique. I really like using these extensions since it is much easier to state the constraints, at least of me coming from MiniZinc, Comet and other non-logical programming.

June 24, 2009

My old swedish blog posts about constraint programming translated (via Google)

Before starting this blog (i.e. My Constraint Programming blog) late December 2008, I blogged about constraint programming in my Swedish blog hakank.blogg). Translations of those Swedish blog post has not been collected before, and now it is time.

So, here are links to most of the blog posts from the category Constraint Programming, translated via Google's Language Tools. Most of the translation is intelligible, but if you have some questions about some particular, please feel to mail me: for more information.

November 4, 2005
Swedish: Sesemans matematiska klosterproblem samt lite Constraint Logic Programming
Translated: Sesemans kloster mathematical problems and little Constraint Logic Programming ("kloster" means "convent").

April 18, 2006
Swedish: Choco: Constraint Programming i Java
Translated: Choco: Constraint Programming in Java

The two post above was written when I had just a cursory interest in constraint programming. From about February 2008 and onward, it became my main interest.

April 5, 2008
Swedish: Constraint Programming: Minizinc, Gecode/flatzinc och ECLiPSe/minizinc,
Translated: Constraint Programming: Minizinc, Gecode / flatzinc and ECLIPSE / minizinc.

April 14, 2008
Swedish: MiniZinc-sida samt fler MiniZinc-exempel
Translated: MiniZinc-page and multi-MiniZinc example.

April 21, 2008
Swedish: Applikationer med constraint programming, lite om operations research samt nya MiniZinc-modeller
Translated: Applications of constraint programming, a little of operations research and new MiniZinc models

April 26, 2008
Swedish: Ett litet april-pyssel
Translated: A small-craft in April (a better translation would be "A small April puzzle")

April 27, 2008
Swedish: Mitt OpenOffice Calc-/Excel-skov
Translated: My Open Office Calc-/Excel-skov (better translation: My Open Office Calc-/Excel period).

May 26, 2008
Swedish: Några fler MiniZinc-modeller, t.ex. Smullyans Knights and Knaves-problem
Translated: Some more MiniZinc models, eg Smullyans Knights and Knaves-problem Smullyans Knights and Knaves problem

June 2, 2008
Swedish: MiniZinc/FlatZinc version 0.8 släppt
Translated: MiniZinc / FlatZinc version 0.8 released

June 2, 2008
Swedish: Nya MiniZinc-modeller, flera global constraints, däribland clique
Translated: New MiniZinc models, several global constraints, including Clique

June 5, 2008
Swedish: Mats Anderssons tävling kring fotbolls-EM 2008 - ett MiniZinc-genererat tips
Translated: Mats Andersson racing around championship in 2008 - a MiniZinc-generated tips (it is about a competition how to predict Soccer World Cup 2008 using MiniZinc)

June 24, 2008
Swedish: Tre matematiska / logiska pyssel med constraint programming-lösningar: n-puzzle, SETS, M12 (i MiniZinc)
Translated: Three mathematical / logical craft with constraint programming solutions: n-puzzle, SETS, M12 (in MiniZinc) ("craft" should be translated to "puzzles")

June 24, 2008
Swedish: MiniZinc-nyheter
Translated: MiniZinc news

June 29, 2008
Swedish: Gruppteoretisk lösning av M12 puzzle i GAP
Translated: Group Theoretical solution of the M12 puzzle in GAP (well, this is not really a constraint programming solution, but it is another way of solving the M12 puzzle blogged about in June 24)

June 30, 2008
Swedish: Gruppteoretisk lösning av M12 puzzle i GAP - take 2
Translated: Group Theoretical solution of the M12 puzzle in GAP - take 2

July 4, 2008
Swedish: Martin Chlond's Integer Programming Puzzles i MiniZinc
Translated: Martin's Chlond Integer Programming Puzzles in MiniZinc

July 7, 2008
Swedish: Fler MiniZinc modeller kring recreational mathematics
Translated: More MiniZinc models on recreational mathematics

July 20, 2008
Swedish: Fler constraint programming-modeller i MiniZinc, t.ex. Minesweeper och Game of Life
Translated: More constraint programming models in MiniZinc, eg Minesweeper och Game of Life Minesweeper and the Game of Life

August 17, 2008
Swedish: JaCoP - Java Constraint Programming solver
Translated: JaCoP - Java Constraint Programming solver

September 14, 2008
Swedish: Constraint programming i Java: Choco version 2 släppt - samt jämförelse med JaCoP
Translated: Constraint programming in Java: Choco version 2 released - and comparison with JaCoP

September 28, 2008
Swedish: Constraint programming: Fler MiniZinc-modeller, t.ex. Martin Gardner och nonogram
Translated: Constraint programming: More MiniZinc models, eg Martin Gardner och nonogram Martin Gardner and nonogram

December 27, 2008
Swedish: Constraint programming-nyheter samt nya MiniZinc-modeller
Translated: Constraint programming, news and new MiniZinc models

December 29, 2008
Swedish: My Constraint Programming Blog
Translated: My Constraint Programming Blog

After that, entries about constraint programming at my swedish blog posts where just summaries of the stuff written here at My Constraint Programming blog.

May 05, 2009

Learning constraint programming - part II: Modeling with the Element constraint

As indicated last in Learning constraint programming (languages) - part I here are some findings when implementing Crossword, Word square, and Who killed Agatha?. See links below for the implementations.

The first constraint programming system i learned after constraint logic programming in Prolog was MiniZinc. When implemented the problems below I realized that I have been quite spoiled by using MiniZinc. The way MiniZinc (and also Comet) supports the Element constraint, i.e. access of variable arrays/matrices, is very straightforward in these systems and it doesn't matter whether the array to access is an array of integers or of non-variable variable integers. In the Java (Choco, JaCoP) and C++ systems (Gecode), however, this is another matter. Due to different circumstances I have not implemented these models in Gecode/R.

Element in MiniZinc and Comet
Accessing arrays and matrices in MiniZinc and Comet is simply done by using the [] construct, no matter what the type of the array or the index are (I assume integers and variable integers here). For the other systems we must explicitly use the Element constraint (called nth in Choco).


This is a standard constraint programming problem, used as a running example in Apt's great book Principles of Constraint Programming. Here is a formulation of the problem (stated differently than in the book):
Place the words listed below in the following crossword. The '#' means a blocked cell, and the numbers indicate the overlappings of the words.

      1   2   3   4   5
  1 | 1 |   | 2 |   | 3 |
  2 | # | # |   | # |   |
  3 | # | 4 |   | 5 |   |
  4 | 6 | # | 7 |   |   |
  5 | 8 |   |   |   |   |
  6 |   | # | # |   | # |
We can use the following words


MiniZinc: crossword.mzn
Gecode/R: (Not implemented)
Gecode: crossword.cpp

Note: I have seen more general models for solving crossword problems in Choco, JaCoP, Gecode/R, and Gecode with constructions other that the simple Elements used here. Since I wanted to compare the same way of solving the problem using the same Element-construct this may be an unfair comparison between the systems. Well, this is at least a finding how to implement this problem by Element...

Explanation of variables
The matrix A is the individual chars of the words (Comet variant):
int A[1..num_words,1..word_len] = 
   [h, o, s, e, s], //  HOSES
   [l, a, s, e, r], //  LASER
   [s, a, i, l, s], //  SAILS
   [s, h, e, e, t], //  SHEET
   [s, t, e, e, r], //  STEER
   [h, e, e, l, 0], //  HEEL
   [h, i, k, e, 0], //  HIKE
   [k, e, e, l, 0], //  KEEL
   [k, n, o, t, 0], //  KNOT
   [l, i, n, e, 0], //  LINE
   [a, f, t, 0, 0], //  AFT
   [a, l, e, 0, 0], //  ALE
   [e, e, l, 0, 0], //  EEL
   [l, e, e, 0, 0], //  LEE
   [t, i, e, 0, 0]  //  TIE
overlapping is the matrix of the overlapping cells)
This is the Comet version:
 [1, 3, 2, 1],   //  s
 [1, 5, 3, 1],   //  s 
 [4, 2, 2, 3],   //  i
 [4, 3, 5, 1],   //  k
 [4, 4, 3, 3],   //  e
 [7, 1, 2, 4],   //  l
 [7, 2, 5, 2],   //  e
 [7, 3, 3, 4],   //  e
 [8, 1, 6, 2],   //  l
 [8, 3, 2, 5],   //  s
 [8, 4, 5, 3],   //  e
 [8, 5, 3, 5]    //  r
E is the variable array of which the word to use for the different overlappings. This is in fact the only variable (array) that is needed in the problem, apart from the utility/convenience variables.

The main constraint for the crossword example in each system is stated thus:

forall(i in 1..num_overlapping) (
   A[E[overlapping[i,1]], overlapping[i,2]] =  A[E[overlapping[i,3]], overlapping[i,4]]
  forall(i in 1..num_overlapping) {[E[overlapping[i,1]], overlapping[i,2]] ==  A[E[overlapping[i,3]], overlapping[i,4]], onDomains);
Note that Choco has a special Element which support two dimensional arrays (matrix), which we use.
for(int I = 0; I < num_overlapping; I++) {
  IntegerVariable tmp = makeIntVar("tmp" + I, 1, 26);
  M.addConstraint(nth(E[overlapping[I][0]], W[overlapping[I][1]], AX, tmp));
  M.addConstraint(nth(E[overlapping[I][2]], W[overlapping[I][3]], AX, tmp));
Here we had used some trickery by using a transposed version of the word matrix since JaCoP has no special Element constraint for two dimensional arrays.
for (int I = 0; I < num_overlapping; I++) {
   FDV tmp = new FDV(store, "TMP" + I, 0, num_words*word_len);
   store.impose(new Element(E[overlapping[I][0]], words_t[overlapping[I][1]], tmp));
   store.impose(new Element(E[overlapping[I][2]], words_t[overlapping[I][3]], tmp));
This is more complicated compared to the two Java systems since in Gecode we use an array (of length rows*cols) to simulate the matrix. (There is a Matrix "view" in Gecode but the indices must be of type integer, not IntVar, so it can not be used.) Also, the constraints plus and mult takes IntVar as argument.

The first overlapped crossing is "expanded" like this (Gecode is 0-based):
   A[E[overlapping[i,0]], overlapping[i,1]] // MiniZinc/Comet
   a1 = A[ E[I*4+0] * word_len + overlapping[I*4+1]] // Gecode
Here is the complete code. The comments hopefully explains what is going on.

First we define an utility function for accessing the element according to the above principle.
 * Special version of element for an array version of a "matrix" words,
 * E is an integer variable array, C is an array of IntVars for
 * the offset j in the words "matrix".
 * The call 
 *    element_offset(*this, words, E[i], word_len_v, C[j], res, opt.icl());
 * corresponds to:
 *    res = words[E[i], j] --> words[E[i]*word_len+J]
void element_offset(Space& space,
                   IntArgs words,
                   IntVar e,
                   IntVar word_len,
                   IntVar c,
                   IntVar res,
                   IntConLevel icl = ICL_DOM) {

      element(space, words, 
                        word_len, icl), 
                   c, icl), 
              res, icl);

The function is then used as follows:
for(int I = 0; I < num_overlapping; I++) {
   IntVar e1(*this, 0, num_overlapping*4);
   IntVar e2(*this, 0, num_overlapping*4);

   IntVarArray o(*this, 4, 0, num_overlapping*4);
   for(int J = 0; J < 4; J++) {
     post(*this, o[J] == overlapping[I*4+J], opt.icl());

   element(*this, E, o[0], e1, opt.icl());      // e1 = E[I*4+0]
   element(*this, E, o[2], e2, opt.icl());      // e2 = E[I*4+2]

   IntVar a1(*this, 0, num_words*word_len);
   element_offset(*this, A, e1, word_len_v, o[1], a1, opt.icl());
   element_offset(*this, A, e2, word_len_v, o[3], a1, opt.icl());
(The same element_offset function is also used in the word_square problem below.) It took quite a time to get the function and temporary variables (and their domains) right. With training (and the element_offset as a skeleton) similiar problems should be easier to implement.

Note: this is not a bashing of Gecode. Gecode is a great system and it happens that for this specific problem, Gecode does not has the appropriate support. I should also mention that it was a long time since I programmed in C++ and am little rusty.

As mentioned earlier, I have been very spoiled by the MiniZinc (and Comet) constructs. Also: I'm a very 'lazy' person (in the Perl sense of the word lazy) and likes the agile programming languages - Perl, Ruby, Python etc - much for their high level constructs.

Word square problem

The word problem is a cousin to the crossword problem, and is described in Wikipedia's Word_square:
A word square is a special case of acrostic. It consists of a set of words, all having the same number of letters as the total number of words (the "order" of the square); when the words are written out in a square grid horizontally, the same set of words can be read vertically.
An example of order 7 found by the Comet model where we see that the first row word (aalborg) is also the first column word.



Here are the models for solving the Word square problem:
MiniZinc: word_square.mzn
Gecode/R: (Not implemented it Gecode/R)
Gecode: word_square.cpp

It is somewhat easier than the crossword problem. As before, E is the array of the index of the words to use, and words is an matrix of the words. Also, these models is an experiment of how to read a file, the word list /usr/dict/words (standard on Unix/Linux systems).

forall(I, J in 1..word_len) (
  words[E[I], J] = words[E[J],I]
  forall(i in 1..word_len) {
    forall(j in 1..word_len) { [E[i], j] == words[E[j],i], onDomains);
// The overlappings (crossings).
// Note that we use a transposed word matrix for the Element.
for(int i = 0; i < word_length ; i++) {
    for(int j = 0; j < word_length ; j++) {
        // Comet: words[E[i], j] ==  words[E[j],i]
        FDV tmp = new FDV(store, "tmp" + i + " " + j, 0, dict_size);
        store.impose(new Element(E[i], words[j], tmp));
        store.impose(new Element(E[j], words[i], tmp));
// Constants for the nth constraint below
IntegerVariable [] C = new IntegerVariable[dict_size];
for (int I = 0; I < word_length; I++) {
    C[I] = makeIntVar("C"+I, I,I);

// The overlappings (crossings)
for(int I = 0; I < word_length ; I++) {
    for(int J = 0; J < word_length ; J++) {
        // Comet: words[E[i], j] ==  words[E[j],i]
        IntegerVariable tmp = makeIntVar("tmp" + I + " " + J, 0, dict_size);
        M.addConstraint(nth(E[I], C[J], words, tmp));
        M.addConstraint(nth(E[J], C[I], words, tmp));
Note that this model use the same function element_offset that was used in the Crossword problem. It took some time to realize that it also could be used here.
// convenience variables for the element constraints below
// since element, plus, and mult wants IntVars.
IntVar word_len_v(*this, word_len, word_len);
IntVarArray C(*this, word_len, 0, word_len-1);
for(int i = 0; i < word_len; i++) {
  rel(*this, C[i], IRT_EQ, i, opt.icl());

for(int i = 0; i < word_len; i++) {
  for(int j = 0; j < word_len; j++) {
    // words[E[i], j] ==  words[E[j],i]

    IntVar tmp(*this, 0, num_words);

    // tmp == words[E[i], j] --> words[E[i]*word_len+j]
    element_offset(*this, words, E[i], word_len_v, C[j], tmp, opt.icl());

    // tmp == words[E[j], i]  --> words[E[j]*word_len+i]
    element_offset(*this, words, E[j], word_len_v, C[i], tmp, opt.icl());

Who killed Agatha?

This is a standard benchmark for theorem proving, also known as The Dreadsbury Mansion Murder Mystery.

Problem formulation from The h1 Tool Suite
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?
Originally from F. J. Pelletier: Seventy-five problems for testing automatic theorem provers., Journal of Automated Reasoning, 2: 191-216, 1986.


MiniZinc: who_killed_agatha.mzn
JaCoP :
JaCoP :
Gecode: who_killed_agatha.cpp

In Some new Gecode models I wrote about the findings in implemented this problem in Gecode and compared to Comet/MiniZinc.

The models use two 3x3 matrices for representing the two relations hates and richer with 0..1 as domain (i.e. boolean). The Element constraints is used for implementing the condition A killer always hates, and is no richer than his victim. where the_killer is an integer variable; the_victim is in some models replaced by agatha (the integer 0). The interesting thing here is that at least one of the indices are integer variables, which caused the difficulties in the two problems above.

These models also use a lot of boolean constructs. A comparison of how these are implemented in the different CP systems may be described in a future blog post.

hates[the_killer, the_victim] = 1 /\
richer[the_killer, the_victim] = 0
Comet:[the_killer, the_victim] == 1);[the_killer, the_victim] == 0);
Note: In the models below I have simplified the problem by using agatha (defined as the integer 0) instead of the integer variable the_victim. This is not a problem since we know that Agatha is the victim, and is the reason why the Element is easier to use than for Crossword and Word square.

JaCoP variant 1 (no Element):
JaCoP don't have a direct support for the case when the index i (in matrix[i][j]) is an integer variable so the first variant of modeling the condition A killer always hates, and is no richer than his victim. does not use Element at all. In we simply loop over all integers (0..2), check if "this" i equals the_killer and then we can use two integers for accessing the matrices. Also, note the IfThen construct.
for(int i = 0; i < n; i++) {
                 new IfThen(
                            new XeqC(the_killer, i),
                            new XeqC(hates[i][agatha], 1)
                 new IfThen(
                            new XeqC(the_killer, i),
                            new XeqC(richer[i][agatha], 0)
This was the first variant I implemented, but then I recall the "trickery" used in Crossword and Word square where the matrices where transposed and Element could be used. The problem with this approach is that all constraints must be rewritten in a way that may be confusing. Come to think of it, maybe the names of the matrices should have been changed to is_hated_by and poorer.

JaCoP variant 2 (transposed matrices, Element)
This method of transposition and using Element is implemented in The constraint is now much simpler:
int shift = -1;
for(int i = 0; i < n; i++) {
    store.impose(new Element(the_killer, hates[agatha], one, shift));
    store.impose(new Element(the_killer, richer[agatha], zero, shift));
Note: the Element in JaCoP defaults to start index as 1, but has support for shifting it to 0, by using -1 as the shift parameter. Choco variant 1 (no Element)
I implemented exact the same principle that was used in the two JaCoP model in the two Choco models. The first - no Element - is

for(int i = 0; i < n; i++) {
                            eq(hates[i][agatha], 1)
                            eq(the_killer, i),
                            eq(richer[i][agatha], 0)
Choco variant 2 (transposed matrices, nth)
Note: one and zero are integer variables since nth cannot handle plain integers as the last argument.
for(int i = 0; i < n; i++) {
   m.addConstraint(nth(the_killer, hates[agatha], one));
   m.addConstraint(nth(the_killer, richer[agatha], zero)


Here we have seen - not surprisingly - that using the Element constraint is quite different depending of which CP system we use and it can be easy or not so easy. It was my explicit intension to see how to solve the same problem as similiar as possible. We should also note that most (if not all) problems can be modeled in many ways, some not using Element at all.

One last comment: The two Java models of Who killed Agatha? took quite a long time to implement. The main reason for that was not the the handling of Element but was due to a bug of confusing the two matrices in one of the conditions. Sigh.

March 12, 2009

MiniZinc Challenge 2008 Results

The MiniZinc Challenge 2008 was held in the summer 2008. I don't know exactly when the result was published (probably in the last week), but here it is; MiniZinc Challenge 2008 Results.

The summary states (higher result better):

The results of the challenge are available here; congratulations go to GeCode on a very convincing win! The summary of results is given in this table:

Contestant Total Score
eclipse_fd 787.3
eclipse_ic 938.8
g12_fd 1655.1
gecode 3418.8

Congratulations to the Gecode team!

This result confirms my impression about the MiniZinc solvers: Gecode/flatzinc is my favorite solver, since it is often very fast, and also that it shows important statistics. See Pi Day Sudoku 2009 for some examples of the latter.

As of writing (2009-03-12) the links to the models and data files in the result page don't work but all the files is included in the last ROTD (release of the day).

By the way, two of the models are from my MiniZinc collection:
* debruijn_binary.mzn: de Bruijn sequences
* quasiGroup7.mzn: quasigroup problem 7

March 11, 2009

Pi Day Sudoku 2009

Brainfreeze Puzzles has a Pi day Sudoku competition:

Pi Day is a celebration of the number π that occurs every March 14 (3.14...). Math geeks all over the world celebrate their math-geekiness on this day with pie-eating contests, recitations of the digits of pi, and occasionally fundraisers where math faculty get hit in the face with pies. At Brainfreeze Puzzles we celebrate Pi Day - how else? - with a Sudoku puzzle.


Rules: Fill in the grid so that each row, column, and jigsaw region contains 1-9 exactly once and π [Pi] three times.

The puzzle is also here (as a PDF file)


I programmed this puzzle in both Comet (using the constraint programming module) and MiniZinc using different solvers. The models use the same principle of solving the problem: a (homebrewn) all different except 0 constraint and counting exactly 3 occurrences of Pi for each row/column and region.

All the solvers give the same unique answer, which of course may mean that there is some systematic error on my part.


Comet solves the problem in about 9 seconds with the following statistics, using exploreall to make sure that it is a unique solution.

time: 8821
#choices = 9999
#fail = 16231
#propag = 23168886

Somewhat surprisingly selecting j before i in the forall loop, gives an improvment from 15 seconds to 9 seconds. This was the same labeling strategy that was used for improving Nonogram (see Comet: Nonogram improved: solving problem P200 from 1:30 minutes to about 1 second). Here is the labeling:

// reversing i and j gives faster solution
forall(j in 1..n, i in 1..n: !x[i,j].bound()) {
tryall(v in V : x[i,j].memberOf(v)) by(v)
m.label(x[i,j], v);
m.diff(x[i,j], v);

MiniZinc and Gecode/flatzinc

Interestingly, the same improvement was observed with MiniZinc and the Gecode/flatzinc solver (the interface to Gecode). Here is the labeling function, with the same swapping of i and j (I didn't know that this mattered in MiniZinc).

solve :: int_search([x[i,j] | j, i in 1..n], "input_order", "indomain", "complete") satisfy;

With the swap, the time went from 16 seconds to 10 seconds with the following statistics:

propagators: 9460
propagations: 13461717
failures: 11221
clones: 11221
commits: 31478
peak memory: 5638 KB sudoku_pi.mzn --num 2 9,41s user 0,72s system 99% cpu 10,139 total

Fzntini, FlatZinc, ECLiPSe and searching for the first solution

MiniZinc's builtin solver flatzinc and fzntini (a SAT solver) only shows one solution and no statistics.

* fzntini solve problem in about 13 seconds
* flatzinc takes 3 seconds.

The ECLiPSe's MiniZinc solver ic takes 6.5 seconds using the same labeling as Gecode/flatzinc. No statistics is shown for this solver either.

For comparison both Comet and Gecode/flatzinc shows the first solutions in 2.5 seconds.


Since it is a competition I won't show my solution or the models on/via the blog. Sorry about that.


I learned about Pi Days Sudoku from the 360 blog: Pi Day Sudoku 2009.

February 28, 2009

Comet: regular constraint, a much faster Nonogram with the regular constraint, some OPL models, and more

Since the last time some more Comet model has been written.

Much faster Nonogram model using the regular constraint

In More Comet models, e.g. Nonogram, Steiner triplets, and different set covering problems I presented, a solver for Nonogram puzzles, and also noted that is was quite slow: Well, it is nice to have some more optimization to do (or more probably, a complete remodelling)....

Inspired by the announcement this week of the ECLiPSe example of Nonogram solver using the regular constraint (see nono_regular.ecl.txt and regular.ecl.txt) - and also my earlier Gecode/R model nonogram.rb which used "regular expressions" - I created a Nonogram model in Comet using the regular constraint:

Let us first look at the regular constraint.

Regular constraint
The regular constraint (see the Comet model for my implementation) is a global constraint using a DFA (deterministic finite automata) which accepts (or not accepts) an input sequence given a "transition matrix". The constraint was presented by Gilles Pesant in "A Regular Language Membership Constraint for Finite Sequences of Variables" (2004).

My implementation of the regular constraint is heavily borrowed from MiniZinc's builtin regular predicate (from lib/zinc/globals.mzn); the translation to Comet was very straightforward (omitting just some asserts).

An exemple of the usage of the constraint: We want to match the regular expression "123*21" (i.e. first "1", then "2", then zero or more "3", then "2", and last a "1"). Note: The length of the sequence is 10, so there must be 6 "3":s since "123" and "21" are "anchored" at the beginning and the end.

int len = 10;
int n_states = 5; // number of states
int input_max = 3; // the states are 1,2, and 3
int initial_state = 1; // we start with the 1 state
set{int} accepting_states = {n_states}; // This is the last state
// The transition matrix
int transition_fn[1..n_states, 1..input_max] =
[[2, 0, 0], // transitions from state 1: "1" -> state 2
[0, 3, 0], // transitions from state 2: "2" -> state 3
[0, 4, 3], // transitions from state 3: "2" -> state 4 | "3" -> state 3 (loop)
[5, 0, 0], // transitions from state 4: "1" -> state 5
[0, 0, 0]]; // transitions from state 5: END state
exploreall {
regular(reg_input, n_states, input_max, transition_fn, initial_state, accepting_states);
} using {
// ....

The unique sequence resulting from this automata is thus 1 2 3 3 3 3 3 3 2 1.

For using regular in the Nonogram problem, the automata for each row/column clue, must be built, preferably by a function. In this is done with the function make_transition_matrix, which by far was the hardest part of this problem (and surely could be written in a smoother way).

For the Nonogram clue [3,2,1] - which represents the regular expression "0*1110*110*10*" - the following automata (transition matrix) is generated:
1 2
0 3
0 4
5 0
5 6
0 7
8 0
8 9
9 0

Note that the regular function uses 0 (zero) as the failing state, so the states must start with 1. This is taken care in the model as the resulting value is subtracted by 1.

As usual in my models, the regular constraint is just a "convenience function", i.e. not using special written propagation methods etc.

The regular constraint has - of course - more applications than for Nonogram solving. I plan to look more into this.

The Nonogram solver:
After the regular constraint and the automata generator was written, it was quite easy to change the old Nonogram solver to use these new tools. The result is in I was quite curious how fast this version should be compared to the former slow model. In short: it is much faster.

As comparison the Lambda instace took about 12 seconds with the old model; with the new model it takes 0.5 seconds, which is a nice improvement. I never finished a run for Nonunique problem with the older model; the new model takes 0.5 seconds (including the startup of the Comet program). Etc.

The P200 problem now takes 2:05 minutes, which can be compared with 57 seconds for the Gecode/R model. Thus, the Comet model is still slow compared to Gecode version and the ECLiPSe version, which solves the P200 problem in just a second or two. Maybe some creative labeling or a "proper" regular constraint can fasten things up...

Update some hour later: One way to gain about 30 seconds to 1:30 minutes on the P200 problem was to explicitly state the consistency level to onDomain, e.g.[m] == q0, onDomains), and to use another labeling strategy:
forall(i in 1..rows, j in 1..cols : !board[i,j].bound()) {
// label(board[i,j]); // the former strategy
tryall(v in 1..2)[i,j] == v, onDomains);

Some more Nonogram problems have been coded:

An aside about regular expressions
I have been very interested in regular expressions (especially the more expressive Perl type) for a long time. In 1997 I wrote a simple Perl program MakeRegex which returns a regular expression given a list of words. It was later Appletized in MakeRegexApplet. Now there are better programs/modules for this.

OPL Models

One of my projects is to translate the OPL models from Pascal Van Hentenryck "The OPL Optimization Programming Language" into Comet. Even if OPL and Comet are different languages the reading of the book has been very awarding. Thanks again, Pascal!

Some OPL models already have been published, but now I've been more systematic and started from the beginning. More models to come.

Finding: arrays in a tuple
In Comet: New models, e.g. Einstein puzzle, KenKen, Kakuro, Killer Sudoku, Stigler's Diet problem, translations of OPL models I wrote

One big difference here: In Comet it is not allowed to have an array in a tuple, so the use data must be a separate matrix.

I've found a way of using arrays in a tuple, by first initialize the values in a matrix and then - by using the all function - "slice" the values into the tuple array. This has been done in the models and

Example from

tuple productType {
int profit;
set{Machines} machines;
int[] use;
int use[Products, Resources] = [[3,4],[2,3], [6,4]];
productType Product[Products] =
[productType(6, {shirtM}, all(i in Resources) use[shirt,i]),
productType(4, {shortM}, all(i in Resources) use[shorts,i]),
productType(7, {pantM}, all(i in Resources) use[pants,i])];

Combining different models

The alphametic problem SEND + MOST = MONEY has the additional requirement to maximize the value of MONEY. The older model does that and nothing more.

One natural extension of the problem is the following:
* first find the maximum value of MONEY
* then find all the solutions with this value.

The model has two functions:
* smm which is just the constraint for the alphametic problem
* send_most_money which has a parameter money.

send_most_money is first called with 0, indicating that is should maximize the value of MONEY, and then returns that value. The next call to send_most_money is with the calculated MONEY value, which indicates that all solutions should be generated.

The answer is

check all solutions for MONEY = 10876
x[9,7,8,2,1,0,4,6] MONEY: 10876
x[9,7,8,4,1,0,2,6] MONEY: 10876

Jim Orlin's Logic Puzzle

In Colored letters, labeled dice: a logic puzzle Jim Orlin stated a logic puzzle:
My daughter Jenn bough a puzzle book, and showed me a cute puzzle. There are 13 words as follows: BUOY, CAVE, CELT, FLUB, FORK, HEMP, JUDY, JUNK, LIMN, QUIP, SWAG, VISA, WISH.

There are 24 different letters that appear in the 13 words. The question is: can one assign the 24 letters to 4 different cubes so that the four letters of each word appears on different cubes. (There is one letter from each word on each cube.) It might be fun for you to try it. I’ll give a small hint at the end of this post. The puzzle was created by Humphrey Dudley.


If anyone wants to write an Excel spreadsheet and solve it via integer programming, please let me know. I’d be happy to post the Excel spreadsheet if you send it to me, or link to it if you post it and send me the URL.

This was a fun puzzle, so I modeled the problem in, and mailed Jim the link.

Some days later he wrote Update on Logic Puzzle where the contributed models were presented. There where another Comet model by Pierre Schaus, one of Comet's developers. Pierres model use an different and more elegant approach than mine.

Jim also linked to some other logical puzzles from the great collection (which have solutions in ECLiPSe/Prolog). One of these puzzles was Building Blocks, in the same vein as his labeled dice puzzle. Hence I had to make a Comet model of this problem:

He concludes the post with the following:

Incidentally, the ease for solving it using Constraint Programming makes me think that Constraint Programming should be considered a fundamental tool in the OR toolkit.

Other Comet models this week

Here are the other Comet models created/published this week. Some of them where very easy to do since they are translations of my MiniZinc models.