« Version 1.3.2 of G12 MiniZinc released | Main | Google or-tools has released support for LP/IP »

A first look at Google or-tools' Java interface

The Java interface for Google or-tools was released some week ago, and I have now ported some of my Python models to Java (about 35 models). See my Google CP Solver page / Java models for a list of them. Some of them has also been committed to the SVN repository of the or-tools project.

In A first look at Google CP Solver/Python (Google or-tools) I described the Python interface for Google or-tools. Since much of what is written there is applicable with the Java interface as well, I here concentrate on the differences between these two versions.

The porting was surprisingly easy to do for most models, since all the work of looking up the proper API call to use was already done for the Python models. See below for some of the differences.

I found very few unexpected things in the Java version. The Python interface (being slightly older) had some bugs when I first tested it, but they where fixed very fast by Laurent Perron and his colleagues.

Example: SEND + MORE = MONEY

One difference between the Java interface and the Python interface is that the Python interface has some more syntactic sugar, e.g. it recognizes the arithmetic operators (+, -, /, *), and (dis)equality: ==, !=. The Java interface has none of this which caused me some pain to translate.

For example: To get the result of two numbers (a + b == c) in Python: 
  solver.Add(a + b == c);
In the Java interface one has to do use two methods (addSum and makeEquality): 
  solver.addConstraint(solver.makeEquality(solver.makeSum(a, b), c));
