×

zbMATH — the first resource for mathematics

A branch-and-cut algorithm for the undirected prize collecting traveling salesman problem. (English) Zbl 1203.90129
Summary: Given an undirected graph with edge costs and vertex prizes, the aim of the Prize Collecting Traveling Salesman Problem (PCTSP) is to find a simple cycle minimizing the total edge cost while collecting at least a minimum amount of prizes. In this article, we present a branch-and-cut algorithm to solve the PCTSP. We have adapted and implemented some classical polyhedral results for the PCTSP and derived inequalities from cuts designed for the Orienteering Problem. Computational results on instances with more than 500 vertices are reported.

MSC:
90C27 Combinatorial optimization
05C85 Graph algorithms (graph-theoretic aspects)
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Software:
SCIP; Concorde; TSPLIB
PDF BibTeX Cite
Full Text: DOI
References:
[1] T. Achterberg, SCIP-A framework to integrate constraint and mixed integer programming, Technical Report ZR-06-19, Konrad-Zuse-Zentrum fur Informationstchnik, Berlin, 2004.
[2] Achterberg, Branching rules revisited, Oper Res Lett 33 pp 42– (2005) · Zbl 1076.90037
[3] Ahuja, Network flows: Theory, algorithms, and applications (1993) · Zbl 1201.90001
[4] Applegate, The traveling salesman problem: A computational study (2006) · Zbl 1130.90036
[5] Awerbuch, New approximation guarantees for minimum-weight k-trees and prize-collecting salesman, SIAM J Comput 28 pp 254– (1998) · Zbl 0916.90256
[6] Balas, Facets of the knapsack polytope, Math Program 8 pp 146– (1975) · Zbl 0316.90046
[7] Balas, The prize collecting traveling salesman problem, Networks 19 pp 621– (1989) · Zbl 0676.90089
[8] Balas, The prize collecting traveling salesman problem. II. Polyhedral results, Networks 25 pp 199– (1995) · Zbl 0843.90120
[9] Balas, The traveling salesman problem and its variations pp 663– (2002)
[10] Balas, Facets of the knapsack polytope from minimal covers, SIAM J Appl Math 34 pp 119– (1978) · Zbl 0385.90083
[11] Chvátal, Edmonds polytopes and weakly hamiltonian graphs, Math Program 5 pp 29– (1973)
[12] Dell’Amico, A lagrangian heuristic for the prize collecting travelling salesman problem, Ann Oper Res 81 pp 289– (1998)
[13] Dell’Amico, On prize-collecting tours and the asymmetric travelling salesman problem, Int Trans Oper Res 2 pp 297– (1995)
[14] Feillet, Traveling salesman problems with profits, Transport Sci 39 pp 188– (2005)
[15] Fischetti, Solving the orienteering problem through branch-and-cut, INFORMS J Comput 10 pp 133– (1998) · Zbl 1034.90523
[16] Fischetti, The traveling salesman problem and its variations pp 609– (2002)
[17] Fischetti, Vehicle routing: Methods and studies pp 319– (1988)
[18] Gendreau, New insertion and postoptimization procedures for the traveling salesman problem, Oper Res 40 pp 1086– (1992) · Zbl 0767.90087
[19] Gendreau, A branch-and-cut algorithm for the undirected selective traveling salesman problem, Networks 32 pp 263– (1998) · Zbl 1002.90044
[20] Grötschel, On the symmetric travelling salesman problem I: Inequalities, Math Program 16 pp 265– (1979)
[21] Grötschel, On the symmetric travelling salesman problem II: lifting theorems and facets, Math Program 16 pp 281– (1979) · Zbl 0413.90049
[22] Jünger 7 pp 225– (1995)
[23] Johnson, Progress in linear programming based branch-and-bound algorithms: An exposition, INFORMS J Comput 12 pp 1– (2000)
[24] Kataoka, An algorithm for single constraint maximum collection problem, J Oper Res Soc Jpn 31 pp 515– (1988) · Zbl 0665.90092
[25] Laporte, The selective travelling salesman problem, Discrete Appl Math 26 pp 193– (1990) · Zbl 0695.90098
[26] Leifer, Strong linear programming relaxations for the orienteering problem, Eur J Oper Res 73 pp 517– (1994) · Zbl 0807.90087
[27] Martello, An upper bound for the zero-one knapsack problem and a branch and bound algorithm, Eur J Oper Res 1 pp 169– (1977) · Zbl 0374.90050
[28] Martello, Knapsack problems, algorithms and computer implementations (1990) · Zbl 0708.68002
[29] Padberg, Facet identification for the symmetric traveling salesman polytope, Math Program 47 pp 219– (1990) · Zbl 0706.90050
[30] Reinelt, TSPLIB: A traveling salesman problem library, ORSA J Comput 3 pp 376– (1991) · Zbl 0775.90293
[31] Tsiligirides, Heuristic methods applied to orienteering, J Oper Res Soc 35 pp 797– (1984)
[32] Weismantel, On the 0/1 knapsack polytope, Math Program 77 pp 49– (1997) · Zbl 0891.90130
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.