Non Deterministic 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

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:

The outcome of this program is: 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:

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.

The outcome of this program is:

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:

The source code to obtain this search tree is just: and the output you\'ll get is:

First Fail Search

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:

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