Here is a table of corresponding operations: 
Python       Java
----------------------------
a + b        makeSum(a, b)
a * b        makeProd(a, b)
a - b        makeDifference(a, b)
- a          makeOpposite(a)
a / b        makeDiv(a, b)
a == b       makeEquality(a, b)
a != b       makeDifference(a, b)
Example: the usual core of the SEND + MORE == MONEY problem can be written in a Python model (and similar in other constraint solver systems): 
# define variables etc
# ...
#
solver.Add(      s*1000 + e*100 + n*10 + d +
                 m*1000 + o*100 + r*10 + e ==
           m*10000 + o*1000 + n*100 + e*10 + y
However, using this approach is not really doable with the Java interface, since it would require a lot of makeSum and makeProd, etc. A better way (and this is probably a general advice for the Python interface as well) is to instead use a scalar product: makeScalProd or makeScalProdEquality. Here is one way, where we also see how the decision variables is declared. 

Solver solver = new Solver("SendMoreMoney");

int base = 10;
IntVar s = solver.makeIntVar(0, base - 1, "s");
IntVar e = solver.makeIntVar(0, base - 1, "e");
IntVar n = solver.makeIntVar(0, base - 1, "n");
IntVar d = solver.makeIntVar(0, base - 1, "d");
IntVar m = solver.makeIntVar(0, base - 1, "m");
IntVar o = solver.makeIntVar(0, base - 1, "o");
IntVar r = solver.makeIntVar(0, base - 1, "r");
IntVar y = solver.makeIntVar(0, base - 1, "y");

IntVar[] x = {s,e,n,d,m,o,r,y};

IntVar[] eq = {s,e,n,d,  m,o,r,e, m,o,n,e,y};
int[] coeffs = {1000, 100, 10, 1,            //    S E N D +
                1000, 100, 10, 1,            //    M O R E
                -10000, -1000, -100, -10, -1 // == M O N E Y
};
solver.addConstraint(
      solver.makeScalProdEquality(eq, coeffs, 0));
// s > 0
solver.addConstraint(
      solver.makeGreater(s, 0));
// m > 0
solver.addConstraint(
      solver.makeGreater(m, 0));
// all different
solver.addConstraint(
      solver.makeAllDifferent(x, true));
This approach, using scalar products, is implemented in SendMoreMoney.java. In SendMoreMoney2.java I experimented with some different approaches of coding this problem, some quite hairy.

Search, labeling, output

There is not really much difference how to do search and labeling in the Java version compared to the Python version. Here is the search section of SendMoreMoney.java: 
DecisionBuilder db = solver.makePhase(x,
                                       solver.INT_VAR_DEFAULT,
                                       solver.INT_VALUE_DEFAULT);
solver.newSearch(db);
while (solver.nextSolution()) {
   for(int i = 0; i < 8; i++) {
     System.out.print(x[i].toString() + " ");
   }
   System.out.println();
 }
solver.endSearch();

// Statistics
System.out.println();
System.out.println("Solutions: " + solver.solutions());
System.out.println("Failures: " + solver.failures());
System.out.println("Branches: " + solver.branches());
System.out.println("Wall time: " + solver.wall_time() + "ms");
One thing that is different, is how to define the variables for labeling. In Python it is quite easy to concatenate two arrays of decision variables like this: 
solver.makePhase(x + y, ...);
But this don't work as easy in Java (being Java). I tend to call such a labeling array for all and fill in all the IntVar from x and y; there are other way of doing this of course. On the other hand, the Python interface cannot handle labeling on matrices (multidimensional tuples), and in these models I also had to rely on a flattened "view" of this matrix (often called x_flat or something like that).

Python also has niftier shortcuts for creating temporary arrays using array comprehensions. For example in the Python version of set_covering.py one can write the following: 
# ensure that all cities are covered
for i in range(num_cities):
   b = [x[j] for j in range(num_cities) if distance[i][j] <= min_distance]
   solver.Add(solver.SumGreaterOrEqual(b, 1))
This I have translated to Java code using an ArrayList instead (SetCovering.java): 
// ensure that all cities are covered
for(int i = 0; i < num_cities; i++) {
  ArrayList b = new ArrayList();
  for(int j = 0; j < num_cities; j++) {
    if (distance[i][j] <= min_distance) {
      b.add(x[j]);
    }
  }
  solver.addConstraint(
      solver.makeSumGreaterOrEqual(b.toArray(new IntVar[1]), 1));
}

Decompositions, and somewhat under the hood

As far as I know, there is not (yet) support for modulo operations with decision variables (IntVar's). Since modulo is a favorite operator of mine, I implemented a version in DivisibleBy9Through1.java which corresponds quite closely to the Python version divisible_by_9_through_1.py. Here is the Python version: 
def my_mod(solver, x, y, r):

    if not isinstance(y, int):
        solver.Add(y != 0)

    lbx = x.Min()
    ubx = x.Max()
    ubx_neg = -ubx
    lbx_neg = -lbx
    min_x = min(lbx, ubx_neg)
    max_x = max(ubx, lbx_neg)

    d = solver.IntVar(min_x, max_x, 'd')    

    if not isinstance(r, int):
        solver.Add(r >= 0)
        solver.Add(x*r >= 0)

    if not isinstance(r, int) and not isinstance(r, int):
        solver.Add(-abs(y) < r)
        solver.Add(r < abs(y))
        
    solver.Add(min_x <= d)
    solver.Add(d <= max_x)
    solver.Add(x == y*d+r)
The Java version is not very different, however I simplified it somewhat and requires that all arguments are IntVar's: 
public static void my_mod(Solver solver, IntVar x, IntVar y, IntVar r) {
        
  long lbx = x.min();
  long ubx = x.max();
  long ubx_neg = -ubx;
  long lbx_neg = -lbx;
  int min_x = (int)Math.min(lbx, ubx_neg);
  int max_x = (int)Math.max(ubx, lbx_neg);

  IntVar d = solver.makeIntVar(min_x, max_x, "d");
    
  // r >= 0
  solver.addConstraint(
        solver.makeGreaterOrEqual(r,0));

  // x*r >= 0
  solver.addConstraint(
      solver.makeGreaterOrEqual(
          solver.makeProd(x,r).Var(), 0));

  // -abs(y) < r
  solver.addConstraint(
      solver.makeLess(
          solver.makeOpposite(
              solver.makeAbs(y).Var()).Var(), r));

  // r < abs(y)
  solver.addConstraint(
      solver.makeLess(r,
          solver.makeAbs(y).Var().Var()));

  // min_x <= d, i.e. d > min_x
  solver.addConstraint(
        solver.makeGreater(d, min_x));


  // d <= max_x
  solver.addConstraint(
        solver.makeLessOrEqual(d, max_x));

  // x == y*d+r
  solver.addConstraint(
        solver.makeEquality(x,
            solver.makeSum(
               solver.makeProd(y,d).Var(),r).Var()));
}
Note: This implementation is based on the ECLiPSe version mentioned in A Modulo propagator for ECLiPSE. Here is the ECLiPSe Prolog source code: modulo_propagator.ecl.

Another example is the decomposition of the global constraint circuit (from Circuit model) based on some observations about the "orbit" of x. 
public static void circuit(Solver solver, IntVar[] x) {

  int n = x.length;
  IntVar[] z = solver.makeIntVarArray(n, 0, n - 1, "z");

  solver.addConstraint(
      solver.makeAllDifferent(x, true));
  solver.addConstraint(
      solver.makeAllDifferent(z, true));

  // put the orbit of x[0] in z[0..n-1]
  solver.addConstraint(
        solver.makeEquality(z[0], x[0]));
  for(int i = 1; i < n-1; i++) {
    solver.addConstraint(
        solver.makeEquality(z[i], 
            solver.makeElement(x, z[i-1]).Var()));
  }

  // z may not be 0 for i < n-1
  for(int i = 1; i < n - 1; i++) {
    solver.addConstraint(
          solver.makeNonEquality(z[i], 0));
  }
        
  // when i = n-1 it must be 0
  solver.addConstraint(
        solver.makeEquality(z[n - 1], 0));

}

Some benchmark: n-queens

Below is some statistics for the the n-queens problem, implemented in NQueens2 model. The constraint section is: 
IntVar[] q = solver.makeIntVarArray(n, 0, n-1, "q");

solver.addConstraint(solver.makeAllDifferent(q, true));

IntVar[] q1 = new IntVar[n];
IntVar[] q2 = new IntVar[n];
for(int i = 0; i < n; i++) {
  q1[i] = solver.makeSum(q[i], i).Var();
  q2[i] = solver.makeSum(q[i], -i).Var();
}
solver.addConstraint(
    solver.makeAllDifferent(q1, true));
solver.addConstraint(
    solver.makeAllDifferent(q2, true));
Here is the timings (for one solution): 
     N    Failures       Branches      Wall time Required
                                                 memory
  -------------------------------------------------------
     8      3             9              2ms
    10      5            16              3ms
    50     15            70              4ms
   100     12           120             10ms
   200      1           198             22ms
   500      2           496            126ms
   501      6           503            128ms
  1000      0           996            504ms 
  2000      0          1995           2164ms
  3000      2          3001           5119ms
  4000      0          3999           9493ms
  5000      1          4994          15803ms
  6000      1          5996          24511ms
  7000      0          6997          34354ms   1.1Gb
  8000      0          7996          46985ms   1.5Gb
  9000      0          8996          62905ms   1.8Gb
 10000      9          9999          81312ms   2.3Gb
I ran these tests on a Linux Ubuntu 10.4 Lynx, with 12Gb RAM, 8 cores, (Intel Core i7 930 @ 2.80GHz). Note: the "Wall time" is the time reported by the solver, and the "Required memory" is manually via the "top" command for the running process.

I wondered if the Python version nqueens3.py that use the same constraints and labeling as the Java version should have any different result. Well, it has exactly the same failures and branches as the Java version (no surprise since it use the same solver engine). Also the wall times and memory usage are almost identical.

Related

See also these blog posts, all about the Python interface:

Some kind of conclusion

As mentioned above, it was quite easy to port the Python models to Java since they share a lot of common API (with some difference in details). If there is no requirement about the language to use, I personally would probably prefer the Python interface since it's more high level and is less verbose than the Java interface (I like brevity).

Maybe (repeat maybe) I will also have a take on Google or-tools' C++ interface.

My Google or-tools Java models

Here are my Java models. All of them where ported from existing Python models. They are also available at Google CP Solver page / Java models (the Python models is available from the same page). For implementation of these problems in other constraint programming systems, see Common constraint programming problems.

Posted by hakank on March 29, 2011 10:18 PM |