« Gecode version 3.4.2 released | Main | Google CP Solver: Regular constraint, Nonogram solver, nurse rostering, etc »

Some new Google CP Solver/Python models

In A first look at Google CP Solver/Python (Google or-tools) and Improvements of some Google CP Solver models I presented my first Google CP Solver models. However, some of my traditional learning problems was not implemented then since I didn't know how to implement certain things with the solver.

Here are implementations of some of these omitted models as well as some other new models. They are is listed below, in all about 40.

Furniture moving (cumulative)

Model: furniture_moving.py

The reason I didn't implement this problem before was that there is no built-in cumulative constraint. This model includes an experimental version of this constraint based on the MiniZinc implementation: 
# Parameters:
#
# s: start_times    assumption: array of IntVar
# d: durations      assumption: array of int
# r: resources      assumption: array of int
# b: resource limit assumption: IntVar or int
#
def my_cumulative(solver, s, d, r, b):
    
    # tasks = [i for i in range(len(s))]
    tasks = [i for i in range(len(s)) if r[i] > 0 and d[i] > 0]
    times_min = min([s[i].Min() for i in tasks])
    times_max = max([s[i].Max() + max(d) for i in tasks])
    for t in xrange(times_min, times_max+1):
        bb = []
        for i in tasks:
            c1 = solver.IsLessOrEqualCstVar(s[i], t)  # s[i] <= t
            c2 = solver.IsGreaterCstVar(s[i]+d[i], t) # t < s[i] + d[i]              
            bb.append(c1*c2*r[i])
        solver.Add(solver.Sum(bb) <= b)

    # Somewhat experimental:
    # This constraint is needed to constrain the upper limit of b.
    if not isinstance(b, int):
        solver.Add(b <= sum(r))
As noted above, this is experimental but seems to solve the problem at hand.

Who killed Agatha: Element and reifications

Model: who_killed_agatha.py

This was another problem I postponed of the standard set of problems, much because I thought it should be hard (or tedious) to convert the many element constraints and reifications to Google CP Solver. However, this was not really true: even if it's not as easy as in MiniZinc or Comet it was quite straightforward.

The problem formulation is from The h1 Tool Suite (originally from F. J. Pelletier: Seventy-five problems for testing automatic theorem provers, Journal of Automated Reasoning, 2: 216, 1986):
Someone in Dreadsbury Mansion killed Aunt Agatha. Agatha, the butler, and Charles live in Dreadsbury Mansion, and are the only ones to live there. A killer always hates, and is no richer than his victim. Charles hates noone that Agatha hates. Agatha hates everybody except the butler. The butler hates everyone not richer than Aunt Agatha. The butler hates everyone whom Agatha hates. Noone hates everyone. Who killed Agatha?
Some examples:

The constraint "A killer always hates, and is no richer than his victim." is translated to this constraint in MiniZinc and Comet: hates[the_killer, the_victim] == 1. In Google CP Solver we state this with an Element constraint: 
solver.Add(solver.Element(hates_flat,the_killer*n+the_victim) == 1)
There are also quite a few reifications and logical operators in this model. As I wrote in Improvements of some Google CP Solver models, there are translated straight forward into calls like this (for the constraint Charles hates noone that Agatha hates. : 
#  (hates[agatha, i] = 1) => (hates[charles, i] = 0),
for i in range(n):
    b1a = solver.IsEqualCstVar(hates[agatha][i], 1)
    b1b = solver.IsEqualCstVar(hates[charles][i], 0)
    solver.Add(b1a-b1b <= 0)
(We don't have to use Element here since the index i is of type int.)

The actual constraint to the solver store (b1a-b1b<=0) is standard OR translations of the condition (see below).

Another model with a lot of Element is a_round_of_golf.py.

Mr Smith problem (logical operators)

Model: mr_smith.py

This problem is a logic puzzle taken from an IF Prolog example:
The Smith family and their three children want to pay a visit but they do not all have the time to do so. Following are few hints who will go and who will not: - If Mr Smith comes, his wife will come too. - At least one of their two sons Matt and John will come. - Either Mrs Smith or Tim will come, but not both. - Either Tim and John will come, or neither will come. - If Matt comes, then John and his father will also come.
As mentioned earlier, Google CP solver don't have a syntactic sugar for boolean (logic) operations on decision variables, such as AND, OR, IF, EQ. Instead one have to rely on traditional translations ("tricks") used in IP modeling. For example the constraint If Mr Smith comes, his wife will come too (which is stated as Mr_Smith -&gr; Mrs_Smith in other systems), is translated here into: 
solver.Add(Mr_Smith - Mrs_Smith <= 0)
Here is a list of some other similar translations. a and b are two BoolVar/IntVar variables (with domain 0..1). 
a AND b: a * b == 1
a OR b: a + b >= 1
a XOR b: a + b == 1
IF a THEN b: a - b <= 0
IF AND ONLY IF a THEN b: a == b (i.e. A EQ B)
There are other ways of formulating these with may be more natural for the problem at hand. Also, for more complex constraints one may have to tweak a little more. For more about this, see the excellent book Model Building in Mathematical Programming by H. Paul Williams (ISBN: 9780471997887), especially chapter 9.

The new models

Here are all the new models, also available via my Google CP Solver page. They are also at the Google Code SVN repository.

Posted by hakank on October 27, 2010 08:33 PM |