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.
The reason I didn't implement this problem before was that there is no built-in
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):
The constraint "A killer always hates, and is no richer than his victim." is translated to this constraint in MiniZinc and Comet:
The actual constraint to the solver store (
Another model with a lot of
This problem is a logic puzzle taken from an IF Prolog example:
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.pyThe 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.pyThis 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.pyThis 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.- a_round_of_golf.py: A Round of Golf puzzle (Dell Logic Puzzles)
- all_interval.py: All interval problem (CSPLib #7)
- broken_weights.p: Broken weights problem
- car.p: Car sequencing
- coins3.py: Coin application (from the ECLiPSe book)
- costas_array.p: Costas array
- covering_opl.py: Set covering problem (from OPL)
- crew.py: Crew allocation problem
- crypta.py: Cryptarithmetic puzzle (standard Prolog benchmark)
- crypto.py: Cryptarithmetic puzzle (standard Prolog benchmark)
- curious_set_of_integers.py: Curious set of integers (Martin Gardner)
- divisible_by_9_through_1.py: Divisible by 9 through 1 puzzle (from Solving Combinatory Problems with LINQ
- einav_puzzle.py: Problem from A programming puzzle from Einav. Laurent Perron made a (slightly) faster and neater variant: einav_puzzle2.py
- eq10.py: Eq 10 (standard benchmark problem)
- eq20.py: Eq 20 (standard benchmark problem)
- fill_a_pix.py: Fill-a-pix (a Minesweeper variant)
Data files: - furniture_moving.p: Furniture moving (with an experimental
cumulative) (see above) - futoshiki.py: Futoshiki problem
- grocery.py: Grocery puzzle
- just_forgotten.py: Just forgotten puzzle (Enigma 1517)
- langford.py: Langford's number problem (CSPLib problem #24)
- lectures.py: Lectures problem (simple scheduling problem)
- marathon2.py: Marathon puzzle (from Xpress)
- max_flow_taha.py: Max flow problem (Taha)
- max_flow_winston1.py: Max flow problem (Winston)
- mr_smith.py: Mr Smith puzzle (from IF Prolog)
- nontransitive_dice.py: Nontransitive dice
- olympic.py: Olympic puzzle (Prolog benchmark)
- organize_day.py: Organizing a day (simple scheduling problem from ECLiPSe)
- p_median.py: P-median problem (OPL)
- pandigital_numbers.py: Pandigital numbers
- photo_problem.py: Photo problem
- post_office_problem2.py: Post office problem (Winston)
- safe_cracking.py: Safe cracking problem (Oz Primer)
- scheduling_speakers.py: Scheduling speakers (from Rina Dechter)
- secret_santa.py: Secret Santa problem I
- secret_santa2.py: Secret Santa problem II
- set_covering_skiena.py: Set covering (Steven Skiena)
- stable_marriage.py: Stable marriage problem (OPL)
- traffic_lights.py: Traffic lights problem (CSPLib problem #16)
- who_killed_agatha.py: Who killed Agatha? (The Dreadsbury Mansion Murder Mystery), standard benchmark in theorem proving