" /> My Constraint Programming Blog: December 2009 Archives

« November 2009 | Main | January 2010 »

December 29, 2009

1 year anniversary and Secret Santa problem II

Exactly one year ago, I started this blog. Little did I know what to expect. Through this blog and its accompanying pages - I have met many very interesting persons that has learned me much in my pursuit of learning constraint programming. I am very grateful for your help and inspiration! And thanks to all my (other) readers.

I hope the following year will be as rewarding as this last.

Secret Santa problem II

As an anniversary gift, here is another Secret Santa problem (compare with Merry Christmas: Secret Santas Problem) with a slightly different touch.

The problem formulation is from Maple Primes forum Secret Santa Graph Theory:
Every year my extended family does a "secret santa" gift exchange. Each person draws another person at random and then gets a gift for them. At first, none of my siblings were married, and so the draw was completely random. Then, as people got married, we added the restriction that spouses should not draw each others names. This restriction meant that we moved from using slips of paper on a hat to using a simple computer program to choose names. Then people began to complain when they would get the same person two years in a row, so the program was modified to keep some history and avoid giving anyone a name in their recent history. This year, not everyone was participating, and so after removing names, and limiting the number of exclusions to four per person, I had data something like this:

Name: Spouse, Recent Picks

Noah: Ava. Ella, Evan, Ryan, John
Ava: Noah, Evan, Mia, John, Ryan
Ryan: Mia, Ella, Ava, Lily, Evan
Mia: Ryan, Ava, Ella, Lily, Evan
Ella: John, Lily, Evan, Mia, Ava
John: Ella, Noah, Lily, Ryan, Ava
Lily: Evan, John, Mia, Ava, Ella
Evan: Lily, Mia, John, Ryan, Noah
I have interpreted the problem as follows:
  • one cannot be a Secret Santa of one's spouse nor of oneself
  • one cannot be a Secret Santa for somebody two years in a row
  • objective: maximize the "Secret Santa distance", i.e. the number of years since the last assignment of the same person
My MiniZinc model for this problem is secret_santa2.mzn.

This is a more traditional linear programming problem compared to Secret Santa I, using a distance matrix for maximizing the "Secret Santa Distance". M is a "large" number (number of persons + 1) for coding that there have been no previous Secret Santa assignment. 
rounds = array2d(1..n, 1..n, [
%N  A  R  M  El J  L  Ev 
 0, M, 3, M, 1, 4, M, 2, % Noah
 M, 0, 4, 2, M, 3, M, 1, % Ava 
 M, 2, 0, M, 1, M, 3, 4, % Ryan
 M, 1, M, 0, 2, M, 3, 4, % Mia 
 M, 4, M, 3, 0, M, 1, 2, % Ella
 1, 4, 3, M, M, 0, 2, M, % John
 M, 3, M, 2, 4, 1, 0, M, % Lily
 4, M, 3, 1, M, 2, M, 0  % Evan
]);
The original problem don't say anything about single persons, i.e. those without spouses. In this model, singleness (no-spouseness) is coded as spouse = 0, and the no-spouse-Santa constraint has been adjusted to takes care of this.

