×

zbMATH — the first resource for mathematics

Improved filtering for weighted circuit constraints. (English) Zbl 1309.90115
Summary: We study the weighted circuit constraint in the context of constraint programming. It appears as a substructure in many practical applications, particularly routing problems. We propose a domain filtering algorithm for the weighted circuit constraint that is based on the 1-tree relaxation of M. Held and R. M. Karp [Oper. Res. 18, 1138–1162 (1970; Zbl 0226.90047); Math. Program. 1, 6–25 (1971; Zbl 0232.90038)]. In addition, we study domain filtering based on an additive bounding procedure that combines the 1-tree relaxation with the assignment problem relaxation. Experimental results on Traveling Salesman Problem instances demonstrate that our filtering algorithms can dramatically reduce the problem size. In particular, the search tree size and solving time can be reduced by several orders of magnitude, compared to existing constraint programming approaches. Moreover, for medium-size problem instances, our method is competitive with the state-of-the-art special-purpose TSP solver Concorde.

MSC:
90C35 Programming involving graphs or networks
90B06 Transportation, logistics and supply chain management
90C27 Combinatorial optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Althaus, E., Bockmayr, A., Elf, M., Jünger, M., Kasper, T., & Mehlhorn, K. (2002). SCIL–Symbolic constraints in integer linear programming. In Proceedings of the 10th annual European symposium on algorithms (ESA). Lecture notes in computer science (Vol. 2461, pp. 75–87). Berlin: Springer. · Zbl 1019.90515
[2] Applegate, D. L., Bixby, R. E., Chvátal, V., & Cook, W. J. (2006). The traveling salesman problem: A computational study. Princeton: Princeton University Press. · Zbl 1130.90036
[3] Azevedo, F. (2007). Cardinal: A finite sets constraint solver. Constraints, 12, 93–129. · Zbl 1118.68653 · doi:10.1007/s10601-006-9012-6
[4] Beldiceanu, N., & Contejean, E. (1994). Introducing global constraints in CHIP. Mathematical and Computer Modelling, 20(12), 97–123. · Zbl 0816.68048 · doi:10.1016/0895-7177(94)90127-9
[5] Beldiceanu, N., Flener, P., & Lorca, X. (2005). The tree constraint. In Proceedings of the fourth international conference on integration of AI and OR techniques in constraint programming for combinatorial optimization problems (CPAIOR). Lecture notes in computer science (Vol. 3524, pp. 64–78). Berlin: Springer. · Zbl 1133.90403
[6] Bessiere, C. (2006). Constraint propagation. In F. Rossi, P. van Beek, & T. Walsh (Eds.), Handbook of constraint programming (Chapter 3). Amsterdam: Elsevier.
[7] Carpaneto, G., Dell’Amico, M., & Toth, P. (1995). Exact solution of large-scale, asymmetric traveling salesman problems. ACM Transactions on Mathematical Software, 21(4), 394–409. · Zbl 0887.65058 · doi:10.1145/212066.212081
[8] Carpaneto, G., Martello, S., & Toth, P. (1988). Algorithms and codes for the assignment problem. Annals of Operations Research, 13(1), 191–223. · doi:10.1007/BF02288323
[9] Caseau, Y., & Laburthe, F. (1997). Solving small TSPs with constraints. In Proceedings of the 14th international conference on logic programming (ICLP) (pp. 316–330). Cambridge: MIT Press.
[10] Chazelle, B. (2000). A minimum spanning tree algorithm with inverse-Ackermann type complexity. Journal of the ACM, 47(6), 1028–1047. · Zbl 1094.68606 · doi:10.1145/355541.355562
[11] Cormen, T. H., Leiserson, C. E., & Rivest, R. L. (1990). Introduction to algorithms. Cambridge: MIT Press. · Zbl 1158.68538
[12] Dixon, B., Rauch, M., & Tarjan, R. (1992). Verification and sensitivity analysis of minimum spanning trees in linear time. SIAM Journal on Computing, 21(6), 1184–1192. · Zbl 0760.68032 · doi:10.1137/0221070
[13] Dooms, G., & Katriel, I. (2006). The minimum spanning tree constraint. In Proceedings of CP. LNCS (Vol. 4204, pp. 152–166). Berlin: Springer. · Zbl 1160.68544
[14] Dooms, G., & Katriel, I. (2007). The ”not-too-heavy spanning tree” constraint. In Proceedings of the fourth international conference on integration of AI and OR techniques in constraint programming for combinatorial optimization problems (CPAIOR). Lecture notes in computer science (Vol. 4510, pp. 59–70). Berlin: Springer. · Zbl 1214.90121
[15] Fages, J.-G., & Lorca, X. (2011). Revisiting the tree constraint. In Proceedings of the 17th international conference on the principles and practice of constraint programming (CP). LNCS (Vol. 6876, pp. 271–285). Berlin: Springer.
[16] Fischetti, M., & Toth, P. (1989). An additive bounding procedure for combinatorial optimization problems. Operations Research, 37(2), 319–328. · Zbl 0676.90049 · doi:10.1287/opre.37.2.319
[17] Fischetti, M., & Toth, P. (1992). An additive bounding procedure for the asymmetric travelling salesman problem. Mathematical Programming, 53(1), 173–197. · Zbl 0773.90082 · doi:10.1007/BF01585701
[18] Focacci, F. (2001). Solving combinatorial optimization problems in constraint programming. Ph.D. thesis, University of Ferrara.
[19] Focacci, F., Lodi, A., & Milano, M. (1999). Cost-based domain filtering. In Proceedings of the fifth international conference on principles and practice of constraint programming (CP). Lecture notes in computer science (Vol. 1713, pp. 189–203).
[20] 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
[21] Focacci, F., Lodi, A., & Milano, M. (2002). A hybrid exact algorithm for the TSPTW. INFORMS Journal on Computing, 14(4), 403–417. · Zbl 1238.90054 · doi:10.1287/ijoc.14.4.403.2827
[22] Focacci, F., Lodi, A., Milano, M., & Vigo, D. (1999). Solving TSP through the integration of OR and CP techniques. Electronic Notes in Discrete Mathematics, 1, 13–25. · Zbl 0990.90553 · doi:10.1016/S1571-0653(04)00002-2
[23] Genç Kaya, L., & Hooker, J. N. (2006). A filter for the circuit constraint. In Proceedings of the 12th international conference on principles and practice of constraint programming (CP). Lecture notes in computer science (Vol. 4204, pp. 706–710). Berlin: Springer.
[24] Gervet, C. (1993). New structures of symbolic constraint objects: Sets and graphs. In Third workshop on constraint logic programming (WCLP’2003).
[25] Gervet, C. (2006). Constraints over structured domains. In F. Rossi, P. van Beek, & T. Walsh (Eds.), Handbook of constraint programming (Chapter 17). Amsterdam: Elsevier.
[26] Grötschel, M., & Holland, O. (1991). Solution of large-scale symmetric travelling salesman problems. Mathematical Programming, 51, 141–202. · Zbl 0733.90047 · doi:10.1007/BF01586932
[27] Gutin, G., & Punnen, A. P. (Eds.) (2007). The traveling salesman problem and its variations. Berlin: Springer. · Zbl 1113.90134
[28] Held, M., & Karp, R. M. (1970). The traveling-salesman problem and minimum spanning trees. Operations Research, 18, 1138–1162. · Zbl 0226.90047 · doi:10.1287/opre.18.6.1138
[29] 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
[30] 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
[31] Helsgaun, K. (2009). General k-opt submoves for the Lin-Kernighan TSP heuristic. Mathematical Programming Computation, 1(2), 119–163. · Zbl 1180.90269 · doi:10.1007/s12532-009-0004-6
[32] IBM Corp. (2010). IBM ILOG CP V1.6 User Manual.
[33] IBM Corp. (2010). IBM ILOG OPL V12.2 User Manual.
[34] Jonker, R., & Volgenant, T. (1983). Transforming asymmetric into symmetric traveling salesman problems. Operations Research Letters, 2(4), 161–163. · Zbl 0529.90090 · doi:10.1016/0167-6377(83)90048-2
[35] Karp, R. M. (1972). Reducibility among combinatorial problems. In R. E. Miller, & J. W. Thatcher (Eds.), Complexity of computer animations (pp. 85–103). London: Plenum Press.
[36] Kilby, P., & Shaw, P. (2006). Vehicle routing. In F. Rossi, P. van Beek, & T. Walsh (Eds.), Handbook of constraint programming (Chapter 23). Amsterdam: Elsevier.
[37] Kuhn, H. W. (1955). The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly, 2, 83–97. · Zbl 0143.41905 · doi:10.1002/nav.3800020109
[38] Lauriere, J.-L. (1978). A language and a program for stating and solving combinatorial problems. Artificial Intelligence, 10(1), 29–127. · Zbl 0374.68060 · doi:10.1016/0004-3702(78)90029-2
[39] Lodi, A., Milano, M., & Rousseau, L.-M. (2006). Discrepancy-based additive bounding procedures. INFORMS Journal on Computing, 18(4), 480–493. · Zbl 1241.90083 · doi:10.1287/ijoc.1050.0168
[40] Milano, M., & van Hoeve, W. J. (2002). Reduced cost-based ranking for generating promising subproblems. In Proceedings of the eighth international conference on principles and practice of constraint programming (CP). Lecture notes in computer science (Vol. 2470, pp. 1–16). Berlin: Springer.
[41] Pesant, G., Gendreau, M., Potvin, J. Y., & Rousseau, J. M. (1998). An exact constraint logic programming algorithm for the traveling salesman problem with time windows. Transportation Science, 32(1), 12–29. · Zbl 0987.90086 · doi:10.1287/trsc.32.1.12
[42] Prim, R. C. (1957). Shortest connection networks and some generalizations. Bell System Techical Journal, 36, 1389–1401. · doi:10.1002/j.1538-7305.1957.tb01515.x
[43] Puget, J. F. (1992). PECOS: A high level constraint programming language. In Proceedings of the Singapore international conference on intelligent systems (SPICIS).
[44] Régin, J.-C. (1994). A filtering algorithm for constraints of difference in CSPs. In Proceedings of the twelfth national conference on artificial intelligence (AAAI) (Vol. 1, pp. 362–367). Menlo Park: AAAI Press.
[45] Régin, J.-C. (2008). Simpler and incremental consistency checking and arc consistency filtering algorithms for the weighted spanning tree constraint. In Proceedings of the fifth international conference on integration of AI and OR techniques in constraint programming for combinatorial optimization problems (CPAIOR). Lecture notes in computer science (Vol. 5015, pp. 233–247). Berlin: Springer. · Zbl 1142.68523
[46] Régin, J.-C. (2011). Global constraints: A survey. In P. Van Hentenryck, & M. Milano (Eds.), Hybrid optimization (pp. 63–134). Berlin: Springer. · Zbl 1206.90181
[47] Régin, J.-C., Rousseau, L.-M., Rueher, M., & van Hoeve, W.-J. (2010). The weighted spanning tree constraint revisited. In Proceedings of the seventh international conference on integration of AI and OR techniques in constraint programming for combinatorial optimization problems (CPAIOR). LNCS (Vol. 6140, pp. 176–180. Berlin: Springer. · Zbl 1285.68162
[48] Sellmann, M. (2004). Theoretical foundations of CP-based Lagrangian relaxation. In Proceedings of the 10th international conference on the principles and practice of constraint programming (CP). LNCS (Vol. 3258, pp. 634–647). Berlin: Springer. · Zbl 1152.68584
[49] Tarjan, R. (1982). Sensitivity analysis of minimum spanning trees and shortest path trees. Information Processing Letters, 14(1), 30–33. · doi:10.1016/0020-0190(82)90137-5
[50] Tarjan, R. E. (1979). Applications of path compression on balanced trees. Journal of the ACM, 26(4), 690–715. · Zbl 0413.68063 · doi:10.1145/322154.322161
[51] van Hoeve, W.-J., & Katriel, I. (2006). Global constraints. In F. Rossi, P. van Beek, & T. Walsh (Eds.), Handbook of constraint programming (Chapter 6). Amsterdam: Elsevier.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.