" /> My Constraint Programming Blog: August 2012 Archives

« May 2012 | Main | October 2012 »

August 02, 2012

A first look at OscaR (Scala in OR), former Scampi

OscaR - (Scala in OR) is a constraint solver for Scala (former called Scampi). The source is here (Bitbucket).

From the Wiki:
OscaR (Scala in OR) is a Scala toolkit to solve Operations Research problems. The techniques currently available in OscaR are:
The part I have focused on is Constraint Programming which is presented in these links: Pierre Schaus (and his blog Constraint Programming ) should be mentioned here as well, since he is the creator of much of the CP support in OscaR. Thanks Pierre for a great system and for all your help.

Modeling in OscaR

OscaR should be seen as a high level CP modeling language, since it has a lot of operator overloaded, see example of this below. (About the only thing I miss regarding this is a "sugared" version of element, i.e. x(y) where y is a decision variable. More about that later on...).

I should perhaps mention that this project has been both learning OscaR and learning more about Scala. Scala is a very nice programming language with suite me quite well since it supports both imperative object oriented way of thinking as well as pure functional approach (though I have to confess that in some models this is not apparent at all).

Most examples shown in this blog post are from my OscaR page. There are other OscaR examples in the repo here.

First model: SEND+MORE=MONEY

Here is the full model of SEND+MORE=MONEY problem (it's also available at SendMoreMoney.scala, and - as mentioned - also in the OscaR repo, see below): 
package oscar.examples.cp.hakank
import oscar.cp.modeling._
import oscar.cp.search._
import oscar.cp.core._

object SendMoreMoney {
  def main(args: Array[String]) {
    val cp = CPSolver()
    val S = CPVarInt(cp, 0 to 9)
    val E = CPVarInt(cp, 0 to 9)
    val N = CPVarInt(cp, 0 to 9)
    val D = CPVarInt(cp, 0 to 9)
    val M = CPVarInt(cp, 0 to 9)
    val O = CPVarInt(cp, 0 to 9)
    val R = CPVarInt(cp, 0 to 9)
    val Y = CPVarInt(cp, 0 to 9)
    val all = Array(S,E,N,D,M,O,R,Y)

    cp.solveAll() subjectTo {
      cp.add(       S*1000 + E*100 + N*10 + D +
                    M*1000 + O*100 + R*10 + E ==
          M*10000 + O*1000 + N*100 + E*10 + Y)
      cp.add(S > 0)
      cp.add(M > 0)
      cp.add(alldifferent(all), Strong)

    } exploration {
      cp.binaryFirstFail(all)
      println(all.mkString(""))
    }
    println()
    cp.printStats()
  }
}
The output is: 
 9 5 6 7 1 0 8 2

(time(ms),36)
(#bkts,5)
(time in fix point(ms),18)
(time in trail restore(ms),0)
(max trail size,587)
Some things to note:
  • OscaR is quite influenced by the way Comet (and OPL) separate the constraint part (cp.solveAll() subjectTo) and the search (branching) and output part (exploration). See below for a little more about search, and for a optimization example.
  • The arithmetic operators (*,+,==, and many more) are nicely overloaded which simplifies much of the modeling. I comment more about this below.
  • Additions of the constraint are done with cp.add(constraint).
A neater encoding of this problem is the following, using Scala's ability to extract variables from an Array (what is called "pattern matching"). This requires that the variables must be lower case. 
// ...
val all = Array.fill(8)(CPVarInt(cp, 0 to 9))
val Array(s,e,n,d,m,o,r,y) = all

cp.solveAll() subjectTo {

  // constraints
  cp.add(       s*1000 + e*100 + n*10 + d +
                m*1000 + o*100 + r*10 + e =
      m*10000 + o*1000 + n*100 + e*10 + y)
  cp.add(s > 0)
  cp.add(m > 0)
  cp.add(alldifferent(all), Strong)
} exploration {
// ...
}
Another example is Minesweeper.scala which is an example of how to use yield to collect variables. 
// ...
val mines = Array.fill(r)(Array.fill(c)(CPVarInt(cp, 0 to 1)))
cp.solveAll subjectTo {
  val tmp = List(-1,0,1)
  for(i <- 0 until r) {
     for(j <- 0 until c
       if game(i)(j) >= 0) {
          cp.add(sum(
             for{ a <- tmp; b <- tmp 
              if ((i+a >= 0) && (j+b  >= 0) &&
                 (i+a <  r)  && (j+b <  c)) 
              } yield mines(i+a)(j+b))
               == game(i)(j)
             ) // end sum

        // redundant constraint
        if (game(i)(j) > X) {
          cp.add(mines(i)(j) == 0)
        }
  }
}
// ...

Running OscaR

Running OscaR requires - of course - the OscaR distribution and Scala. Compiling it from source also requires the sbt tool. Obtaining a working version of OscaR can be done in two ways:
  • Get the distribution from the bitbucket.org repo. A JAR file is available here.
  • Or use Mercurial to do things manually, which basically consists of the following:
    (ht clone), hg pull, hg update, sbt assembly, sbt test

Running OscaR models

Note that models that are in Scala packages - such as the models in the distribution and my own models - must first be compiled with scala/fsc, i.e. they cannot be run as Scala scripts (at least using the current Scala version). Here is how I run a OscaR model under Linux:
$ fsc -J"-Xmx2000m" -deprecation -cp /path/to/oscar/oscar.jar -P:continuations:enable oscar/examples/cp/hakank/SendMoreMoney.scala

$ time scala -J"-Xmx2000m" -cp /path/to/oscar/oscar.jar -P:continuations:enable oscar.examples.cp.hakank.SendMoreMoney

Defining constraints (decompositions)

To define a constraint (decomposition) there are two variants depending on the return value. For "simple" constraints which returns a single value, e.g. CPVarInt, a Constraint, or CPVarBool then it can be used quite "seam less" in the model as cp.add(myConstraint(x)). An example from DeBruijn.scala is the constraint toNum which channels between an array of CPVarInt's and a CPVarInt (e.g. the Array (4,2,3,1) is channeled with the number 4231): 
def toNum(t: Array[CPVarInt], base: Int=10) = sum(
    Array.tabulate(t.length)(i=> t(i)*pow(base, t.length-i-1).toInt))

  // ...

  cp.solveAll subjectTo {

    // ...
    // Usage: 
    cp.add(x(i) == toNum(t, base))
    // ...

  } // ...


For other constraints which don't return a single value, then one have to use a slightly different approach and add the CPSolver as a parameter to the function. Here is an example of defining the inverse, used in Marathon.scala and PhotoProblem.scala for presenting the result in a more appropriate manner: 
def inverse(cp: CPSolver,
            x: Array[CPVarInt],
            y: Array[CPVarInt]) {
   val len = x.length
   for(i <- 0 until len;
       j <- 0 until len) {
         cp.add( (y(j) === i) == (x(i) === j) )
      }
   }

// ...

cp.maximize(z) subjectTo {

   // Usage: Channeling positions <=> places
   inverse(cp, positions, places)

} // ...
Here are some other defined decompositions (many not at all advanced, but never the less nice to have): More advanced advices regarding user-defined constraints are mentioned in the Wiki page Implement your own constraint.

Reification: Alldifferent except 0

Here is a simple decomposition of the global constraint alldifferent expcept 0 to show how reifications are done in OscaR. 
def alldifferent_except_0(cp: CPSolver, y: Array[CPVarInt]) = {
  for(i <- 0 until y.length; j <- 0 until i) {
    cp.add( ((y(i) !== 0) && (y(j) !== 0)) ==> (y(i) !== y(j)) )
  }
}
I.e.: if both y(i) and y(j) are != 0, then they should be different.

OscaR use the following operators when using boolean operators and reifications: 
  A >  B is reified with A >>= B
  A >= B is reified with A >== B                                                                                          
  A  < B is reified with A <<= B
  A <= B is reified with A <== B
  A == B is reified with A === B
(Note the trailing = for the reified variant.)

Also, b1 ==> b2 represents the implication: b1 implies b2 (i.e. if b1 is true, then b2 is true). And !A is the negation of A.

An example that use a lot of reifications is WhoKilledAgatha.scala. Here's an extract: 
//  ...
//  Charles hates noone that Agatha hates.
NRANGE.foreach(i=>
  cp.add((hates(agatha)(i)) ==>
         (!hates(charles)(i))))

//  The butler hates everyone not richer than Aunt Agatha.
NRANGE.foreach(i=>
  cp.add(!richer(i)(agatha) ==>
         hates(butler)(i)))

Always put the CPVarInt at the left in mixed expressions

This is a gotcha when using OscaR, and I mentioned a similar problem regarding JaCoPInScala in my blog post A first look at scalaJaCoP (Scala wrapper for JaCoP).

When an expression (constraint, reification) has both an Int and an CPVarInt variable, then OscaR/Scala is picky about where to put the terms. For example, the above equation SEND+MORE=MONEY must be written with the CPVarInt at the left, i.e. as S * 1000 + .. (rather than 1000 * S + ...), and this is a consequence how Scala's overloading works: Int's don't know about constraints etc, but CPVarInt's knows everything...

If the equation would have been stated as cp.add(1000*S... then the following error is thrown which can be confusing; and I mention it here so you might remember it when starting to use OscaR on you own. (Perhaps more seasoned Scala users understands this immediately and feel offended by this friendly advice.) 
SendMoreMoney.scala:57: error: overloaded method value * with alternatives:
  (x: Double)Double 
  (x: Float)Float 
  (x: Long)Long 
  (x: Int)Int 
  (x: Char)Int 
  (x: Short)Int 
  (x: Byte)Int
 cannot be applied to (oscar.cp.core.CPVarInt)
        cp.add(       1000*S + E*100 + N*10 + D +
                           ^

Optimization

OscaR supports - of course - optimization. Here's a simple diet problem (Diet2.scala), where the object is to minimize the total cost with the restrictions that the nutritions have minimum limits. Note the nice feature that a decision variable (here cost) can be defined directly using a constraint (val cost = weightedSum(price, x)).

The way to indicate optimization of a variable is cp.minimize(cost) (and cp.minimize(z)): 
val cp = CPSolver()
val n = 4
val price  = Array( 50, 20, 30, 80)
// minumum requirements for each nutrition
val limits = Array(500,  6, 10,  8)
// nutritions for each product
val calories  = Array(400, 200, 150, 500)
val chocolate = Array(3,2,0,0)
val sugar     = Array(2,2,4,4)
val fat       = Array(2,4,1,5)
val all = Array(calories, chocolate, sugar, fat)

// variables
val x = Array.fill(n)(CPVarInt(cp, 0 to 10))
val cost = weightedSum(price, x)

cp.minimize(cost) subjectTo {
  // handle the nutrition requirements
  for(i <- 0 until n) (
      cp.add(weightedSum(all(i), x) >= limits(i))
  )
} exploration { 
   cp.binaryFirstFail(x)
   println(x.mkString(" "))
}
The result shows that the minimum cost is 90 using 3 units of item 2. 
 0  3  0  1
objective tighten to 140
 0  3  1  0
objective tighten to 90

(time(ms),31)
(#bkts,5)
(time in fix point(ms),6)
(time in trail restore(ms),0)
(max trail size,446)

Element: Langford

Since I'm a little obsessed with how the element constraint is written in a CP system, it must be mentioned here as well. Example: element constraints in used in Langford.scala: 
for(i <- 1 to k) {
   cp.add(position(i+k-1) == (position(i-1) + i+1))
   cp.add(element(solution, position(i-1)) == i)
   cp.add(element(solution, position(k+i-1)) == i)
}
And this is similar to most CP systems which are hosted in a programming language.

In a very high level CP system, such as MiniZinc (langford2.mzn), it is stated a little more simple (and - in my book - more natural) as: 
forall(i in 1..to) (
  position[i+k-1] = position[i-1] + i+1 /\
  solution[position[i-1]]   == i        /\
  solution[position[k+i-1]] == i
)

Search (labeling/branching)

This principle of search (labeling, branching) in OscaR is inspired by Comet which means that you have building blocks that can be put together to do quite advanced things. The basic approach is defined in OscaR's Wiki search. In OscaR's main CP example directory, there are many example how to do advanced search.

Here I will just mention some of the basic search methods (which I tend to use first). Let us here assume that x is an Array of CPVarInt, then OscaR support these utility functions:
  • cp.binary(x)
  • cp.binaryFirstFail(x)
  • cp.binaryMaxDegree(x)
Quite recently some other variants was added (after my request; post hoc ergo propter hoc). From the answer:
I [Pierre Schaus] have adapted binary to let you add custom variable/value heuristics.

binary(vars: Array[CPVarInt], varHeuris: (CPVarInt => Int) = minVar, valHeuris: (CPVarInt => Int) = minVal)

So if you want a min dom heuristic, taking the max value you would do

cp.binary(x,_.size,_.max)

If you want a max degree one you can do

cp.binary(x,-_.constraintDegree,_.max)
The available attributes (of a CPVarInt) that can be used directly in this manner is:
  • size
  • min
  • max
  • constraintDegree
  • randomValue (for value selection)
  • an combinations such as (v => v.max-v.min), etc.
As a simple example of the latter, see the CalvinPuzzleTable.scala where the search is defined thus: 
// ...
cp.binary(x_flat,-_.constraintDegree,_.randomValue)
// ...

Scheduling

Very recently support for scheduling was added to OscaR by Renaud Hartert. See the Wiki entry Scheduling with CP for more information. I haven't used it very much so I just point to the examples.

Some end notes

It's fun modeling in OscaR since it's so high level, and extra fun since Scala is a very nice programming language.

As indicated in the introduction, OscaR has more features besides support for Constraint Programming, such as Constraint Based Local Search (former Asteroid), Linear Programming, and Discrete Event Simulation, as well as Scheduling in CP (mentioned above). Also there is support for visualization. These features has not been tested but I hope to test some of them in the future.

Most of my own OscaR models where converted from either my JaCoP/Scala models or my or-tools/C# models; and this probably shows in some of them.

My OscaR models

Here are some of my OscaR models.

All these models (or at least the majority) is also be available from the OsacaR repo: https://bitbucket.org/oscarlib/oscar/src/tip/src/main/scala/oscar/examples/cp/hakank. Thanks to Pierre Schaus for improving several of these models, either directly or indirectly by adding functions (or syntactic sugar).

Posted by hakank at 10:26 PM |