" /> My Constraint Programming Blog: February 2009 Archives

« January 2009 | Main | March 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 nonogram.co, 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: nonogram_regular.co.

Let us first look at the regular constraint.


Regular constraint
The regular constraint (see the Comet model regular.co 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 regular.co 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: nonogram_regular.co
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 nonogram_regular.co. 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 nonogram_p200.co 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. cp.post(a[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) m.post(board[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 fixed_charge2.co and production3.co.

Example from fixed_charge2.co: 

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 send_most_money.co 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 send_most_money2.co 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 labeled_dice.co, 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 WordPuzzleSchaus.co 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 brownbuffalo.sourceforge.net (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: building_blocks.co.

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.

Posted by hakank at 07:09 AM | | Comments (2)

February 21, 2009

Comet: New models, e.g. Einstein puzzle, KenKen, Kakuro, Killer Sudoku, Stigler's Diet problem, translations of OPL models

Here are some of the new Comet models written the last week.

Findings this week

Representing KenKen, Kakuro, and Killer Sudoku

One important thing in modelling a problem is how to representing the data in the problem. For grid puzzles such as KenKen, Kakuro, and Killer Sudoku, where one of the objects is to operate (add, multiply, etc) on an array of unknown length, I found one representation which work quite well (at least on the simple problem I tested).

Let's take the KenKen problem from Wikipedia.

The first version kenken.co was quite large, and stated explicitly all the operations (addition, subtraction, multiplication, or division). This was slightly generalized in the same model, though.

After that I relaxed the requirement to state exactly which operation to do things actually got simpler to model. In the Comet model kenken2.co we represent an cell with a tuple (struct) as two integers 

tuple cell {

  int r;

  int c;

}

The cage of numbers to add (or multiply etc) is represented by another tuple, a set of cells, and the result (integer): 

tuple P {

  set{cell} c;

  int res;

}

Now, it is only to state the problem using this structure:

int num_p = 15; // number of cages/segments
P problem[1..num_p] = 
  [
   P({cell(1,1), cell(2,1)}, 11),
   P({cell(1,2), cell(1,3)}, 2),
   P({cell(1,4), cell(2,4)}, 20),
   P({cell(1,5), cell(1,6), cell(2,6), cell(3,6)}, 6),
   P({cell(2,2), cell(2,3)}, 3),
   P({cell(2,5), cell(3,5)}, 3),
   P({cell(3,1), cell(3,2), cell(4,1), cell(4,2)}, 240),
   P({cell(3,3), cell(3,4)}, 6),  
   P({cell(4,3), cell(5,3)}, 6),
   P({cell(4,4), cell(5,4), cell(5,5)}, 7),
   P({cell(4,5), cell(4,6)}, 30),  
   P({cell(5,1), cell(5,2)}, 6),
   P({cell(5,6), cell(6,6)}, 9),
   P({cell(6,1), cell(6,2), cell(6,3)}, 8),
   P({cell(6,4), cell(6,5)}, 2)
   ];

This representation makes it possible to reading a problem from a file etc (which has not been done, though).

The single function that calculates the values in the segment given the result is as follows. Note: Here I assume that division and subtraction will only be done for two sized sets.

function void calc(Solver m, set{cell} cc, var{int}[,] x, int res) {

  if (cc.getSize() == 2) {

    var{int} a(m, x.getRange(0));

    var{int} b(m, x.getRange(0));

    m.post(a == x[cc.atRank(0).r,cc.atRank(0).c]);

    m.post(b == x[cc.atRank(1).r,cc.atRank(1).c]);

    m.post((a + b == res) || (a * b == res) || 

           (a * res == b) || (b * res == a) || 

           (a - b == res) || (b - a == res));

  } else {

    m.post(sum(i in cc) x[i.r, i.c] == res || prod(i in cc) x[i.r, i.c] == res);

  }

}


In the exploreall we state the following constraints: 

// all rows and columns must be unique

  forall(i in R)

      m.post(alldifferent(all(j in R) x[i,j]));

  forall(j in R)

    m.post(alldifferent(all(i in R) x[i,j]));

  // the specific problem

  forall(i in 1..num_p) {

    calc(m, problem[i].c, x, problem[i].res);

  }

Now, the other two grid puzzles in Comet, Killer Sudoku, and Kakuro, is represented is the same way, using just slight modifications in the calc function and added or altered constraints.

For more about these three grid puzzles see Wikipedia's entries:
* KenKen
* Killer Sudoku
* Kakuro


Different solvers in one model: Sudoku generator


Speaking of grid puzzles, here is a (proof-of-concept) generator of Sudoko puzzles: sudoku_generate.co. It uses a simple and brute force approach:

* Generate a problem matrix with the proper number of unknowns
* Try to solve the problem. If there are exactly one solution, then all is fine, else generate another problem.

It also use two limits to ensure that one generation/solution is not
to costy (which may miss some good problems):
* timeout
* number of failures

The thing to note here is the way two different functions works together: first one constraint solver (model) to generate a Sudoku matrix, then another constraint solver (model) to really solve the Sudoko problem.


User defined constraints


Earlier I wrote how to define function in Comet, e.g. in Some Comet constraint programming (CP) models .

This week I wanted to state my own functions in the same way as the built in functions, e.g. as m.post(myConstraint(...));.

The following function implements the (global) constraint increasing, which then can be stated as m.post(increasing(x));. Please note that this is just a "modelling" constraint, and it will use the underlying solver propagation etc.

class increasing extends UserConstraint {

  var{int}[] _x;

  int _n;

  increasing(var{int}[] x) : UserConstraint() {

    _x = x;

    _n = _x.getSize();      

  }

  Outcome post(Consistency cl) {

    Solver cp = _x[1].getSolver();

    forall(i in 2.._n) {

      cp.post(_x[i-1] <= _x[i], cl);

    }

    return Suspend;

  }

  Outcome propagate() { 

     return Suspend;

  }  

}

The Comet model constraint_test.co implements the following constraints:

  • alldifferent_except_0
  • increasing
  • decreasing
  • toNum
  • correspondence

Translating OPL models

I've started to read Pascal Van Hentenryck's great book about OPL, "The OPL Optimization Programming Language", (ISBN: 9780262720304, unfortunately out of print), and it is quite clear the Comet "is not very unlike OPL". Which is not a big surprise since Van Hentenryck is the designer of both languages.

There are differences between Comet and OPL, sometimes quite big, but often they are easy to circumvent. Maybe later findings will discuss more about this.

The following Comet models are translations of OPL models, some of these are from the examples from ILOG's OPL Models.

  • building_a_house.co: Scheduling building a house (OPL). Comet use a different way of stating scheduling constraints than OPL.
  • covering_opl.co: Set covering problem. Also note the labeling (in the uses section), which solves the problem faster than with the default label, or labelFF.
  • einstein_opl.co: Einstein puzzle, translation of the OPL model from Daniel Selman's Einstein's Puzzle - Or, 'The Right Tool for the Job'. The presentation in the Comet model is different than the OPL model (which is shown commented) but it is quite close.
  • fixed_charge.co: Fixed-charge problem. 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.
  • number_square.co: From page 32 of Van Hentenryck's OPL book: Finding a eight digit square which remains a square when 1 is concatenated in from of it. This simple problem translates very well to Comet.
  • p_median_opl.co: P-median problem. This also translates very well to Comet.
  • production2.co: Production planning problem. Same difference as in the fixed charge model, where arrays in a tuple is not allowed.
  • warehouse.co: Warehouse location problem.


Models


Here are the new Comet models. As usual more information about the problem/model is in the header of the model.

Posted by hakank at 09:47 AM |

JaCoP: Features request for version 2.4

In Submit features requests for JaCoP 2.4 Radoslaw Szymanek asks for feature requests for JaCoP version 2.4:


Dear all,

We are already planning release 2.4. We will include global constraint - bounded Knapsack constraint. Given time we will also look into creating a parser from Flatzinc to jaCoP.

Please let us know of other features you would like to see in future releases of JaCoP. Requests for additional global constraints and other requests which extend modeling power of JaCoP will have a preference. Please contact Radoslw Szymanek to submit your request ( radoslaw { . } szymanek [@] gmail ( dot ) com ).

best regards,

Radoslaw Szymanek

I especially look forward to the FlatZinc parser.


By the way, the News section has a feed (which I have missed): RSS 2.0, Atom.

Posted by hakank at 06:45 AM |

February 18, 2009

Minion version 0.8 released

Version 0.8 of Minion is released.

Minion is presented in the following way


MINION is a new constraint solver, which is very fast and scales well as problem size increases. Empirical results on standard benchmarks show orders of magnitude performance gains over state-of-the-art constraint toolkits. These gains increase with problem size --- MINION delivers scalable constraint solving.

MINION is a general-purpose constraint solver, with an expressive input language based on the common constraint modelling device of matrix models. Focussing on matrix models supports a lean, highly-optimised implementation. This contrasts with current constraint toolkits, which, in order to provide ever more modelling and solving options, have become progressively more complex at the cost of both performance and usability.

MINION is a black box from the user point of view, deliberately providing few options. This, combined with its raw speed, makes MINION a substantial step towards Puget's `Model and Run' constraint solving paradigm.

From the relase notes for version 0.8:


Users who use pre-compiled binaries should find any existing problem
files run the same as before. Building from source has changed
substantially, with Minion now requiring both the 'cmake' build system
and 'boost' C++ library. Full instructions are included in the source
package.

[a lot of bug fixes]

Note that Tailor is not part of the standard Minion distribution anymore; it is
released separately.

Tailor can be downloaded here.

Posted by hakank at 07:56 PM |

February 15, 2009

More Comet models, e.g. Nonogram, Steiner triplets, and different set covering problems

During the week some more Comet models has been published. Many of them are translations of my MiniZinc models.

Findings this week

Here are some findings for the previous week.

tryall again: Nonogram

One of the models I really wanted to make was Nonogram, since it would be interesting to compare with the MiniZinc model nonogram.mzn and the Gecode/R model nonogram.rb. The Comet model is nonogram.co.

The first version was very influenced by the MiniZinc model, and used tryall where the MiniZinc model used exists (see the previous post About 20 more constraint programming models in Comet for some more comments ablit this). But this was way too slow.

After some thoughts, I rewrote the tryall:s and it was getting faster. For a simple Nonogram problem like The Hen (see picture below), it originally took about 30 seconds. And after the changes, it now takes a fraction of a second (with alot of fewer propagations).

Nonogram The hen
. X X X . . . .
X X . X . . . .
. X X X . . X X
. . X X . . X X
. . X X X X X X
X . X X X X X .
X X X X X X . .
. . . . X . . .
. . . X X . . .

Still, compared to the Gecode/R (and - of course - Gecode) models, which uses "regular expression" representation, the Comet model is slow, but is faster the MiniZinc version. For example the Lambda picture (see below) takes about 12 seconds with the Comet model, compared to 0.5 seconds with the Gecode/R model. Well, it is nice to have some more optimization to do (or more probably, a complete remodelling)...

Nonogram: Lambda problem
. X X . . . . . . .
X . X X . . . . . .
X . . X . . . . . .
. . . X X . . . . .
. . . . X . . . . .
. . . X X X . . . .
. . . X X X . . . .
. . X X . X X . . .
. . X X . . X . . .
. X X . . . X X . X
. X X . . . . X X X
X X . . . . . X X .

To summarize, the main finding here was to replace two tryall statements with two decision variables, and change the rest accordingly. The model also include two symmetry breaking constraints ("alldifferent except 0" and ordering of a temporary array), but these make no big difference.

binary representation of set variables

As far as I know, Comet don't (yet) have a variable set variables (i.e. as decision variables). Instead, another representation must be used, and probably the most natural representation is an array of binary decision values representing each value of the set.

The following models use this representation:
* set_partition.co, partitions a range of integers 1..n in two equal sized sets where the sums and sums of squares of the two sets are equal.
* steiner_triplets.co: the well known problem of Steiner triples.
* partition_function.co, (partitions values according to a function of some kind)

Models

These models is available by My Comet page. As usual, the problems are presented in the header of the file.

Posted by hakank at 06:08 PM |

February 09, 2009

About 20 more constraint programming models in Comet

Since Some Comet constraint programming (CP) models, I've continued to translate some more of my (approx. 600) MiniZinc models to Comet. There are a few new models: game_theory_taha.co and fill_in_the_squares.co.

Findings this week

tryall

One finding this week is that tryall almost behaves like MiniZinc's exists, a very useful modelling tool. See for example the following models for the usage:
* Hidato puzzle
* Knights path
* SONET problem
* Word golf.

tryall behaves slightly different depending where it is placed: In the main explore/exploreall section, it may not generate all the solutions; but when placed in the using section, it generates all the solutions (and makes the model a bit slower).

Search strategies (labelling)

I've started to experiment with different search strategies (labelling), but for most of the models, the two builtin label and labelFF (first fail) are reasonable fast. This is an area I will look into more.

Other things

* strings/dictionaries: It is very nice to be able to use "real" strings in modelling. See for example Word golf, and Set covering deployment. The latter model also - just for fun - has a hash table for counting the number of occurrences of the selected countries.

* more than one models in the same program. MiniZinc only allows one model per file. As an experiment, game_theory_taha.co (two player zero sum game) solves first for one player, and then another model for the second player (which is not necessary since the solutions are a dual problem). Also, in Word golf, there is a loop of models solving for different ladder lengths.

The models

As usual, the description of the problem is included in the model, and a reference to my other model(s) of the same problem.

bus_schedule.co: Bus scheduling (Taha)
calculs_d_enfer.co: Calculs d'enfer puzzle (from the NCL manual)
crew.co: Crew scheduling (Gecode)
discrete_tomography.co: Discrete Tomography (one color model)
fill_in_the_squares.co: Fill in the squares, recreational mathematics. (from ZDC system). Origin unknown.
furniture_moving.co: Optimizing furniture moving (Marriott and Stuckey)
game_theory_taha.co: 2 player zero sum game (Taha). This uses the MIP (mixed integer programming) module.
heterosquare_cp.co: Heterosquare problem
hidato.co: Hidato puzzle
knights_path.co: Knight path
least_square.co: Least square (From Lundgren, Rönnqvist, Värbrand: "Optimeringslära"), using the MIP module.
max_flow_winston1.co: Maximum flow problem (Winston)
pandigital_numbers.co: Pandigital numbers (any base << about 12)
photo_problem.co: Photo problem
place_number_puzzle.co: Eight number placement puzzle
quasigroup_completion.co: Quasigroup completion problem.
Problem files:


set_covering.co: Set covering, placing of firestations (Winston)
set_covering_deployment.co: Set covering deployment
sonet_problem.co: SONET problem
survo_puzzle.co: Survo puzzle
traffic_lights.co:Traffic lights problem (CSPLib problem 16)
who_killed_agatha.co: Who killed agatha? (The Dreadsbury Mansion Murder Mystery, a automated reasoning problem)
word_golf.co: Word golf (word chain, word ladder), word_golf_len3.co: Data file with 2044 3-letter words.
young_tableaux.co: Young tableaux and partitions

Posted by hakank at 07:04 PM | | Comments (2)

February 04, 2009

Some of my models now at the Gecode/R site

In the comments of Some models in Gecode/R (Ruby interface to Gecode), Andreas Launila - the maintainer of Gecode/R - indicated that he wanted to include some of my models in the Gecode/R distribution.

As of writing, he has included two models in the Examples collection (as well as the SVN repository):
* nonogram.rb: Nonogram, painting by numbers
* minesweeper.rb: Minesweeper

Please note that Andreas has made some modifications which makes them much neater. For comparison, my original models is at My Gecode/R page.

Thanks Andreas!

Posted by hakank at 07:09 PM |