This page is no longer maintained — Please continue to the home page at www.scala-lang.org

Nondeterministic control for hybrid search implemented in Scala into Scampi Solver

No replies
pschaus
Joined: 2012-01-15,
User offline. Last seen 33 weeks 5 days ago.

Nondeterministic control for hybrid search where introduced in a paper
by Pascal Van Hentenryck and Laurent Michel (Constraints Journal,
2006).
This kind of search is the most elegant one never invented to solve
constraint programming problems.
We were able to implement it in Scampi (Constraint Programming Solver
in Scala) thanks to the continuations available in Scala.
Here is a small example:

val cp = CPSolver()
val v = Array.tabulate(3)(i => new ReversibleBool(cp))
cp.exploration {
cp.branch { v(0).setValue(true) }
{ v(0).setValue(false)}
cp.branch { v(1).setValue(true) }
{ v(1).setValue(false)}
cp.branch { v(2).setValue(true) }
{ v(2).setValue(false)}
println(v.mkString(","))
nb += 1
}
println(nb)

Will make a DFS exploration and output

true,true,true
true,true,false
true,false,true
true,false,false
false,true,true
false,true,false
false,false,true
false,false,false
nb:8

If you are interested to see more about it, have a look here:
https://bitbucket.org/pschaus/scampi/wiki/search

Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland