The last week I have tested the equation discovery system Eureqa which uses genetic programming (symbolic regression). Hopefully it may be of some interest.
Today I blogged about my (simple) experiments on my Swedish blog Eureqa: equation discovery med genetisk programmering. Google translation to English: Eureqa: equation discovery with genetic programming.
Also, see My Eureqa page.
square(ONE) /\ ( square(TWO) \/ square(THREE) \/ square(FOUR)) % /\ .. % or (square(ONE) /\ ( bool2int(square(TWO)) + bool2int(square(THREE)) + bool2int(square(FOUR)) = 1) % /\ ...where square is defined as:
predicate square(var int: y) =
let {
var 1..ceil(sqrt(int2float(ub(y)))): z
} in
z*z = y;
In some of the later versions of MiniZinc (probably 1.0.2), the handling of reification was changed. My fix was to add a boolean matrix which handled the boolean constraints. It is not beatiful:
% In the list ONE TWO THREE FOUR just the first and one other are perfect squares. square(ONE) /\ [bools[1,j] | j in 1..4] = [square(ONE),square(TWO),square(THREE),square(FOUR)] /\ sum([bool2int(bools[1,j]) | j in 1..4]) = 2 /\ % ...
This year (2010) my older brother Anders will be the same age as the year I was born in the last century, and I will be the same age as the year he was born in the last century. My brother is four years older than me. How old are we this year?A (unnecessary complex) MiniZinc model of this problem is birthdays_2010.mzn. Of course, it can be solved much easier with the simple equation:
{H+A=110,A-H=4} (link to Wolfram Alpha), or in MiniZinc:
constraint H+A = 110 /\ A-H = 4;But this latter version is not very declarative, and I - in general - prefer the declarative way.
Problem: Given a list of people at a party and for each person the list of people they know at the party, we want to find the celebrities at the party. A celebrity is a person that everybody at the party knows but that only knows other celebrities. At least one celebrity is present at the party.(This paper contains an implementation of the problem in Scala.)
Adam knows {Dan,Alice,Peter,Eva},
Dan knows {Adam,Alice,Peter},
Eva knows {Alice,Peter},
Alice knows {Peter},
Peter knows {Alice}
Solution: the celebrities are Peter and Alice.
Adam (1) knows {Dan,Eva,Alice,Peter} {2,3,4,5}
Dan (2) knows {Adam,Alice,Peter} {1,4,5}
Eva (3) knows {Alice,Peter} {4,5}
Alice (4) knows {Peter} {5}
Peter (5) knows {Alice} {4}
This is coded in MiniZinc as:
party = [
{2,3,4,5}, % 1, Adam
{1,4,5}, % 2, Dan
{4,5}, % 3, Eva
{5}, % 4, Alice
{4} % 5, Peter
];
This corresponds to the following incidence matrix, which is calculated in the model. For simplifying the calculations, we assume that a person know him/herself (this is also handled in the model).
% 1 2 3 4 5 1,1,1,1,1, % 1 1,1,0,1,1, % 2 0,0,1,1,1, % 3 0,0,0,1,1, % 4 0,0,0,1,1 % 5This conversion from incidence sets (
party) to incidence matrix (graph) is done by the set2matrix predicate:
predicate set2matrix(array[int] of var set of int: s,
array[int,int] of var int: mat) =
forall(i in index_set(s)) ( graph[i,i] = 1)
/\
forall(i,j in index_set(s) where i != j) (
j in party[i] <-> graph[i,j] = 1
)
All must know a celebrity
I started this model by consider the celebrities as a clique, and therefore using the constraint clique (which is still included in the model). However, is not enough to identify the clique since there may be other cliques but are not celebrities. In the above example there is another clique: {Dan,Adam}.
In fact, the clique constraint is not needed at all (and it actually makes the model slower). Instead we can just look for person(s) that everybody knows, i.e. where there are all 1's in the column of a celebrity in the party graph matrix (graph in the model). This is covered by the constraint:
forall(i in 1..n) (
(i in celebrities -> sum([graph[j,i] |j in 1..n]) = n)
)
This is a necessary condition but not sufficient for identifying celebrities.
Celebrities only know each other
We must also add the constraint that all people in the celebrity clique don't know anyone outside this clique. This is handled by the constraint the all celebrities must knows the same amount of persons, i.e. the size (cardinality) of the clique:
forall(i in 1..n) (
i in celebrities -> sum([graph[i,j] | j in 1..n]) = num_celebrities
)
As noted above, a person is assumed to know him/herself.
Running the model
If we run the MiniZinc model finding_celebrities.mzn we found the following solution:
celebrities = 4..5;
num_celebrities = 2;
which means that the celebrities are {4,5}, i.e. {Alice, Peter}.
Another, slightly different party
We now change the party matrix slightly by assuming that Alice (4) also know Adam (1), i.e. the following incidence matrix:
% 1 2 3 4 5
1,1,1,1,1, % 1
1,1,0,1,1, % 2
0,0,1,1,1, % 3
1,0,0,1,1, % 4
0,0,0,1,1 % 5
]);
This makes Alice a non celebrity since she knows the non celebrity Adam,
and this in turn also makes Peter a non celebrity since he knows the non
celebrity Alice. In short, in this party there are no celebrities.
The model also contains a somewhat larger party graph with 10 persons.
Update about 8 hours later
There is now a version which uses just set constraints, i.e. no conversion to an incidence matrix: finding_celebrities2.mzn. The constraint sections is now:
constraint
num_celebrities >= 1
/\ % all persons know the celebrities,
% and the celebrities only know celebrities
forall(i in 1..n) (
(i in celebrities ->
forall(j in 1..n where j != i) (i in party[j]))
/\
(i in celebrities ->
card(party[i]) = num_celebrities-1)
)
I have kept the same representation of the party (the array of sets of who knows who) as the earlier model which means that a person is now not assuming to know him/herself. The code reflects this change by using where j != i and num_celebrities-1.
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:I have interpreted the problem as follows:
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
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.
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)
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
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.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
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.
1..n, and the families are identified with a number 1..num_families.
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.
family array consists of the family identifier of each person.
all_different(x).
no_fix_point predicate, stating that there can be no i for which x[i] = i (i.e. no "fix point").
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]]).
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"];
[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.
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)
You have five bales of hay.The answer? There is a unique solution (when bales are ordered on weight): 39, 41, 43, 44, 47.
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?
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.
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.
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).
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)
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):
- Helmut Simonis, Cork Constraint Computation Centre, Ireland (SAIS/SweConsNet joint invited speaker)
- ASTRA Research Group, Uppsala University
- Serdar Kadıoğlu, Brown University, USA
- Toni Mancini, Sapienza Università di Roma, Italy
- Tomas Nordlander, Sintef, Norway
- Carl Christian Rolf, Lund Institute of Technology
- Christian Schulte, Royal Institute of Technology
Organisation
SweConsNet 2010 is chaired by Magnus Ågren (SICS). Local arrangements are made by Pierre Flener and Justin Pearson (Uppsala University).
About the catalogueThe news in this release:
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 last working version (2009-12-10) (about 14 Mo)
- the edited version (2005-08) (Sicstus technical report, about 7 Mo)
Another nice thing is that it is now possible to search just the HTML pages, or PDF documents.2009-12-10 working version update: 348 constraints
- new constraints: graph, order, vector, arithmetic constraints...
- new description field Systems: synonyms in the constraint systems Choco, Gecode, Jacop, and SICStus (see also: gccat_systems.xml).
- new description field Reformulation: decomposition as conjunctions of constraints (see e.g.: tree).
- Getting Started section.
- alphabetical index of the constraints, keywords, global index.
clpfd part. These models can be downloaded at My SICStus Prolog page. See below for more about these models.
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, IterSpec2An 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.
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.
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.
% 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.
% 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.)
library(clpfd) now contains many examples of do-loops. Some of the older examples has also been rewritten using these constructs.
% runtime: 80 ms % solvetime: 10 ms % solutions: 1 % constraints: 22 % backtracks: 1 % prunings: 64This makes it easier to compare it to other solvers.
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."
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)
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.
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.
alldifferent_except_0
alldifferent_cst
alldifferent_modulo
all_differ_from_at_least_k_pos
all_equal
all_min_dist
among
among_seq
constraint bin_packing (not exactly like the traditional bin packing))
circuit (SICStus has a built in circuit)
clique
cumulative constraint
distribute
exactly
global contiguity
inverse
sequence
sliding sum
table/2 from SWI Prolog manual)
Changes in Version 3.2.2 (2009-11-30)
This release adds the sequence constraint (contributed by David Rijsman, Quintiq) and has as always some small additions and fixes.
- Kernel
- Bug fixes
- Added missing assignment operator for space-based allocators for STL data structures. (minor, thanks to Gustavo Gutierrez)
- Search engines
- Bug fixes
- The memory reported could be sometimes too low (the previous fix for 3.2.0 did not fix it for branch and bound search). (minor)
- Finite domain integers
- Additions
- Added sequence constraint. (major , contributed by David Rijsman)
- Bug fixes
- The global cardinality (count) constraint now accepts unsorted arrays of values. It previously propagated incorrectly if the array was not sorted. (minor, thanks to Alberto Delgado)
- Fixed bug in the ICL_VAL propagator for global cardinality. (minor)
- Subscription to constant views did not honor the flag to avoid processing. (minor)
- Finite integer sets
- Bug fixes
- Subscription to constant views did not honor the flag to avoid processing (did not occur in practice). (minor)
- Script commandline driver
- Additions
- Report if search engine has been stopped. (minor)
- Range and value iterators
- Other changes
- Renamed test for subset or disjointness of range iterators to "compare". (minor)
- Example scripts
- Additions
- Added car sequencing example (problem 1 in CSPLib). Uses the new sequence-constraint. (minor)
- Gecode/FlatZinc
- Bug fixes
- Support search annotations with constants in the variable arrays. (minor, thanks to Håkan Kjellerstrand)
- The set_in and set_in_reif constraints were buggy when used with Boolean variables (which are usually not generated by mzn2fzn so that the issue probably does not occur in practice). (minor)
- The global_cardinality constraint was not completely compatible with the MiniZinc semantics. It would constrain values not mentioned in the array to have zero occurrences, while in MiniZinc they are unrestricted. (minor)
- Element constraints in reified positions produced an error in the mzn2fzn translation. (major, thanks to Håkan Kjellerstrand)
This is especially impressive because the faster solvers are large, complex programs custom designed to solve paint-by-number puzzles. This one is a general purpose solver with just a couple hundred custom lines of code to generate the constraints, run the solver, and print the result. Considering that this is a simple application of a general purpose solving tool rather than hugely complex and specialized special purpose solving tool, this is an astonishingly good result.From the analysis of my MiniZinc model:
Getting really first class search performance usually requires a lot of experimentation with different search strategies. This is awkward and slow to do if you have to implement each new strategies from scratch. I suspect that a tool like Gecode lets you try out lots of different strategies with relatively little coding to implement each one. That probably contributes a lot to getting to better solvers faster.
If you tried turning this into a fully useful tool rather than a technology demo, with input file parsers and such, it would get a lot bigger, but clearly the constraint programming approach has big advantages, achieving good search results with low development cost.And later in the Conclusions:
...
These two results [Gecode/FlatZinc and LazyFD] highlight the advantage of a solver-independent modeling language like MiniZinc. You can describe your problem once, and then try out a wide variety of different solvers and heuristics without having to code every single one from scratch. You can benefit from the work of the best and the brightest solver designers. It's hard to imagine that this isn't where the future lies for the development of solvers for applications like this.
The two constraint-based systems by Lagerkvist and Kjellerstrand come quite close in performance to the dedicated solvers, although both are more in the category of demonstrations of constraint programming than fully developed solving applications. The power of the underlaying search libraries and the ease of experimentation with alternative search heuristics obviously serves them well. I think it very likely that approaches based on these kinds of methods will ultimately prove the most effective.I think this is an important lesson: Before starting to write very special tools, first try a general tool like a constraint programming system and see how well it perform.
But the remarkable thing is that [the Lazy FD solver] solves almost everything. Actually, it even solved the Lion puzzle that no other solver was able to solve, though, on my computer, it took 80 minutes to do it. Now, I didn't allow a lot of other solvers 80 minutes to run, but that's still pretty impressive. (Note that Kjellerstrand got much faster solving times for the Lion than I did. Lagerkvist also reported that his solver could solve it, but I wasn't able to reproduce that result even after 30 CPU hours. I don't know why.)After some discussion, we come to the conclusion that the differences was probably due to the fact that I use a 32-bit machine (and the 32-bit version of MiniZinc) with 2 Gb memory, and Wolter use a 64-bit machine with 1 Gb memory.
solve :: int_search(
[x[i,j] | j in 1..cols, i in 1..rows],
first_fail,
indomain_min,
complete)
satisfy;
solve :: int_search(
[x[i,j] | i in 1..rows, j in 1..cols],
first_fail,
indomain_min,
complete)
satisfy;
labeling):
array[1..rows*cols] of var 1..2: labeling;and then copy the element in the grid to that array based on the relation between rows and column hints:
constraint
% prepare for the labeling
if rows*row_rule_len < cols*col_rule_len then
% label on rows first
labeling = [x[i,j] | i in 1..rows, j in 1..cols]
else
% label on columns first
labeling = [x[i,j] | j in 1..cols, i in 1..rows]
endif
/\
% ....
and last, the search is now based just on this labeling array:
solve :: int_search(
labeling,
first_fail,
indomain_min,
complete)
satisfy;
solve satisfy;This labeling is recommended by the authors of LazyFD. See MiniZinc: the lazy clause generation solver for more information about this solver.
| Model | fz normal | fz row_column | fz mixed | jacop normal | lazy satisfy | Comet normal | Gecode normal |
| Dancer (#1) | 0.48s (0) | 0.31s (0) | 1.00s (0) | 3.64s (0) | 0.91s (0) | 0.691s (0) | 0.199s (0) |
| Cat (#6) | 0.24s (0) | 0.24s (0) | 0.25s (0) | 1.20s (0) | 1.13s (0) | 0.6s (0) | 0.025s (0) |
| Skid (#21) | 0.24s (13) | 0.23s (3) | 0.28s (13) | 0.78s (13) | 1.37s (0) | 0.586s (0) | 0.217s (0) |
| Bucks (#27) | 0.32s (3) | 0.32s (9) | 0.37s (3) | 0.96s (3) | 2.37s (0) | 1.366s (5) | 0.026s (2) |
| Edge (#23) | 0.16s (25) | 0.17s (25) | 0.18s (25) | 0.59s (25) | 0.31s (0) | 0.521s (43) | 0.175s (25) |
| Smoke (#2413) | 0.27s (5) | 0.27s (8) | 0.28s (8) | 0.83s (5) | 1.44s (0) | 0.616s (14) | 0.275s (5) |
| Knot (#16) | 0.42s (0) | 0.43s (0) | 0.48s (0) | 1.19s (0) | 8.15s (0) | 1.307s (0) | 0.329s (0) |
| Swing (#529) | 0.95s (0) | 0.94s (0) | 0.96s (0) | 2.19s (0) | 21.94s (0) | 1.782s (0) | 0.431s (0) |
| Mum (#65) | 0.64s (20) | 0.64s (22) | 0.66s (22) | 1.68s (20) | 16.34s (0) | 1.268s (39) | 0.491s (22) |
| Tragic (#1694) | 340.32s (394841) | 1.02s (255) | 436.92s (394841) | -- (198329) | 45.97s (0) | 477.39s (702525) | 1.139s (255) |
| Merka (#1611) | -- (361587) | 1.44s (79) | -- (294260) | -- (136351) | 80.92s (0) | 1.654s (46) | 0.645s (13) |
| Petro (#436) | 2.97s (1738) | 143.09s (106919) | 3.42s (1738) | 7.27s (1738) | 9.86s (0) | 3.103s (3183) | 151.09s (106919) |
| M_and_m (#4645) | 1.41s (89) | 601.27s (122090) | 1.59s (89) | 3.43s (89) | 66.98s (0) | 2.215s (162) | 2.797s (428) |
| Signed (#3541) | 1.87s (929) | 23.12s (6484) | 28.23s (6484) | 5.75s (929) | 73.02s (0) | 20.369s (12231) | 1.648s (929) |
| Light (#803) | (400660) | -- (621547) | -- (485056) | (171305) | 8.64s (0) | -- (0) | -- (538711) |
| Forever (#6574) | 4.14s (17143) | 7.86s (30900) | 6.22s (17143) | 12.21s (17143) | 3.27s (0) | 7.5s (27199) | 8.077s (30900) |
| Hot (#2040) | -- (303306) | -- (330461) | -- (248307) | -- (119817) | 165.72s (0) | -- (0) | -- (312532) |
| Karate (#6739) | 95.78s (215541) | 67.27s (130934) | 133.43s (215541) | 373.02s (215541) | 19.32s (0) | 120.02s (272706) | 80.56s (170355) |
| Flag (#2556) | -- (1686545) | 5.69s (14915) | 7.93s (14915) | -- (243222) | 9.29s (0) | 7.28s (24678) | 3.998s (16531) |
| Lion (#2712) | -- (542373) | -- (1124697) | -- (420216) | -- (187215) | 115.56s (0) | -- (0) | -- (869513) |
regular constraints (whereas the LazyFD, and the Comet solvers use a decomposition).
regular constraint, and Comet use my own decomposition of the constraint. For the Merka problem the Comet version outperforms the Gecode/FlatZinc version, otherwise it's about the same time (and number of failures).
... The article analyses some pitfalls in benchmarking, recalling previous published results from benchmarking different kinds of software, and explores some issues in comparative benchmarking of CLP systems.
Changes in Version 3.2.1 (2009-11-04) This release fixes one serious bug in the element constraint for matrices; adds branchings using accumulated failure counts (also known as weighted degree); provides some optimizations (mostly for element constraints and for regular expressions with millions of nodes); adds two cute models (word-square and crossword); and a little this and that as always.
- Kernel
- Additions
- Propagators and variables now maintain an accumulated failure count (AFC). (major). Details: The AFC of a propagator counts how often has the propagator failed during the entire search, and the AFC of a variable is its degree plus the sum of the AFCs of all propagators depending on the variable. While it looks straightforward, this required a major extension of the Gecode toplevel namespace. kernel to deal with global information accessed concurrently from several threads during search. The AFC is also known as "weighted degree".
- Finite domain integers
- Additions
- Added INT_VAL_RANGES_MIN (and INT_VAL_RANGES_MAX) as value selection for branching: it tries the values from the smallest (largest) range first, if the variable's domain has several ranges, otherwise it splits the domain. (minor)
- Added AFC-based branching strategies for integer and Boolean variables: INT_VAR_AFC_MIN, INT_VAR_AFC_MAX, INT_VAR_SIZE_AFC_MIN, INT_VAR_SIZE_AFC_MAX. For details, see "Modeling with Gecode". (major)
- Other changes
- The semantics of division and modulo has changed to match the C standard. This means that the operations round towards zero, and that the result of the modulo has the same sign as its first argument. (minor)
- Bug fixes
- Fixed segfault in matrix element constraint. (major)
- Added missing dispose function for linear disequality of Boolean variables (the only problem was that with a proper dispose function more memory can be reused when the propagator becomes subsumed, so really a tiny quirk). (minor)
- Performance improvements
- Element constraints for integer arrays now accept shared integer arrays (IntSharedArray). By this, the very same array can be shared among several element constraints. Models require no change, as IntArgs are automatically coerced to IntSharedArrays. See "Modelling with Gecode" for more explanation. (minor)
- Optimized element for matrices (in special cases, the propagator is up to six times as efficient as before). (minor)
- Finite integer sets
- Additions
- Added AFC-based branching strategies for set variables: SET_VAR_AFC_MIN, SET_VAR_AFC_MAX, SET_VAR_SIZE_AFC_MIN, SET_VAR_SIZE_AFC_MAX. For details, see "Modeling with Gecode". (major)
- Other changes
- Split rel-op.cpp and rel-op-const.cpp into several compilation units, to avoid excessive memory and time usage of the gcc compiler. (minor)
- Minimal modeling support
- Performance improvements
- Conversion of a regular expression to a DFA would crash on regular expressions with several million nodes (due to running out of call stack space). (minor, thanks to Håkan Kjellerstrand)
- Example scripts
- Additions
- Added word square puzzle. (minor , contributed by Håkan Kjellerstrand)
- Added crossword puzzle (thanks to Peter Van Beek for providing access to some crossword grids). (minor, thanks to Peter Van Beek)
- Other changes
- Sudoku and GraphColor now uses smallest size over accumulated failure count (AFC) as the default heuristic. (minor)
- Bug fixes
- The Nonogram example no longer crashes on empty lines. (minor, thanks to Jan Wolter)
- Gecode/FlatZinc
- Bug fixes
- Fixed statistics output (number of solutions was sometimes wrong). (minor)
- General
- Other changes
- Now posting of propagators and branchers take an object of class Home (rather than just a space) that can carry additional information relevant for posting (for example, groups and accumulated failure information). Models do not need to be changed in any way! (major) :Details: While models require no change, propagator rewriting does (it will work but some information might be lost). Instead of writing something like GECODE_REWRITE(*this,SomeProp::post(home,...)); where *this is the propagator to be rewritten, you should now write GECODE_REWRITE(*this,SomeProp::post(home(*this),...)); By this, the new propagator will inherit information from *this (in particular the accumulated failure count).
Assessment: Slow on more complex puzzles.Update 2009-11-01
...
Results: Run times are not really all that impressive, especially since it is only looking for one solution, not for two like most of the other programs reviewed here. I don't know what the differences are between this and Lagerkvist's system, but this seems much slower in all cases, even though both are ultimately being run in the Gecode library.
mzn2fzn translator did not use the -G gecode flag, which means that Gecode/FlatZinc uses a decomposition of the regular constraint instead of Gecode's built in, which is really the heart in this model. The model is basically two things: build an automata for a pattern and then run regular on it.-G gecode flag for mzn2fzn.
| Problem | Runtime | Solvetime | Failures | Total time |
| Dancer | 0.002 | 0.000 | 0 | 1.327s |
| Cat | 0.009 | 0.002 | 0 | 0.965s |
| Skid | 0.012 | 0.006 | 13 | 0.660s |
| Bucks | 0.015 | 0.004 | 3 | 0.866s |
| Edge | 0.008 | 0.005 | 25 | 0.447s |
| Smoke | 0.011 | 0.004 | 5 | 0.963s |
| Knot | 0.026 | 0.006 | 0 | 1.450s |
| Swing | 0.059 | 0.012 | 0 | 1.028s |
| Mum | 0.120 | 0.093 | 20 | 1.811s |
| Tragic | 6:24.273 | 6:23.607 | 394841 | 6:28,10 |
| Merka | -- | -- | -- | -- |
| Petro | 2.571 | 2.545 | 1738 | 4.071s |
| M&M | 0.591 | 0.510 | 89 | 1.961s |
| Signed | 1.074 | 1.004 | 929 | 2.461s |
| Hot | -- | -- | -- | -- |
| Flag | -- [lazy solver: 2 solutions in 10 seconds] | -- | -- | -- |
| Lion | -- | -- | -- | -- |
-G gecode and a "normal" optimized Gecode.
-G gecode option, and the time is much more like mine in the table above. The analysis is quite different with an assessment of Pretty decent, and the following under Result:...
When comparing this to other solvers, it's important to note that nonogram_create_automaton2.mzn contains only about 100 lines of code. From Kjellerstrand's blog, it is obvious that these 100 lines are the result of a lot of thought and experimentation, and a lot of experience with MiniZinc, but the Olšák solver is something like 2,500 lines and pbnsolve approaches 7,000. If you tried turning this into a fully useful tool rather than a technology demo, with input file parsers and such, it would get a lot bigger, but clearly the CSP approach has big advantages.
Assessment: Pretty decent.I mailed Jan today about the
...
Puzzles with blank lines seem to cause the program to crash with a segmentation fault.
Otherwise it performs quite well. There seems to be about 0.02 seconds of overhead in all runs, so even simple puzzles take at least that long to run. Aside from that, it generally outperforms the Wilk solver. It's not quite in the first rank, especially considering that it was only finding one solution, not checking for uniqueness, but it's still pretty darn good.
...
-solutions n options in the Gecode related solvers (he tested my MiniZinc model with Gecode/FlatZinc), as well as some other comments about my model. Also, I will download the problems tested and play with them.
Christian Schulte suggested using branch strategy INT_VAL_SPLIT_MIN instead of INT_VAL_MAX . This made an improvement for size 7 from 322 failures to 42 and from 1:16 minutes to 10 seconds (for 1 solution). Now it manage to solve a size 8 in a reasonable time (1:33 minutes and 1018 failures): abastral bichrome achiotes shippers troponin rotenone amerinds lessnessBut wait, there's more!
examples/word-square.cpp where Christian Schulte and Mikael Zayenz Lagerkvist has done a great job of improving it (using a slighly smaller word list, though). It solves a size 8 problem in about 14 seconds. There is also two different approaches with different strengths, etc. I have great hopes that it will improved even further...
Comet version 2.0.1 has been released (this Wednesday). It can be downloaded here.
From the release notes:
Version 2.0.1 is a revision on 2.0 that includes several enhancements and bug fixes. The Comet Documentation is now also shipping as a separate installer for each OS so that it can be updated on a more frequent basis, independent of the release of the Comet System. The installers for the Comet System include the latest version of the documentation....
This release has the following new features [with bug tracking id where applicable]:
Major additions since 2.0:* New FlexibleUnaryResource
that allows to specify different durations for activity depending on which resource the activity is executed.
* New CP constraints over set variables, including: SetGlobalCardinality, allDisjoint, atleastIntersection,isExcluded, and unionOf.Other improvements:
* Added ability to change the row of a VisualActivity in gant charts
* Added ability to use set variables in LNS[#395]
* New section on soft global constraints in CP in the manual
* Added tooltips and setColor to VisualActivities
* Added events to var<:CP>{bool} [#365]
* Class documentation now shows inherited methods [#373,#393]
* Improved error messages for set atRank method [#402]
* Better error messages when no solution is found in CP [#401]
* Improved error messages in LNS with no initial solution [#400]
* Improved error messages in DBStatement::setParam with index out of range [#385]
* Added methods excludes and requires to var{set} [#380]
* Added getValue method to var{float} [#356]
* Allow use of var{int} in by clause of a forall [#374]
* Improved error handling in atmost constraint [#362]
* Tooltips on VisualRectangle, VisualCircle, VisualLine, VisualText, and VisualTextTable. [#363]
* Improved error handling in VisualDisplayTable [#359]Bug Fixes:
* Fixed rank and filtering algorithms of AlternativeUnaryResource
[#381]
* Fixed rank on UnaryResourcewith optional activities[#239]
* Fixed exactIntersection constraint.[#397]
* Fixed bug in random seeds leading to correlated UniformDistribution objects [#384]
* Fixed bug in Graphical Debugger that caused the last line to not be shown [#361]
* Fixed element constraint on 3D matrices[#369]
* Fixed array out of bounds error on VisualDisplayTable [#370]
* Fixed rounding problem when using cotln with SCIP library [#398]
* Implemented getSwapDelta and getMultipleAssignDelta on DisequationSystem [#318]
* Fixed memory leaks in CP library [#293]
* Fixed bug in breakable activities [#388]
* Fixed segfault when returning an int[][] from a user plugin [#386]
* Implemented casting var{float} to an int [#355]
For more about Comet, see My Comet page.