The constraint part is the following, where n is the number of persons: 
constraint
   all_different(santas)

   /\ % no Santa for one self or the spouse
   forall(i in 1..n) (
      santas[i] != i /\
      if spouses[i] > 0 then santas[i] != spouses[i] else true endif
   )

   /\ % the "santa distance" (
   forall(i in 1..n) ( santa_distance[i] = rounds[i,santas[i]] )

   /\ % cannot be a Secret Santa for the same person two years in a row.
   forall(i in 1..n) (
      let { var 1..n: j } in
       rounds[i,j] = 1 /\ santas[i] != j
   )

   /\
   z = sum(santa_distance)

Solution

This model gives - when using solve satisfy and the constraint z >= 67 - the following 8 solutions with a total of Secret Santa distance of 67 (sum(santa_distance)). If all Secret Santa assignments where new it would have been a total of n*(n+1) = 8*9 = 72. As we can see there is always one Santa with a previous existing assignment. (With one Single person and the data I faked, we can get all brand new Secret Santas. See the model for this.) 
santa_distance: 9 9 4 9 9 9 9 9
santas        : 7 5 8 6 1 4 3 2

santa_distance: 9 9 4 9 9 9 9 9
santas        : 7 5 8 6 3 4 1 2

santa_distance: 9 9 9 4 9 9 9 9
santas        : 7 5 6 8 1 4 3 2

santa_distance: 9 9 9 4 9 9 9 9
santas        : 7 5 6 8 3 4 1 2

santa_distance: 9 9 9 9 4 9 9 9
santas        : 4 7 1 6 2 8 3 5

santa_distance: 9 9 9 9 4 9 9 9
santas        : 4 7 6 1 2 8 3 5

santa_distance: 9 9 9 9 9 9 4 9
santas        : 4 7 1 6 3 8 5 2

santa_distance: 9 9 9 9 9 9 4 9
santas        : 4 7 6 1 3 8 5 2

Posted by hakank at 07:50 PM |

December 25, 2009

Merry Christmas: Secret Santas Problem

Here is a fun little problem related to the holiday. Merry Christmas, everyone! (For the Swedish readers: Sorry for the one day off greeting.)

This problem is from the Ruby Quiz#2 Secret Santas
Honoring a long standing tradition started by my wife's dad, my friends all play a Secret Santa game around Christmas time. We draw names and spend a week sneaking that person gifts and clues to our identity. On the last night of the game, we get together, have dinner, share stories, and, most importantly, try to guess who our Secret Santa was. It's a crazily fun way to enjoy each other's company during the holidays.

To choose Santas, we use to draw names out of a hat. This system was tedious, prone to many "Wait, I got myself..." problems. This year, we made a change to the rules that further complicated picking and we knew the hat draw would not stand up to the challenge. Naturally, to solve this problem, I scripted the process. Since that turned out to be more interesting than I had expected, I decided to share.

This weeks Ruby Quiz is to implement a Secret Santa selection script.

Your script will be fed a list of names on STDIN.

...

Your script should then choose a Secret Santa for every name in the list. Obviously, a person cannot be their own Secret Santa. In addition, my friends no longer allow people in the same family to be Santas for each other and your script should take this into account.
The MiniZinc model secret_santa.mzn skips the parts of input and mailing. Instead, we assume that the friends are identified with a unique number from 1..n, and the families are identified with a number 1..num_families.

We use two arrays:
  • the array x represents whom a person should be a Santa of. x[1] = 10 means that person 1 is a Secret Santa of person 10, etc.
  • the family array consists of the family identifier of each person.
Now, the three constraints can easily be stated in a constraint programming system like MiniZinc:
  • "everyone gives and received a Secret Santa gift": this is handled with a permutation of the values 1..n using all_different(x).
  • "one cannot be one own's Secret Santa". This is captured in the no_fix_point predicate, stating that there can be no i for which x[i] = i (i.e. no "fix point").
  • "no Secret Santa to a person in the same family". Here we use the family array and checks that for each person (i), the family of i (family[i]) must not be the same as the family of the person that receives the gift (family[x[i]]).
Here is the complete MiniZinc model (in a slightly compact form): 
include "globals.mzn"; 
int: n = 12;
int: num_families = 4;
array[1..n] of 1..num_families: family = [1,1,1,1, 2, 3,3,3,3,3, 4,4];
array[1..n] of var 1..n: x :: is_output;

% Ensure that there are no fix points in the array.
predicate no_fix_points(array[int] of var int: x) = 
      forall(i in index_set(x)) ( x[i] != i  );

solve satisfy;

constraint
  % Everyone gives and receives a Secret Santa
  all_different(x) /\      

  % Can't be one own's Secret Santa
  no_fix_points(x) /\   

  % No Secret Santa to a person in the same family
  forall(i in index_set(x)) (   family[i] != family[x[i]]  )
; 

% output (just for the minizinc solver)
output [
   "Person " ++ show(i) ++ 
   " (family: " ++ show(family[i]) ++ ") is a Secret Santa of " ++ 
    show(x[i]) ++ 
   " (family: " ++ show(family[x[i]]) ++ ")\n"
   | i in 1..n
] ++ 
["\n"];

Solution

Here is the first solution (of many): 
[10, 9, 8, 5, 12, 4, 3, 2, 1, 11, 7, 6]
This means that person 1 should be a Secret Santa of person 10, etc.

The minizinc solver gives the following, using the output code (slightly edited): 
Person  1 (family: 1) is a Secret Santa of 10 (family: 3)
Person  2 (family: 1) is a Secret Santa of  9 (family: 3)
Person  3 (family: 1) is a Secret Santa of  8 (family: 3)
Person  4 (family: 1) is a Secret Santa of  5 (family: 2)
Person  5 (family: 2) is a Secret Santa of 12 (family: 4)
Person  6 (family: 3) is a Secret Santa of  4 (family: 1)
Person  7 (family: 3) is a Secret Santa of  3 (family: 1)
Person  8 (family: 3) is a Secret Santa of  2 (family: 1)
Person  9 (family: 3) is a Secret Santa of  1 (family: 1)
Person 10 (family: 3) is a Secret Santa of 11 (family: 4)
Person 11 (family: 4) is a Secret Santa of  7 (family: 3)
Person 12 (family: 4) is a Secret Santa of  6 (family: 3)

Bales of Hay

As an extra, here is another MiniZinc model: bales_of_hay.mzn which solves the following problem (from The Math Less Traveled the other day):
You have five bales of hay.

For some reason, instead of being weighed individually, they were weighed in all possible combinations of two. The weights of each of these combinations were written down and arranged in numerical order, without keeping track of which weight matched which pair of bales. The weights, in kilograms, were 80, 82, 83, 84, 85, 86, 87, 88, 90, and 91.

How much does each bale weigh? Is there a solution? Are there multiple possible solutions?
The answer? There is a unique solution (when bales are ordered on weight): 39, 41, 43, 44, 47.

Posted by hakank at 11:32 AM |

December 22, 2009

Some updated SICStus Prolog models

Mats Carlsson (designer and main implementer of SICStus Prolog) was kind enough to send me alternative versions of some of my SICStus Prolog models, which now are included in the models (marked with his name). His versions are - of course - more elegant and faster than mine. Thanks, Mats.

Assignment problem

Model: assignment.pl using the global constraint global_cardinality. 
assignment2(Problem) :-
        cost(Problem, Mode, CostRows),
        format('\nProblem ~d\n~w\n', [Problem,Mode]),
        transpose(CostRows, CostCols),
        length(CostRows, R),
        length(CostCols, C),
        length(Vars, R),
        domain(Vars, 1, C),
        (   for(I,1,C),
            foreach(I-Y,Ys)
        do  Y in 0..1
        ),
        global_cardinality(Vars, Ys, [cost(Cost,CostRows)]),
        (Mode==minimize -> Dir=up ; Dir=down),
        labeling([Dir], [Cost]),
        labeling([], Vars), !,
        format('assignment = ~w, cost = ~d\n', [Vars,Cost]),
        fd_statistics, nl.

Bin Packing

Model: bin_packing.pl. Here is the global constraint cumulative used. Note: The representation of the filled bins is however not the same as in my approach. 
bin_packing2(Problem) :-
        problem(Problem, StuffUnordered, BinCapacity),
        portray_clause(problem(Problem, StuffUnordered, BinCapacity)),
        length(StuffUnordered, N),
        N1 is N+1,
        (   foreach(H,StuffUnordered),
            foreach(task(S,1,E,H,1),Tasks),
            foreach(NH-S,Tagged),
            foreach(S,Assignment),
            foreach(_-X,Keysorted),
            foreach(X,Vars),
            param(N1)
        do  S in 1..N1,
            E in 2..N1,
            NH is -H
        ),
        keysort(Tagged, Keysorted),
        maximum(Max, Vars),
        cumulative(Tasks, [limit(BinCapacity)]),
        labeling([minimize(Max),step], Vars),
        portray_clause(assignment(Assignment)),
        fd_statistics,
        nl.

Post Office Problem

Model: post_office_problem2.pl. This is a much better way of solving this problem in Prolog than my translation from MiniZinc. 
go2 :-
        Days = 7,
        % requirements number workers per day
        Need = [17, 13, 15, 19, 14, 16, 11],
        % Total cost for the 5 day schedule.
        % Base cost per day is 100.
        % Working saturday is 100 extra
        % Working sunday is 200 extra.
        Cost = [500, 600, 800, 800, 800, 800, 700],
        % Decision variables. X[I]: Number of workers starting at day I
        length(X, Days),
        domain(X, 0, 10),
        append(X, X, [_,_,_|Ys]),
        (   foreach(Nd,Need),
            fromto(Ys, Ys1, Ys2, _)
        do  Ys1 = [Y1|Ys2],
            Ys2 = [Y2,Y3,Y4,Y5|_],
            Y1+Y2+Y3+Y4+Y5 #>= Nd
        ),
        scalar_product(Cost, X, #=, Total),
        labeling([minimize(Total),bisect], X),
        format('assignment = ~w, total cost = ~d\n', [X,Total]),
        fd_statistics.
I also corrected a weird (and wrong) way of calculating the total cost in my version (as well as in the MiniZinc model post_office_problem2.mzn).

Posted by hakank at 07:10 PM |

December 19, 2009

Choco's new site

Soon the website for Choco constraint programming solver will be changed to a this site (will replace the old one). There are some broken links and missing information, but it seems to be well organized.

Some links: For anyone not familiar with Choco, here is a short description (from the new site):
choco is a java library for constraint satisfaction problems (CSP), constraint programming (CP) and explanation-based constraint solving (e-CP).
It is built on a event-based propagation mechanism with backtrackable structures.

choco can be used for:

* teaching (a user-oriented constraint solver with open-source code)
* research (state-of-the-art algorithms and techniques, user-defined constraints, domains and variables)
* real-life applications (many application now embed choco)

Posted by hakank at 09:35 AM |

December 15, 2009

SweConsNet 2010 (May 21, 2010 in Uppsala, Sweden)

SweConsNet 2010 is to be held May 21 2010 in Uppsala, Sweden. This is the 9th workshop of the Network for Sweden-based researchers and practitioners of Constraint programming (SweConsNet). It is collocated with the SAIS Workshop 2010 (May 20-21).

From the SweConsNet 2010 site:
The purpose of this workshop is to learn about ongoing research in constraint programming, existing projects and products, and further development of the network.

The workshop is open to everybody interested in the theory and practice of constraint programming, whether based in Sweden or elsewhere.

...

Please forward this information to people who might be interested in this workshop but are not yet on the SweConsNet mailing list. They can subscribe to it by sending a message to Justin Pearson.

...

Location

Uppsala University, Information Technology Center (ITC), Polacksbacken, house 1 (Directions).

Programme

List of speakers (preliminary):

Organisation

SweConsNet 2010 is chaired by Magnus Ågren (SICS). Local arrangements are made by Pierre Flener and Justin Pearson (Uppsala University).

The last work shop (May this year) was very interesting and fun, and I'm really looking forward to SweConsNet 2010. For more about SweConsNet 2009, see its homepage and my own Report from SweConsNet2009, including my presentation.

Posted by hakank at 07:46 PM |

December 14, 2009

The Global Constraint Catalog has been updated

A new version of Global Constraint Catalog has been released. That's great! The update date is 2009-12-10, but I didn't see it until today.

Here is the presentation of the catalog:
About the catalogue

The catalogue presents a list of 348 global constraints issued from the literature in constraint programming and from popular constraint systems. The semantic of each constraint is given together with a description in terms of graph properties and/or automata.

The catalogue is periodically updated by Nicolas Beldiceanu, Mats Carlsson and Jean-Xavier Rampon. Feel free to contact the first author for any questions about the content of the catalogue.

Download the Global Constraint Catalog in pdf format:

The news in this release:
2009-12-10 working version update: 348 constraints
Another nice thing is that it is now possible to search just the HTML pages, or PDF documents.

Sophie Demassey has done a wonderful work with the online version.

Also, I am happy for the links to this blog and my MiniZinc page, see the section on (decompositions of) global constraints.

Posted by hakank at 07:59 PM |

December 12, 2009

SICStus Prolog 4.1 released and My SICStus Prolog page

SICStus Prolog version 4.1 was released yesterday (2009-12-11). Congratulations to the SICStus team! See here for a summary of the news in this version.

For the past weeks I have tested the beta version of this release. In these tests I focused mainly on the following:
  • the do-loops (for loops)
  • support for MiniZinc version 1.0
  • and somewhat SPIDER (the new IDE)
I did report some findings in the beta version, but most of the time I have been creating SICStus models and just learning the system, especially the clpfd part. These models can be downloaded at My SICStus Prolog page. See below for more about these models.

do-loops

SICStus Prolog's support for do-loops is based on Joachim Schimpf's paper Logical Loops (link to CiteSeer). These constructs where first implemented in the ECLiPSe Constraint Programming System (which I wrote about in Constraint programming in ECLiPSe Constraint Programming System).

The following constructs are implemented in SICStus version 4.1: 
fromto(First,In,Out,Last)
foreach(X,List)
foreacharg(X,Struct)
foreacharg(X,Struct,Idx)
for(I,MinExpr,MaxExpr)
count(I,Min,Max)
param(Var)
IterSpec1, IterSpec2
An example: quasigroup_completion.pl is a simple model that demonstrates the foreach loop, the constraints makes it a latin square given the hints in the Problem matrix: 
solve(ProblemNum) :-
        problem(ProblemNum, Problem),
        format('\nProblem ~d\n',[ProblemNum]),
        length(Problem, N),
        append(Problem, Vars),
        domain(Vars, 1, N),

        ( foreach(Row, Problem)
        do
          all_different(Row,[consistency(domain)])
        ),

        transpose(Problem, ProblemTransposed),
        ( foreach(Column, ProblemTransposed)
        do
          all_different(Column,[consistency(domain)])
        ),

        labeling([], Vars),
        pretty_print(Problem),nl,
        fd_statistics.

problem(1, [[1, _, _, _, 4],  
            [_, 5, _, _, _],
            [4, _, _, 2, _],
            [_, 4, _, _, _],
            [_, _, 5, _, 1]]).
Some other examples are from the Bin Loading model bin_packing.pl. First is an example of a constraint that requires a (reversed) ordered array. 
% load the bins in order:
% first bin must be loaded, and the list must be ordered
element(1, BinLoads, BinLoads1),
BinLoads1 #> 0,
( fromto(BinLoads,[This,Next|Rest],[Next|Rest],[_])
do
  This #>= Next
),
Next is how to sum occurrences of the loaded bins, using fromto to count the number of loaded bins (Loaded is a reified binary variable): 
% calculate number of loaded bins 
% (which we later will minimize)
( foreach(Load2,BinLoads),
  fromto(0,In,Out,NumLoadedBins),
  param(BinCapacity)
do
  Loaded in 0..1,
  Load2 #> 0 #<=> Loaded #= 1,
  indomain(Loaded),
  Out #= In + Loaded
),
A slighly more general version of ordering an array is the predicate my_ordered from young_tableaux.pl: 
my_ordered(P,List) :-
        ( fromto(List, [This,Next | Rest], [Next|Rest],[_]),
          param(P)
        do
          call(P,This,Next)
        ).
where a comparison operator is used in the call, e.g. my_ordered(#>=,P) to sort in reversed order.

Most of my models use these do loop constructs. As you can see of from the models I'm not a Prolog guy by profession, even though the language has fascinated me for a long time. SICStus' (and also ECLiPSe's) new approach of using for do-loops has made me appreciate Prolog in a new way. Very inspiring!

Two missing construct in SICStus (compared to the ECLiPSe implementation) are for(...) * for(...) and multifor. When writing the ECLiPSe models I used these two quite often, for example in the ECLiPSe model assignment.ecl. Also, SICStus don't support the syntactic sugar of array/matrix access with [] (note, this feature is not related to do-loops). When I first realized that they where missing in SICStus, I thought that it would be a hard job of converting my ECLiPSe models to SICStus. Instead, these omissions was - to my surprise - quite a revelation.

My ECLiPSe models was mostly just a translation of the MiniZinc/Comet models I've written before, i.e. array/matrix based models where array access and loops such as forall(i in 1..n) () is used all the time. Not surprising, my first SICStus models was then just a conversion of these array/matrix access to nth1 or element constraints to simulate the ECLiPSe constructs. But it was not at all satisfactory; in fact, it was quite ugly sometimes, and also quite hard to understand. Instead I started to think about the problem again and found better ways of stating the problem, thus used much less of these constructs. Compare the above mentioned model with the SICStus version assignment.pl which in my view is more elegant than my ECLiPSe version.

Here is a simple comparison of the assignment models mentioned above.

The ECLiPSe version (using []-indices): 
% 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
),
% calculate TotalCost
(for(I,1,Rows) * for(J,1,Cols), 
 fromto(0,In,Out,TotalCost),
 param(X,Cost) do 
     Out #= In + X[I,J]*Cost[I,J]
),
As we see, this is heavily influenced by the MiniZinc/Comet way of coding.

Here is the corresponding code in SICStus: 
% exacly one assignment per row, all rows must be assigned
( foreach(Row, X) do
      sum(Row,#=,1)
),
% zero or one assignments per column
transpose(X, Columns),
( foreach(Column, Columns) do
      sum(Column,#=<,1)
),
% calculate TotalCost
append(Cost, CostFlattened),
scalar_product(CostFlattened,Vars,#=,TotalCost),
(Almost the same code could be written in ECLiPSe as well; this is more about showing how my approach of coding has changed.)

However, I have not been able to completely free myself from the matrix approach; sometimes it was simply too hard, and sometimes I was just lazy.

A final note: The example directory of library(clpfd) now contains many examples of do-loops. Some of the older examples has also been rewritten using these constructs.

Support for MiniZinc/FlatZinc verion 1.0

One other quite large part of the testing was of the support of MiniZinc/FlatZinc version 1.0 (the earlier SICStus version supported just version 0.9). The solver is often very fast, but I did not do any systematic comparison with other solvers using the beta version.

I am especially happy about that the FlatZinc solver now shows statistics, e.g. 
% runtime:      80 ms
% solvetime:    10 ms
% solutions:    1
% constraints:  22
% backtracks:   1
% prunings:     64
This makes it easier to compare it to other solvers.

There are a number of ways of running a MiniZinc model or FlatZinc file (see the documentation). Here is how I normally run the MiniZinc models from the command line (via my Perl wrapper program):

mzn2fzn -G sicstus minesweeper_3.mzn && sicstus --goal "use_module(library(zinc)), on_exception(E,zinc:fzn_run_file('minesweeper_3.fzn',[solutions(1),statistics(true),timeout(30000)]), write(user_error,E)), halt."

Explanation:
  • statistics(true): show the statistics
  • solutions(1): just show one solution. Use solutions(all) for all solutions
  • timeout(30000): time out in milliseconds (here 30 seconds)
  • the on_exception wrapper, so errors don't give the prompt. Note: There may be some strange results if the timeout from library(timeout) is used at the same time.
Note: "set vars" and "float vars" are not supported in this version.

SPIDER

I did just briefly tested SPIDER, the Eclipse-based development environment for SICStus, and I honestly don't know how much I will use it instead of good old Emacs. However, where I a professional SICStus Prolog programmer, I would surely use it all the time since it has a lot of very good features especially crafted for SICStus.

One very useful feature is that it is quite good at detecting variables not properly declared in the do-loops (and singletons elsewhere); one has to use param for using a variable in inner loops. SPIDER is very good at detecting errors when such param values are missing (as well as other errors). For many models I have just started SPIDER to check if there where such bugs.

Another nice feature is the "balloon help", where the SICStus documentation is presented (click in the yellow area for more information).

My SICStus Prolog models

As always when starting learning a new constraint programming system, I started with my learning models, this time mostly by translating the ECLiPSe models. It first took quite a long time, since I missed some constructs I was used to in ECLiPSe (see above). But after a time it was rather easy to do it more like a SICStus approach, and now I really like writing in SICStus. Still, there are some models where this direct translations shows (and I'm not very proud of these models).

Also, I would like to thank Mats Carlsson and Magnus Ågren of the SICStus team for some great help with some of the first models.

So, I have now done almost all my ECLiPSe models in SICStus, except for those using floats or some where the SICStus' distributed examples are much better. SICStus don't support "set vars", so I used boolean lists instead, see for example steiner.pl and clique.pl. Also, there are some 30-40 models not done in written ECLiPSe, and hopefully more is to come. All these models can be seen at My SICStus Prolog page.

These models contains comments of the problem, e.g. references and also links to other of my models implementing the problem (in other constraint programming systems).

Posted by hakank at 07:48 PM |