" /> My Constraint Programming Blog: May 2010 Archives

« April 2010 | Main | June 2010 »

May 23, 2010

SweConsNet 2010 - some brief comments

This Friday (May 22) I was attending SweConsNet Workshop 2010, co-located with SAIS Workshop 2010 in Uppsala. I wrote about the SweConsNet workshop and the talks in SweConsNet 2010: Abstract for the presentations.

Here are some brief comments.

As with the last year's workshop, it was very interesting to listen to all the talks, a good mix of theory and practical results. Somewhat to my own surprise, two of the talks I enjoyed most was the more theoretical by two PhD students: Serdar Kadıoğlu on Efficient Context-Free Grammar Constraints, and Jun He's on An automaton Constraint for Local Search. I also very much enjoyed Helmut Simonis two talks: CPTV - Generating Personalized TV Schedules, and VIZ - A Generic Visualization Toolkit for Constraint Programming (I'm not at all surprised of this enjoyment).

This year I finally met Pierre Flener who introduced me to SweConsNet in 2009 (and convinced me to talk at the 2009 workshop). I had a great time discussing many things with him, especially on the "Mosquito evening". Also, it was fun to met some readers of this blog, that actually use (or got inspiration from) my constraint programming models. Some business cards where exchanged.

Thanks to the organizers of this great workshop, and to all the persons I listened to/discussed with, for a great workshop (and for the nice weather in Uppsala :-). I hope we all met in SweConsNet Workshop 2011 .

Two new tools for MiniZinc, and a paper

Some days ago, the G12 group released two new tools for MiniZinc that I haven't used that much, but will hopefully do in the not to far future. Also, a recent paper is mentioned.

G12 IDE

The G12 IDE is an application for writing, running, visualizing, and debugging MiniZinc models. It is based on (the Java IDE) Eclipse. It can be downloaded here.

fzn2xcsp

fzn2xcsp is a tool for converting a subset of FlatZinc to XCSP 2.1. As of writing this tools is only available in the development version.

Paper: Philosophy of the MiniZinc challenge

Peter J. Stuckey, Ralph Becket, and Julien Fischer: Philosophy of the MiniZinc challenge (Springer Link). It is published in the Constraints Journal, but the paper is not available there (yet).
Abstract
MiniZinc arose as a response to the extended discussion at CP2006 of the need for a standard modelling language for CP. This is a challenging problem, and we believe MiniZinc makes a good attempt to handle the most obvious obstacle: there are hundreds of potential global constraints, most handled by few or no systems. A standard input language for solvers gives us the capability to compare different solvers. Hence, every year since 2008 we have run the MiniZinc Challenge comparing different solvers that support MiniZinc. In this report we discuss the philosophy behind the challenge, why we do it, how we do it, and why we do it that way.

Beside being an interesting paper about the MiniZinc challenge (see the MiniZinc homepage for links to the last two year's challenges, and this year's), it is also the first constraint programming paper where I'm mentioned (in the Acknowledgment). Thanks for this, I'm honored and appreciate it very much.

May 14, 2010

Optimizing shopping baskets: The development of a MiniZinc model

Yesterday (Thursday) was a holiday in Sweden and I had a busy day. Apart from writing a modulo propagator for ECLiPSe/ic, I also spend a lot of time with the Stack Overflow question How to use constraint programming for optimizing shopping baskets?. It asked for some tips (in a Java constraint programming system) for solving a problem of optimizing a shopping basket where different shops has different prices for items, as well as a delivery cost for orders below a certain limit.

You can read what I wrote and the developments of the models in my answer (I am hakank).

Update 2010-05-16: Added a better version. See below, Version 6.

First version

Even though the question was about a Java constraint system (I mentioned JaCoP, though), I rather quickly throw together a MiniZinc model instead as some kind of a prototype for a Java model. I'm a very lazy person and MiniZinc is excellent for prototyping.

This first version is shopping_basket.mzn (which actually include the next requirement: to handle shops which don't have all items). It solved the very simple example described in the problem section without any problem.

This model is quite straightforward: x is a matrix of 0/1 decision variables which shop to buy which item (the "knapsack" part). The more tricky part is to calculate the delivery costs if the total is below a certain limit (delivery_costs_limits). Here is the constraint part of the model:
constraint
   % we must buy all items (from some shop)
   forall(i in 1..num_items) (
       sum([x[i,j] | j in 1..num_shops]) = 1
   )
   /\ 
   total = sum(i in 1..num_items) (
       % costs of the products
       sum(j in 1..num_shops) (
          x[i,j]*costs[i,j]
       )
   ) + sum(j in 1..num_shops) (
       %  and delivery costs if total for a shop < limit
       let {
         var int: this_cost = sum([costs[i,j]*x[i,j] | i in 1..num_items])
       } in
       delivery_costs[j]*bool2int(this_cost > 0 /\ this_cost < delivery_costs_limits[j])
   );

The N/A problem: Not all shops sells all items

The next question was how to handle the "N/A" cases, i.e. for shops that don't have some item. It was solved by setting the price to a large number (999999 or 99999). However this is not very nice to the constraint solver. I really wanted to set these N/A to 0 (zero) but didn't get this correct (see below for a wrong turn on this).

As mentioned above the model shopping_basket.mzn includes the N/A problem.

Another representation

Almost always there are different approached how to model a problem. In the next version, shopping_basket2.mzn, I represented x - instead of a 0/1 matrix - as an array of length 1..num_items with the domains 1..num_shops to represent which shop to buy an item. The idea was that the constraint solvers now had much less work to do.

The constraint section is now simpler in some part, but calculating the delivery costs required a little more code:
constraint
 total = sum(i in 1..num_items) (
     costs[i,x[i]]
 ) + 
 sum(j in 1..num_shops) (
   let {
   var int: this_cost = 
     sum([costs[i,j]*bool2int(x[i]==j) | i in 1..num_items])
   } in
   delivery_costs[j]*bool2int(
      this_cost > 0 /\ 
      this_cost < delivery_costs_limits[j])
 );

Real data

The simple example data was easily solved for these two models, but the real challenge began when handling real data: 29 items and 37 shops. The two simplistic models was, however, not strong enough to handle this, so I started to think harder about the problem.

A wrong turn

The first attempt was continuing with the matrix approach and trying to be clever to represent N/A by 0 (zero), see above. This was done in shopping_basket3.mzn, but this model is plain wrong! The reason for this rather embarrissing bug was that the test case I used was not correct (completely mea culpa of course).

Final(?) version, part I: limiting the domains

OK, back to the drawing board. After some deep thoughts (i.e. an afternoon nap) I realized that the first models was too much of a proof-of-concept, too much prototype. In these I had broken one of the cardinality rules of constraint programming: not thinking about the domains of all decision variables.

In the first models the total cost (total) was defined as
var int: total :: is_output;
and the temporary variables this_cost was also defined as var int. This means that there is no limits of these variables (not even that they should be positive) which gives little hints for the constraint solvers.

The remedy is shown in the final(?) version shopping_basket5.mzn (shopping_basket4.mzn is basically the same thing for the matrix approach, and was not published).

Here the maximum total for any shop is first calculated, which can be quite large given the 99999 for N/A, but it is still limited and positive.
% total price
int: max_total :: is_output = 
      sum(i in 1..num_items) (
         max([costs[i,j] | j in 1..num_shops] )
      );
total is then defined with this limit:
var 0..max_total: total :: is_output; 
The temporary variable this_cost is handled accordingly.

Final(?) version, part II: labeling

This model was now in better shape, but still too slow. For all these versions I tried a lot of different labelings (search heuristics) and with many solvers (including the two MIP solvers, MiniZinc/mip and ECLiPSe/eplex, but they didn't accept the models).

I first saw a real improvement with the combination of Gecode/fz and the largest,indomain_max labeling. It solved the problem in 25 seconds (and with 69964 failures) :
total = 42013
x = [13, 20, 17, 18, 18, 13, 17, 17, 20, 13, 17, 17, 13, 13, 
     18, 17, 13, 13, 17, 8, 13, 36, 10, 17, 13, 13, 17, 20, 13] 
Just a minute or so after publishing this result (which seemed to please the person asking the question), I tested a different labeling, largest,indomain_split, and it solved the problem in 12 seconds (51013 failures). It gave a slightly different solution of where to buy item 12 (shown as bold):
total = 42013
x = [13, 20, 17, 18, 18, 13, 17, 17, 20, 13, 17, 13, 13, 13, 
     18, 17, 13, 13, 17, 8, 13, 36, 10, 17, 13, 13, 17, 20, 13]. 
These two solutions are the only two solutions for the (optimal) total of 42013. The test for all solutions takes about 1 second.

Some comments

This was a fun problem, quite simple but instructive what will happen when ignoring declaration of proper domain variables in the first versions of the models.

Even though the "real problem" was of the magnitude of 29 items and 37 shops (29 * 37 =1073), I am somewhat surprised that the problem was so hard to solve. This reminds me of the coins_grid problem which MIP solvers solve very fast, but the constraint solver have problems with it.

Update 2010-05-16: Version 6: Now faster

Well, version 5 was not the final version. Maybe this version 6 (shopping_basket6.mzn) is?

By two simple changes the problem is now solved in about 2 seconds and with 4460 failures (compared with 12 seconds and 51013). Here are the changes:
* The first change was the representation of N/A:s from 99999 to 0 (zero) . As noted above the former representation is not a good since it make all calculations, and the domains, unnecessary large.
* And finally, the following constraint states that all prices to consider must be larger than 0:
   forall(i in 1..num_items) (
      costs[i,x[i]] > 0
   ) 
Sigh. Of course! No defense of my silliness there is.

This also lessens the surprise considerable in Some comment above.

A modulo propagator for ECLiPSe/ic

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

Preamble

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

"Trickery" versions of modulo

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

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

A modulo propagator for ECLiPSe

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

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

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

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

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

May 11, 2010

MiniZinc version 1.1.2 released

Version 1.1.2 of MiniZinc has been released. Download.

Changes from version 1.1.1 (from NEWS):

G12 MiniZinc Distribution 1.1.2
--------------------------------
Bugs fixed in this release:

* The file diffn.mzn is now included in globals.mzn.

* A bug in mzn2fzn that caused it to abort when flattening int2float expressions has been fixed.

* An error in the FlatZinc specification has been fixed. All var types may have assignments, not just arrays.

* A bug in mzn2fzn that caused it generate an array_int_element constraint where an array_var_int_element constraint was required has been fixed. [Bug #122]

* A bug that caused mzn2fzn to generate invalid FlatZinc rather than emit an error message when the bound of an unbounded variable is taken has been fixed.


May 06, 2010

Some 40 new ECLiPSe models

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

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

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

The new models

Here is all the new ECLiPSe models.

Related

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