×

The salesman and the tree: the importance of search in CP. (English) Zbl 1334.90143

Summary: The traveling salesman problem (TSP) is a challenging optimization problem for CP and OR that has many industrial applications. Its generalization to the degree constrained minimum spanning tree problem (DCMSTP) is being intensively studied by the OR community. In particular, classical solution techniques for the TSP are being progressively generalized to the DCMSTP. Recent work on cost-based relaxations has improved CP models for the TSP. However, CP search strategies have not yet been widely investigated for these problems. The contributions of this paper are twofold. We first introduce a natural generalization of the weighted cycle constraint (WCC) to the DCMSTP. We then provide an extensive empirical evaluation of various search strategies. In particular, we show that significant improvement can be achieved via our graph interpretation of the state-of-the-art Last Conflict heuristic.

MSC:

90C27 Combinatorial optimization
90C35 Programming involving graphs or networks

Software:

Concorde; TSPTW; LKH
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] Andrade, R., Lucena, A., Maculan, N. (2006). Using Lagrangian dual information to generate degree constrained spanning trees. Discrete Applied Mathematics, 154(5), 703-717. · Zbl 1120.90067 · doi:10.1016/j.dam.2005.06.011
[2] Benchimol, P., van Hoeve, W.J., Régin, J.-C., Rousseau, L.-M., Rueher, M. (2012). Improved filtering for weighted circuit constraints. Constraints, 17(3), 205-233. · Zbl 1309.90115 · doi:10.1007/s10601-012-9119-x
[3] Concorde TSP solver. http://www.tsp.gatech.edu/concorde.html. · Zbl 1185.68645
[4] da Cunha, A.S., & Lucena, A. (2007). Lower and upper bounds for the degree-constrained minimum spanning tree problem. Networks, 50(1), 55-66. · Zbl 1119.90069 · doi:10.1002/net.20166
[5] da Cunha, A.S., & Lucena, A. (2008). A hybrid relax-and-cut/branch and cut algorithm for the degree-constrained minimum spanning tree problem. Technical report, Universidade Federal do Rio de Janeiro. · Zbl 0969.90073
[6] Dooms, G., Deville, Y., Pierre, D. (2005). CP(Graph): Introducing a graph computation domain in constraint programming. In Principles and Practice of Constraint Programming, CP, vol. 3709, pp. 211-225. · Zbl 1153.68457
[7] Focacci, F., Lodi, A., Milano, M. (1999). Cost-based domain filtering. In CP, volume 1713 of Lecture Notes in Computer Science, (pp. 189-203): Springer. · Zbl 1310.05144
[8] Focacci, F., Lodi, A., Milano, M. (2002). Embedding relaxations in global constraints for solving TSP and TSPTW. Annals of Mathematics and Artificial Intelligence, 34(4), 291-311. · Zbl 1002.68159 · doi:10.1023/A:1014492408220
[9] Focacci, F., Lodi, A., Milano, M. (2002). Optimization-oriented global constraints. Constraints, 7(3-4), 351-365. · Zbl 1028.68024 · doi:10.1023/A:1020589922418
[10] Francis, K.G., & Stuckey, P.J. (2013). Explaining circuit propagation. Constraints, 19, 1-29. · Zbl 1310.05144 · doi:10.1007/s10601-013-9148-0
[11] Maria, J., de la Banda, G., Stuckey, P.J., Wazny, J. (2003). Finding all minimal unsatisfiable subsets. In PPDP, pp. 32-43. · Zbl 1119.90069
[12] Haralick, R.M., & Elliott, G.L. (1979). Increasing tree search efficiency for constraint satisfaction problems. In: Proceedings of the 6th International Joint Conference on Artificial Intelligence - Vol. 1, IJCAI’79, (pp. 356-364): Morgan Kaufmann Publishers Inc. · Zbl 1120.90067
[13] Held, M., & Karp, R.M. (1971). The traveling-salesman problem and minimum spanning trees: Part II. Mathematical Programming, 1, 6-25. · Zbl 0232.90038 · doi:10.1007/BF01584070
[14] Helsgaun, K. (2000). An effective implementation of the Lin-Kernighan traveling salesman heuristic. European Journal of Operational Research, 126(1), 106-130. · Zbl 0969.90073 · doi:10.1016/S0377-2217(99)00284-2
[15] Lecoutre, C., Sais, L., Tabary, S., Vidal, V. (2009). Reasoning from last conflict(s) in constraint programming. Artificial Intelligence, 173(18), 1592-1614. · Zbl 1185.68645 · doi:10.1016/j.artint.2009.09.002
[16] Le Pape, C., Perron, L., Régin, J.-C., Shaw, P. (2002). Robust and parallel solving of a network design problem. In Principles and Practice of Constraint Programming, CP, vol. 2470, pp. 633-648. · Zbl 1185.68645
[17] Régin, J.-C. (2004). Tutorial: Modeling problems in constraint programming. In Principles and Practice of Constraint Programming, CP.
[18] Régin, J.-C. (2008). Simpler and incremental consistency checking and arc consistency filtering algorithms for the weighted spanning tree constraint. In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR, vol. 5015, pp. 233-247. · Zbl 1142.68523
[19] Régin, J.-C., Rousseau, L.-M., Rueher, M., van Hoeve, W.J. (2010). The weighted spanning tree constraint revisited. In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR, vol. 6140, pp. 287-291. · Zbl 1285.68162
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.