# 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.*

## Theoretical questions¶

## 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
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!