A restricted Lagrangean approach to the traveling salesman problem

DOI10.1007/BF01584228zbMATH Open0461.90068OpenAlexW2008200956MaRDI QIDQ3911684FDOQ3911684

E. 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

assignment problembranch and boundcomputational experienceHamiltonian circuitsasymmetric traveling salesman2-matching problemarc premiumspolynomially bounded proceduresrestricted Lagrangean relaxation

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (50)

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

This page was built for publication: A restricted Lagrangean approach to the traveling salesman problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3911684)