Abstract
The determination of true optimum solutions of combinatorial optimization problems is seldomly required in practical applications. The majority of users of optimization software would be satisfied with solutions of guaranteed quality in the sense that it can be proven that the given solution is at most a few percent off an optimum solution. This paper presents a general framework for practical problem solving with emphasis on this aspect. A detailed discussion along with a report about extensive computational experiments is given for the traveling salesman problem.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bentley JL (1992) Experiments on geometric traveling salesman heuristics. ORSA Journal on Computing 4:387–411
Christofides N (1976) Worst case analysis of a new heuristic for the traveling salesman problem. Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh
Clarke G, Wright JW (1964) Scheduling of vehicles from a central depot to a number of delivery points. Operations Research 12:568–581
Crowder H, Padberg MW (1980) Solving large-scale symmetric traveling salesman problems to optimality. Management Science 26:495–509
Derigs U, Metz A (1991) Solving (large-scale) matching problems combinatorically. Mathematical Programming 50:113–121
Edmonds J (1965) Maximum matching and a polyhedron with 0,1-vertices. Journal of Research of the National Bureau of Standards B 69:125–130
Grötschel M, Holland O (1991) Solution of large-scale symmetric traveling salesman problems. Mathematical Programming 51:141–202
Johnson DS (1990) Local optimization and the traveling salesman problem. Proceedings of the 17th colloquium on automata, languages and programming, Springer Verlag 446–461
Jünger M, Mutzel P (1993) Solving the maximum weight planar subgraph problem by branch & cut. Proceedings of the third IPCO conference 479–492
Jünger M, Reinelt G, Rinaldi G (1994) The traveling salesman problem. to appear In: Ball M, Magnanti T, Monma CL, Nemhauser G (eds) Handbook on Operations Research and Management Sciences: Networks, North Holland
Knuth DE (1973) The art of computer programming, volume 3, sorting and searching, Addison-Wesley, Reading, Massachusetts
Lin S, Kernighan BW (1973) An effective heuristic algorithm for the traveling salesman problem. Operations Research 21:498–516
Padberg MW, Rao MR (1982) Odd minimum cut sets and b-matchings. Mathematics of Operations Research 7:67–80
Padberg MW, Rinaldi G (1990) Facet identification for the symmetric traveling salesman polytope. Mathematical Programming 47:219–257
Padberg MW, Rinaldi G (1991) A branch and cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Review 33:60–100
Reinelt G (1991) TSPLIB—A traveling salesman problem library. ORSA Journal on Computing 3:376–384
Reinelt G (1992) Fast heuristics for large geometric traveling salesman problems. ORSA Journal on Computing 4:206–217
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Jünger, M., Thienel, S. & Reinelt, G. Provably good solutions for the traveling salesman problem. ZOR - Methods and Models of Operations Research 40, 183–217 (1994). https://doi.org/10.1007/BF01432809
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01432809