Part 8: Search¶
We ask you not to publish your solutions on a public repository. The instructors interested to get the source code of our solutions can contact us.
Conflict-based Search Strategies¶
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)
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)
Bound-Impact Value Selector¶
Implement the bound-impact value selector [BIVS2017] in order to discover good solutions quickly.
Implement within TSPBoundImpact.java. Verify experimentally that the first solution found is smaller than with the default minimum-value heuristic. You can also use it in combination with your conflict ordering search.
Hint: You can test the effect on the objective value by first saving the state, fixing the variable to a value, and retrieving the new domain of the objective variable, before finally restoring the previous state.
Limited Discrepancy Search (optional)¶
Implement LimitedDiscrepancyBranching, a branching that can wrap any branching to limit the discrepancy of the branching.
Test your implementation in LimitedDiscrepancyBranchingTest.java..