Part 3: Memory Management (Trail + Copy) and Search

We ask you not to publish your solutions on a public repository. The instructors interested to get the source-code of the solutions can contact us.

Slides

Memory Management: Copy and Trail, Search

Theoretical questions

• State managers

DFS Explicit Stack

The search algorithm of Mini-CP is depth-first-search. It is implemented using a recursive method in the class DFSSearch.java. To avoid any stack-overflow exception due to a too deep recursion in Java we ask you to reimplement the depth-first-search with an explicit stack of instead of relying on the recursion call stack.

Consider the following search tree where alternatives to execute are represented as letters.

A DFS exploration should executes the branches in the following order A->D->E->B->C->F->G. On backtrack, the state should be restored and therefore these successive executions of the branches should be interleaved with ‘push’ and ‘pop’ operations on the trail. For instance a valid sequence for restoring the states on backtrack is the following: push->A->push->D->pop->push->E->pop->pop->push->B->pop->push->C->push->F->pop->push->G->pop->pop. The push operations are executed in pre-order fashion while the pop operations are executed in a post-order fashion. This is highlighted in the recursive dfs code given next.

     private void dfs(SearchStatistics statistics, Predicate<SearchStatistics> limit) {
         if (limit.stopSearch(statistics)) throw new StopSearchException();
         Procedure[] branches = branching.get();
         if (alternatives.length == 0) {
             statistics.nSolutions++;
             notifySolutionFound();
         }
         else {
             for (Procedure b : branches) {
                 state.saveState(); // pre-order
                 try {
                     statistics.nNodes++;
                     alt.call(); // call the alternative
                     dfs(statistics,limit);
                 } catch (InconsistencyException e) {
                     notifyFailure();
                     statistics.nFailures++;
                 }
                 state.restoreState(); // post-order
             }
         }
     }

A skeleton of solution is given next but you don’t have to follow exactly this solution since there are many ways

to implement it.

     private void dfs(SearchStatistics statistics, Predicate<SearchStatistics> limit) {
         Stack<Procedure> alternatives = new Stack<Procedure>();
         expandNode(alternatives,statistics); // root expension
         while (!alternatives.isEmpty()) {
             if (limit.stopSearch(statistics)) throw new StopSearchException();
             try {
                 alternatives.pop().call();
             } catch (InconsistencyException e) {
                 notifyFailure();
                 statistics.nFailures++;
             }
         }
     }
     private void expandNode(Stack<Procedure> alternatives, SearchStatistics statistics) {
        // TODO
     }

The idea of this solution is wrap the push/pop/alternative execution inside Alternative closure objects as illustrated on the next figure showing the stack after the root node expansion at line 3.

Check that your implementation passes the tests DFSearchTest.java

Remark (optional): It is actually possible to reduce the number of operations on the trail by skipping the push on a last branch at a given node. The sequence of operations becomes push->push->A->push->D->pop->E->pop->push->B->pop->C->push->F->pop->G->pop.

Implement a Custom Search

Modify the Quadratic Assignment Model QAP.java to implement a custom search strategy. A skeleton for a custom search is the following one:

DFSearch dfs = makeDfs(cp, () -> {
    IntVar sel = selectMin(x,
            vari -> vari.size() > 1, // filter
            vari -> vari.size()      // variable selector
    );
    if (sel == null)
        return EMPTY;
    int v = sel.min(); // value selector (TODO)
    return branch(
        () -> equal(sel,v),
        () -> notEqual(sel,v)
    );
});

• As a variable heuristic, select the unbound variable x[i] (a facility i not yet assigned to a location) that has a maximum weight w[i][j] with another facility j (x[j] may be bound or not).
• As a value heuristic, on the left branch, place this facility on the location which is the closest possible to another location possible for the facility j you selected earlier. On the right branch remove the value .
• Hint: selectMin is a generic method parameterized by ‘T’ and ‘N’ (the type on which the minimum is computed). To implement this heuristic, adding pairs (i,j) as a type for T is probably the easiest way to go.

public static <T, N extends Comparable<N>> T selectMin(T[] x, Predicate<T> p, Function<T, N> f)

Sequencer Combinator

Sometimes we wish to branch on a given order on two families of variables, say x[] and then y[] as show on the next picture. A variable in y should not be branched on before all the variables in x have been decided. Furthermore, we may want to apply a specific heuristic on x which is different from the heuristic we want to apply on y variables.

scale:

50 :width: 200

alt:combinator

This can be achieved as follows

IntVar [] x;
IntVar [] y;
makeDfs(and(firstFail(x),firstFail(y)))

The and factory method creates a Sequencer.java. You must complete its implementation.

Check on INGInious

When you are done implementing your constraints and branching functions, do not forget to upload your code on INGInious to actually get your grade!