A restricted Lagrangean approach to the traveling salesman problem

DOI10.1007/BF01584228zbMath0461.90068OpenAlexW2008200956MaRDI QIDQ3911684

Egon Balas, Nicos Christofides

Publication date: 1981

Published in: Mathematical Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01584228

zbMATH Keywords

branch and boundassignment problemHamiltonian circuitscomputational experienceasymmetric traveling salesman2-matching problemarc premiumspolynomially bounded proceduresrestricted Lagrangean relaxation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Numerical mathematical programming methods (65K05) Eulerian and Hamiltonian graphs (05C45)

Related Items

Lagrangean relaxation. (With comments and rejoinder)., Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs, An inexact algorithm for the sequential ordering problem, Dynamic bundle methods, The symmetric travelling salesman problem. I: New fast lower bounds for the problem of optimal 2-matching, A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags, Discrete optimization by optimal control methods. III. The dynamic traveling salesman problem, Maximum travelling salesman problem. I, Matheuristics: survey and synthesis, Better assignment lower bounds for the Euclidean traveling salesman problem, Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times, Lower bounds for the symmetric travelling salesman problem from Lagrangean relaxations, On the stochastic complexity of the asymmetric traveling salesman problem, The symmetric travelling salesman problem. II: New low bounds, A production planning problem in FMS, Nonlinear resolving functions for the travelling salesman problem, The three-dimensional assignment and partition problems. New lower bounds, Discrete optimization by optimal control methods. II: The static traveling salesman problem, Reduced first-level representations via the reformulation-linearization technique: Results, counterexamples, and computations, An additive bounding procedure for the asymmetric travelling salesman problem, Travelling salesman problem tools for microcomputers, A relax-and-cut algorithm for the set partitioning problem, Approximate algorithms for the traveling salesman problem. II, Exact algorithms for the vertex separator problem in graphs, The traveling salesman problem: An overview of exact and approximate algorithms, The multiple-robot assembly plan problem, Analysis of the Held-Karp lower bound for the asymmetric TSP, A Lagrangian relaxation approach to the edge-weighted clique problem, Shuffling heuristics for the storage location assignment in an AS/RS, Decomposition and dynamic cut generation in integer linear programming, Facets of the three-index assignment polytope, A diagonal completion and 2-optimal procedure for the travelling salesman problem, A branch and bound algorithm for the capacitated vehicle routing problem, New lower bounds for the triplanar assignment problem. Use of the classical model, Cluster based branching for the asymmetric traveling salesman problem, On dual solutions of the linear assignment problem, Heuristic methods and applications: A categorized survey, New lower bounds for the symmetric travelling salesman problem, New edges not used in shortest tours of TSP, Minimum directed 1-subtree relaxation for score orienteering problem, Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems, Transforming asymmetric into symmetric traveling salesman problems, Recent trends in combinatorial optimization, Heuristics for the flow line problem with setup costs, Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition, Some facets of the simple plant location polytope, A set covering reformulation of the pure fixed charge transportation problem, Analyzing tradeoffs between zonal constraints and accessibility in facility location, An algorithm for the traveling salesman problem with pickup and delivery customers, Non delayed relax-and-cut algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial Optimization: What is the State of the Art
• Cutting planes from conditional bounds: A new approach to set covering
• A NEW PRACTICAL SOLUTION FOR LARGE-SCALE TRAVELING SALESMAN PROBLEM
• Travelling Salesman and Assignment Problems: A Survey
• Improvements of the Held—Karp algorithm for the symmetric traveling-salesman problem
• The Traveling Salesman Problem: A Survey
• The Shortest Hamiltonian Chain of a Graph
• Pathology of Traveling-Salesman Subtour-Elimination Algorithms
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II
• Technical Note—Bounds for the Travelling-Salesman Problem