The Java/Scala choice to implement CP Solvers

I recently started to implement a solver in Java during my free time. I choosed Java for several reasons:

- it is still by far the most popular language

- integration and deployment facility of a Java project + portability

- most of my colleagues at n-Side know Java and they are less familiar with C++

- the development tools (eclipse/InteliJ) are wonderful

- good tradeoff between speed and ease of modeling

Of course the price to pay is this factor 3. I like a lot the point of view of Nate Brixius (developer of Solver Foundation) about that. Here are few extracts about his blog post:

"I did standard critical path scheduling in both C# and C++ and found that the C# version was only 10-15% slower. We went with C# and in the course of development we were able to find algorithmic improvements that resulted in a faster implementation that the original C++ codebase. "

"Many programmers (myself included) are much more productive writing C# code. This gives me more time to investigate possible algorithmic improvements, write good unit tests, etc. There are opportunity costs!"

This is also true for CP solvers, what really makes a difference to solve a problem with CP is the functionalities available in your solver: the modeling facility, the global constraints available, how easy it is to write a custom search, to do a LNS, restarts, make parallelisation ...

I'm certainly not the first one to have chosen Java to develop a CP solver. Two popular open source CP solvers are implemented in Java: Choco and Jacop. There is also a standardization project for solvers in Java.

One of my colleague (Gilles) at n-Side is a real "Scala Enthutiast" and made me discover this wonderful language called Scala.

Since that time, I don't think anymore that writing a model in Java is very convenient...

The really good thing about Scala is that its syntax is so flexible that you can use it to write DSL (If find Scala much better than Python to do that)

But the other cool thing about Scala is that it is at least as efficient as Java.

A comparison between C++, Java, Scala and Go made by Google was published at the Scala Days a few days ago on an algorithmic benchmark:

Scala was about 3 times slower and Java 5 times slower than an optimized C++ code.

Of course I didn't throw away all my Java implem but I started a Scala wrapper on top of it for fun (integration between Scala and Java is perfect in both direction). I choosed to make a syntax quite close to OPL/Comet because I'm used to it and I find it very clear. Here is how the Queen problem looks like in my Scala wrapper:

object Queens  extends Model {
   def main(args: Array[String]) {
  
      val cp = new CPSolver()
      
      val n = 6 //number of queens
      val Queens = 0 until n
      //variables
      val queens = for(i <- Queens) yield CPVarInt(cp,1 to n)
      
      var nbsol = 0
      cp.onSolution {
       nbsol += 1
      }
      
      cp.solveAll subjectTo {
       cp.add(alldifferent(queens))
       cp.add(alldifferent(for(i <- Queens) yield queens(i) + i))
       cp.add(alldifferent(for(i <- Queens) yield queens(i) - i))
      } exploring {
       //exploration of the search tree
       new Binary(queens)
      }

      //print some statistics
      println("#sol",nbsol)
      cp.printStats()
    }
}

Again, it seems that I'm not the only one to have taken that decision. The Jacop team also adopted the same approach and started to make a wrapper for their solver. Here is the Queen model in Jacop/Scala:

object Queen extends Application with jacop {

  val n = 50

  val q: List[IntVar] = for (i <- List.range(0, n)) yield new IntVar("q"+i, 0, n)

  def noattack(i: Int, j: Int, qi: IntVar, qj: IntVar) = {
 qi     != qj 
 qi + i != qj + j 
 qi - i != qj - j 
  }

  for (i <- 0 until n; j <- i+1 until n) noattack(i, j, q(i), q(j))

  val result = satisfy( search(q, first_fail, indomain_middle) )

  if (result) 
    q.foreach(qi => {
      for( i <- 0 until n) 
  if (qi.value() == i) print(" # ") else print(" . ")
      println

    })
  else println("No solution")
}

I think we may see even more Scala wrapper for CP solvers in the near future...