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.
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.
Conflict-based Search Strategy¶
|[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)|
|[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)|
Bound-Impact Value Selector¶
Implement the bound-impact value selector [BIVS2017] to discover good solutions quickly. Test it on the TSP and compare it with random value selection.
Implement in 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 implementation.
Hint: you can test the effect on the objective value by first saving the state, assigning a value to a variable and retrieving the new domain of the objective value, before finally restoring the previous state.
|[BIVS2017]||Fages, J.-G., & Prud’Homme, C. (2017). Making the first solution good! IEEE 29th International Conference on Tools with Artificial Intelligence. IEEE. (PDF)|