Part 8: Search¶
We ask you not to publish your solutions on a public repository. The instructors interested to get the source-code of the solutions can contact us.
Discrepancy Limited Search (optional)¶
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.|
|[COS2015]||Gay, S., Hartert, R., Lecoutre, C., & Schaus, P. (2015). Conflict ordering search for scheduling problems. In International conference on principles and practice of constraint programming (pp. 140-148). Springer.|
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 the bound-impact value selector in TSPBoundImpact.java Verify experimentally that the first solution found is smaller than with the default min value heuristic. You can also use it in combination with your conflict ordered search implementation.
|[BIVS2009]||Fages, J. G., & Prud’Homme, C. Making the first solution good! In 2017 IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI). IEEE.|