My Constraint Programming Blog

In A first look at Google CP Solver/Python (Google or-tools) I showed my first models in Google CP Solver (or-tools).

Laurent Perron (the designer of the Google CP Solver) was kind enough to comment and improve some of these models. Thanks, Laurent!

Decomposition of alldifferent_except_0

Model: alldifferent_except_0.py

Laurent mentioned that reifications can be stated much simpler than my approach. My first version was:

def alldifferent_except_0(solver, a):
    n = len(a)
    for i in range(n):
        for j in range(i):
            # This syntactic sugar would be nice to have:
            # solver.Add( ((a[i] != 0) and (a[j] != 0)) -> (a[i] != a[j] ) )            
            bi = solver.BoolVar('bi')
            bj = solver.BoolVar('bj')
            bij = solver.BoolVar('nij')
            solver.Add(solver.IsDifferentCstCt(a[i],0, bi))
            solver.Add(solver.IsDifferentCstCt(a[j],0, bj))
            solver.Add(solver.IsDifferentCt(a[i],a[j], bij))
            solver.Add(bi*bj <= bij)

However, these temporary variables don't have to be declared and added to the solver. Instead one can write

bi = solver.IsDifferentCstVar(a[i],0)

Note the slightly different method name. The Var at the end means that the method returns a variable.

So, the decomposition is now much nicer and easier to understand.

def alldifferent_except_0(solver, a):
   n = len(a)
   for i in range(n):
      for j in range(i):
          bi = solver.IsDifferentCstVar(a[i],0)
          bj = solver.IsDifferentCstVar(a[j],0)
          bij = solver.IsDifferentVar(a[i],a[j])
          solver.Add(bi*bj <= bij)

This following one liner version works but is less readable. (Yes, I'm trying to push the limits. :-)

# ...
solver.Add(solver.IsDifferentCstVar(a[i],0)*
           solver.IsDifferentCstVar(a[j],0) <=
           solver.IsDifferentVar(a[i],a[j]))

Young tableaux and partition

Model: young_tableaux.py

The improvement here was about the same as for alldifferent_except_0. The following constraints:

        b = [solver.BoolVar("b%i"%j) for j in range(n)]
        for j in range(n):
            solver.Add(b[j] == solver.IsLessOrEqualCstVar(x[(i,j)],n))

is replaced with

         b = [solver.IsLessOrEqualCstVar(x[(i, j)], n) for j in range(n)]
         solver.Add(p[i] == solver.Sum(b))

Again, there are not so many variables sent to the constraint store. Alternative it could be written in a more compact form:

solver.Add(p[i] == solver.Sum([solver.IsLessOrEqualCstVar(x[(i, j)], n)
                               for j in range(n)]))

Coins grid

Model: coins_grid.py

Laurent suggested several improvements in this model:

• First, I had forgot to add objective to the monitor list.
• The objective (z) is not a (declared) decision variable any more. It was defined as

  z = solver.IntVar(0,1000000, 'z')
  # ...
  solver.Add(solver.Sum([x[(i,j)]*abs(i-j)*abs(i-j) 
                        for i in range(n) for j in range(n)]) == z)
  # ...
  

  Now the return value of solver.Sum is used. The sum is also slightly redefined (skipping two abs calls):

  objective_var = solver.Sum([x[(i, j)] * (i - j) * (i - j)
                             for i in range(n) for j in range(n)])
  

• Added solution.AddObjective(objective_var)
• Using the value strategy solver.ASSIGN_MAX_VALUE instead of solver.ASSIGN_MIN_VALUE.
• The rows/column summation use the faster solver.SumEquality instead of solver.Sum

Hidato

My own Hidato model was quite ugly and slow.

Laurent wrote a much more elegant version (hidato_laurent.py) using, amongst other things, the global constraint solver.AllowedAssignments. This solves the hardest problem in the file in a blink with just a few failures.

A humbling lesson.

New model: A "general" alphametic solver

Model: alphametic.py

Yesterday I wrote a "general" alphametic solver which solves used defined (from the command-line) problems of the form "SEND+MORE=MONEY". It only solves addition problems of the form NUMBER_1+NUMBER_2...+NUMBER_N_1 = NUMBER_N where the last number is the sum (so it's not very general).

The program has the following usage:

python alphametic.py
         ->  solves SEND+MORE=MONEY in base 10
    
python alphametic.py  'SEND+MOST=MONEY' 11
         -> solver SEND+MOST=MONEY in base 11

python alphametic.py TEST 
         -> solve some test problems in base 
                   (defined in test_problems())

Compare with the Zinc model alphametic.zinc which use the same basic ideas. However Zinc don't have Python's excellent support for strings and sets.