When 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..