Information

Deadline No deadline
Submission limit No limitation

Sign in

[Part9 Exercise] Black box search

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:

  1. Last Conflict, branching on the most recent variable having caused a failure.
  2. Conflict Ordering Search, an extension of last conflict where all failures are time-stamped.
  3. 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.)