1. Pierre Schaus
  2. OscaR

Wiki

Clone wiki

OscaR / search

OscaR CP supports non deterministic search as introduced in

Nondeterministic control for hybrid search by Pascal Van Hentenryck and Laurent Michel (Constraints Journal, 2006). This type of search was first implemented in the Comet system. It heavily uses continuations but there is no need to understand what a continuation is to understand the search effect and how to use this kind of search abstraction correctly.

Non deterministic search is all about exploring search tree and declaring how the search tree should look like but without explaining in which order the nodes should be explored.

Currently OscaR supports only DFS (Depth First Search) IDS (Iterative Discrepancy Search).

Search for all solutions

Let's start with an small example. Although we use a CPSolver to show the search functionality, we don't make use of CPVariable or constraints here. We only manipulate Scala objects.

We declare first a CPSolver, an array of 3 booleans and a counter variable nb

import oscar.cp.modeling._
import oscar.cp.core._

object MySearch extends App {
  val cp = CPSolver()
  val v = Array.tabulate(3)(i => false)
  var nb = 0
}

We would like to explore in a Depth First Search manner all the possibilities to assign true or false to those 3 booleans. Here is how to do it in OscaR:

import oscar.cp.modeling._
import oscar.cp.core._

object MySearch extends App {
  val cp = CPSolver()
  val v = Array.tabulate(3)(i => false)
  var nb = 0
  cp.exploration {
    cp.branch { v(0) = true } { v(0) = false }
    cp.branch { v(1) = true } { v(1) = false } 
    cp.branch { v(2) = true } { v(2) = false }
    println(v.mkString(","))
    nb += 1
  } run()
  println("number of solutions:"+nb)
}

The outcome of this program is:

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

which is exactly what we wanted... Let's explain how it works: The branch instruction requires two blocks of code:

  • the first one is executed on the left branch
  • the second one is executed on the right branch

When we go on the left, we assign the boolean to true, on the DFS backtrack the right branch will be executed and the effect of what we did on the left branch is overrided. The final search tree explored is the following:

tree1

Each time the search comes down along a branch without any fail, it reaches the end of the exploration block printing the solution and incrementing the number of solution. Only when the search has been exhausted it exits the exploration block and finally prints 8 (i.e. the number of time the search reached a leaf node).

Search for 3 first solutions

We provide one more parameter to stop the search when 3 solutions have been found.

import oscar.cp.modeling._
import oscar.cp.core._

object Test extends App {
  val cp = CPSolver()
  val v = Array.tabulate(3)(i => false)
  var nb = 0
  cp.exploration {
    cp.branch { v(0) = true } { v(0) = false }
    cp.branch { v(1) = true } { v(1) = false } 
    cp.branch { v(2) = true } { v(2) = false }
    println(v.mkString(","))
    nb += 1
  } run(3)
  
  println("exploration completed:"+cp.explorationCompleted)
  println("number of solutions:"+nb)
}

The outcome of this program is:

true,true,true
true,true,false
true,false,true
exploration completed:true
number of solutions:3

Note that we printed a boolean (cp.explorationCompleted) confirming that the search was stopped while it could have continued.

Cutt-off branches

Let's complexify a bit this example and imagine that you want to cut-off the right branches at the second level of the search tree:

tree2

The source code to obtain this search tree is just:

import oscar.cp.modeling._
import oscar.cp.core._

object Test extends App {

  val cp = CPSolver()
  val v = Array.tabulate(3)(i => false)
  var nb = 0
  cp.exploration {
    cp.branch { v(0) = true } 
              { v(0) = false }
    cp.branch { v(1) = true } 
              { cp.fail() } // we force the solver to fail such that the search backtracks here
    cp.branch { v(2) = true } 
              { v(2) = false }
    println(v.mkString(","))
    nb += 1
  } run()

  println("number of solutions:"+nb)
}

and the output you'll get is:

true,true,true
true,true,false
false,true,true
false,true,false
number of solutions:4

Now that the search in OscaR is almost clear, we'll implement a first fail search. The first fail search on a vector of decision variables x consists of selecting as the next variable to branch on the not instantiated one with the smallest domain size. On the left branch we can for instance attempt to instantiate the variable to it's smallest possible value and on the right branch we force it to take a different value. As soon as every variable is bound the search found a solution and will exit the while loop:

 while (!allBounds(vars)) {
   val unbound = vars.filter(!_.isBound)
   val minDomSize = unbound.map(_.getSize()).min 
   val x = unbound.filter(_.getSize == minDomSize).first
   val v = x.getMin()
   cp.branch (cp.post(x == v))(cp.post(x != v))
 }

This code is precisely the one that is executed by the method cp.binaryFirstFail used in most of the small CP examples.

Updated