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¶
|[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] 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.
|[BIVS2017]||Fages, J.-G., & Prud’Homme, C. (2017). Making the first solution good! IEEE 29th International Conference on Tools with Artificial Intelligence. IEEE. (PDF)|