In late May, the
JaCoP team announced
Scala and JaCoP, a
Scala wrapper for JaCoP:
Scala programming language gets more and more acceptance in the community. It compiles to Java byte code and is executed using JVM. This makes it possible to use JaCoP directly in Scala by importing its packages. However, since Scala offers a nice way to define domain specific languages (DSL), we have developed an experimental implementation of the DSL for JaCoP solver.
Our implementation uses several Scala features to define a clear way of using JaCoP solver. We overloaded operators to specify easily arithmetical, logical and set constraints. We also use the package object to gather global constraints and search methods. This together with Scala features, such as implicit conversions, simplifies use of JaCoP and makes it easier to understand.
Some day after I started to test the first (beta) version and have had some interesting discussion with the developers, about bugs and also about syntax and functionality. Some weeks ago, they released a new version, which I personally think is better than the first version.
Programming in a high level programming language like Scala makes constraint programming much easier than using plain Java. With scalaJaCoP the JaCoP team has done a great job extending the world of constraint programming to other realms.
Below I explain some of the concepts I've met during my tests, as well as some gotchas. My public models has been collected in my
JaCoP/Scala page.
Update 2011-08-11: Some of the gotchas mentioned below has been fixed.
Documentation
The current release of scalaJaCoP don't include any documentation, just the wrapper code and about 20 examples. Here is a little guide how to learn more about it:
- JaCoP and the supported constraints are presented in JaCoP Library User’s Guide and JaCoP API
- The Scala file jacop.Scala (in scalaJaCoP directory) is where the core JaCoP is wrapped.
- The Scala file globals.scala (in scalaJaCoP directory) contains the global constraints supported by scalaJaCoP which is many (most) of JaCoP's global constraints. If you miss any JaCoP constraint, I think that the JaCoP team will be grateful for feedback.
Also, my
JaCoP/Scala models may hopefully be of some use.
Running scalaJaCoP
Running scalaJaCoP is quite easy after installing
JaCoP and
Scala:
- Download scalaJaCoP: Go to Sourceforge, select the latest JaCoP version and then download scalaJaCoP.zip. It contains two directories:
scalaJaCoP (core files) and ExamplesScala (examples)
- Compile the two core files: jacop.scala and global.scala:
scalac scalaJaCoP/*.scala
- Compile the examples:
scalac ExamplesScala/*.scala
- To compile an individual model:
scalac ExamplesScala/Adder.scala
scala ExamplesScala.Adder
The program fsc (fast background compiler) is faster when compiling:
fsc ExamplesScala/Adder.scala
scala ExamplesScala.Adder
Or as I tend to do:
fsc SendMoreMoney.scala && scala SendMoreMoney
Note: If running into trouble after updating scalaJaCoP, it might be a good idea to remove the class files.
SendMoreMoney.scala
Here is a complete scalaJaCoP model, the standard SEND+MORE=MONEY problem:
SendMoreMoney.scala. This examplifies much of what scalaJaCoP has to offer, in terms of high level constraints etc.
import scalaJaCoP._
object SendMoreMoney extends App with jacop {
// define variables
val s = new IntVar("s", 0, 9)
val e = new IntVar("e", 0, 9)
val n = new IntVar("n", 0, 9)
val d = new IntVar("d", 0, 9)
val m = new IntVar("m", 0, 9)
val o = new IntVar("o", 0, 9)
val r = new IntVar("r", 0, 9)
val y = new IntVar("y", 0, 9)
val all = Array(s,e,n,d,m,o,r,y)
// constraints
alldifferent(all)
// note the # operator
1000*s + 100*e + 10*n + d +
1000*m + 100*o + 10*r + e #=
10000*m + 1000*o + 100*n + 10*e + y
s #> 0
m #> 0
// labeling
val result =
satisfyAll(search(all, first_fail, indomain_min), printIt)
statistics
// output callback
def printIt() {
println("" + s.value + e.value + n.value + d.value + " + " +
m.value + o.value + r.value + e.value + " = " +
m.value + o.value + n.value + e.value + y.value)
}
}
Here are some things to note:
# for JaCoP's operators
The operators with "#" are operators that will be converted to JaCoP constraints. They are specially "tagged" in this way to distiguish them from Scala's operators. (Using operators without "#" are allowed in the current scalaJaCoP version but are deprecated.)
Output
Output can be done in two ways. Either as in this model by using a callback (which I happen to call
printIt) that is called for all solutions. The function is placed last in
satisfyAll. This is my preferred way.
The other way is to print according to JaCoP's default way of printing, i.e. just the last solution. Then
satisfyAll should not have any callback function, of course. Many of the examples in the scalaJaCoP distribution use this principle.
Statistics
For getting statistics of the solution, just place
statistics somewhere in the code. Then scalaJaCoP will print the (predefined) statistics information. Here is the statistics for the SendMoreMoney model:
Search statistics:
==================
Search nodes : 10
Search decisions : 5
Wrong search decisions : 5
Search backtracks : 5
Max search depth : 5
Number solutions : 1
Alternative version
Here is an alternative approach of the same problem (from
SendMoreMoney2.scala) using an array for the variables and
sum (as scalar product).
import scalaJaCoP._
object SendMoreMoney2 extends App with jacop {
val all = Array.tabulate(8)(i => new IntVar("x["+i+"]", 0, 9))
val Array(s,e,n,d,m,o,r,y) = all
alldifferent(all)
val values1 = Array(1000,100,10,1)
val values2 = Array(10000,1000,100,10,1)
( sum(List(s,e,n,d), values1)
+
sum(List(m,o,r,e), values1)
) #=
sum(List(m,o,n,e,y), values2)
s #> 0
m #> 0
// ... labeling and output as above
}
Other things in scalaJaCoP
Below are some other things I've found during my tests that may be of some help when programming in scalaJaCoP.
Defining constraint functions
Defining constraints (decompositions) is quite straightforward. Here is an example from
SequenceSum.scala to define
sequence_sum, to ensure that the sum of each subsequence of length
s sums to
m:
def sequence_sum(y: Array[IntVar], m: IntVar, s: Int) = {
val n = y.length
for(i <- 0 until n - s + 1) {
sum( Range(i,i+s).map(j => x(j) ).toList) #= m
}
}
Summing an array
In
Diet2 there is an example how to sum an array. Here we see both how to define and arrays, and also using
sum constraint over a collection of calculated values.
// define variables
val x = Array.tabulate(n)(i => new IntVar("x["+i+"]", 0, 10))
val cost = sum(Array.tabulate(n)(i => x(i)*price(i)).toList)
// constraint
Array.tabulate(n)(
nutr => sum(Array.tabulate(n)(i => x(i) * all(nutr)(i))) #>= limits(nutr)
)
Matrices
In scalaJaCoP, matrices can be defined as List of Lists, e.g. the connection matrix in
MapColoring.scala:
val connections =
List(List(0, 0, 1, 1, 1, 1),
List(0, 0, 0, 1, 0, 0),
List(1, 0, 0, 1, 1, 0),
List(1, 1, 1, 0, 1, 1),
List(1, 0, 1, 1, 0, 0),
List(1, 0, 0, 1, 0, 0))
The constraint to make the color different for the neighbours (the object of the model) is then defined as:
for (c1 <- 0 until num_countries;
c2 <- 0 until c1) {
if (connections(c1)(c2)==1) {
color(c1) #\= color(c2)
}
}
Note: the element access in the array (and matrix) are with
(), i.e. not brackets (
[]) as in Java.
Another note: there is no support for using an IntVar as an index in an IntVar array. For this the
element constraint must be used. See below for more comments about
element.
In
WhoKilledAgatha.scala there is an example of an
element constraint on a matrix.
yield
yield is not a JaCoP or Constraint Programming thing but a nice way in Scala to collect values given some condition or loop construct. The possibility to do these kind of constructs is why I like scalaJaCoP over the more complex way in Java.
Here's an example from
Sudoku to get the boxes:
for(i <- 0 until reg; j <- 0 until reg) {
alldistinct( (for{ r <- i*reg until i*reg+reg;
c <- j*reg until j*reg+reg
} yield x(r)(c)).toArray
)
Note that we have to convert the List made by the yield expression to an array (with
toArray) since this is what
alldictict expect.
Another example of
yield is in
Minesweeper.
IntVar intervals
This is a thing in JaCoP that has bitten me a few times before. JaCoP has defined the limits of
IntVar to the be
-10000000..10000000 and if a variable overflows it is considered
to fail. This is, for example, what happens in
DivisibleBy9Through1.scala for
n larger than 8.
element
Element in JaCop is another thing that I have had some problems with before, namely that
element is per default 1-base, and for use with 0-based one have to use an extra argument (offset) to the constraint to force it to be 0-based: e.g.
element(p(i-1), x, p(i), -1).
Here is a 0-based definition of
circuit (from
CircuitTest0Based.scala), as well as a "extractor" of the path from the circuit (
circuit_path), nice for representation of the solution.
def circuit_me(x: Array[IntVar]) = {
val len = x.length
val z = Array.tabulate(len)(i=>
new IntVar("z("+i+")", 0, len-1))
alldifferent(x)
alldifferent(z)
z(0) #= x(0)
// then put the orbit of x(0) in z(1..n-1)
for(i <- 1 until len) {
// we must use element/4, with an offset
element(z(i-1), x, z(i), -1)
}
z(len-1) #= 0
}
def circuit_path(x: Array[IntVar], p:Array[IntVar]) = {
alldifferent(p)
p(0) #= 0 // path always starts with 0
for(i <- 1 until n) {
element(p(i-1), x, p(i), -1)
}
}
(A 1-based version of the above is in
CircuitTest.scala.)
Some other models that use
element:
Langford.scala (Langford's number problem), and
WhoKilledAgatha.scala.
Reification
Unfortunately scalaJaCoP don't have a high level support (i.e. syntactic sugar) for reifications. In
AllDifferentExcept0.scala there is an example of how to use reification for decomposing the global constraint
alldifferent_except_0. The high level version could maybe be something like:
// This is NOT valid scalaJaCoP code:
for(i <- 0 until y.length; j <- 0 until i) {
(y(i) #\= 0 AND y(j) #\= 0) -> (y(i) #\= y(j))
}
As of now, one have to write it something like this, i.e. define a BoolVar
with the constraint, and then make the reification.
// alldifferent except 0
def alldifferent_except_0(y: Array[IntVar]) = {
for(i <- 0 until y.length; j <- 0 until i) {
val b = new BoolVar("b")
b <=> AND((y(i) #\= 0), (y(j) #\= 0));
b -> (y(i) #\= y(j))
}
}
A model that use many refications is
WhoKilledAgatha.scala. This was one of the models I struggled with quite a long time before I realized about the special treatment for 0-based element.
More about the #operator
Update 2011-08-11: Please note that these problems with #-operator has been fixed in the latest version of scalaJaCoP.
Another thing to be aware of in scalaJaCoP is when using both a (Scala) integer variable and a IntVar: it may matter if the (Scala) integer variable is to the left or right of the #operator. For example, in
Xkcd.scala (Xkcd knapsack problem) there are some examples of this, shown here.
Here
x is an
IntVar array, defined as:
val x = Array.tabulate(num_prices)(i => new IntVar("x["+i+"]", 0, 10))
The object of the model is to ensure that the number of items in
x sums to a certain
total, namely 1505, which is defined as a Scala
val variable.
val total = 1505
Now, if
total is on the
left side of the
#= operator, Scala cannot figure out how to convert to an IntVar:
// don't work
total #= sum(Array.tabulate(num_prices)(i=> x(i)*price(i)))
This results in errors like
error: reassignment to val.
However, there is a couple ways that do work, for example moving the integer variable to the right side, which I tend to do:
sum(Array.tabulate(num_prices)(i=> x(i)*price(i))) #= total
Or explicitly convert
total to an
IntVar with
intToIntVar or
(:IntVar)
intToIntVar(total) #= sum(Array.tabulate(num_prices)(i=> x(i)*price(i)))
(total:IntVar) #= sum(Array.tabulate(num_prices)(i=> x(i)*price(i)))
Often, this is not much a problem, but it can be
abs (decomposition with reification)
Update 2011-08-11: The latest version of scalaJaCoP includes a definition of abs, so this comment (and the defined function) is not needed anymore.
In
AllIntervals.scala, I needed the
abs constraint but I couldn't find any in scalaJaCoP. Here is a brutal version using reifications, hardwired to handle the case of
c=abs(a-b):
def my_abs(a:IntVar, b:IntVar, c:IntVar) {
val b1 = new BoolVar("b1")
b1 <=> (a #> b)
b1 -> (c #= a - b)
~b1 -> (c #= b - a)
}
(This can most probably be written both more elegant and more general.)
Number of solutions/Timeout
Among the things that where added to the new version of scalaJaCoP was support for timeout and for getting a specific number of solutions, both very useful, especifally for debugging.
-
numberSolutions(n) where n is the number of solutions to print
-
timeOut(s) where s is in seconds
My JaCoP/Scala models
All my public scalaJaCoP models are collected in my
JaCoP/Scala page but listed here for easy access. Most of them have also been implemented in another CP systems (see
Common constraint programming problems).