INGIniousWhen you modified the search heuristics in previous modules, you only did it when knowing about the structure of the problem at hands. For instance, the search done on the TSP was taking into account the distance matrix in the problem.
You will now implement branching strategies that do not care about the structure of the problem. The black-box strategies that you will implement are:
- Last Conflict, branching on the most recent variable having caused a failure.
- Conflict Ordering Search, an extension of last conflict where all failures are time-stamped.
- Limited Discrepency, limiting the number of right decisions taken within the search tree.
1. Last Conflict
Implement the Last Conflict [LC2009] heuristic presented in the course. Your implementation needs to be done within the lastConflict method from BranchingScheme.java.
To detect if a failure happened, you can surround a cp.post(...) call by a try-catch(-finally) block:
try {
cp.post(...)
} catch (InconsistencyException inconsistency) {
// do something
}
Test your implementations in LastConflictSearchTest.java.
| [LC2009] | Lecoutre, C., Saïs, L., Tabary, S., & Vidal, V. (2009). Reasoning from last conflict(s) in constraint programming. Artificial Intelligence, 173(18), 1592-1614. (PDF.) |
2. Conflict Ordering Search
Implement the Conflict Ordering Search [COS2015] heuristic. Your implementation needs to be done within the conflictOrderingSearch method from BranchingScheme.java.
Test your implementations in ConflictOrderingSearchTest.java..
| [COS2015] | Gay, S., Hartert, R., Lecoutre, C., & Schaus, P. (2015). Conflict ordering search for scheduling problems. International Conference on Principles and Practice of Constraint Programming, pp. 140-148. Springer. (PDF) |
3. Limited Discrepancy Search
Implement LimitedDiscrepancyBranching, a branching that can wrap any branching to limit the discrepancy of the branching.
Procedure[] branches = bs.get();
Procedure[] filteredBranches = new Procedure[...];
for (int i = 0; i < filteredBranches.length; i++) {
... // do something
filteredBranches[i] = () -> {
... // do something to update the discrepancy
branches[bi].call(); // call the initial branching
};
}
Test your implementation in LimitedDiscrepancyBranchingTest.java..