Pathology of Traveling-Salesman Subtour-Elimination Algorithms

DOI10.1287/opre.19.2.278zbMath0219.90032OpenAlexW2077053998MaRDI QIDQ5624982

J. C. Malone, Mandell Bellmore

Publication date: 1971

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/opre.19.2.278

Mathematics Subject Classification ID

Integer programming (90C10) Mixed integer programming (90C11) Linear programming (90C05)

Related Items

An exact algorithm for the capacitated shortest spanning arborescence ⋮ The symmetric travelling salesman problem. I: New fast lower bounds for the problem of optimal 2-matching ⋮ Results from a parallel branch-and-bound algorithm for the asymmetric traveling salesman problem ⋮ A note on the complexity of the asymmetric traveling salesman problem ⋮ A Fast Lower Bound for the Minimum Cost Perfect 2-Matching Linear Program ⋮ Some problems in discrete optimization ⋮ A study of complexity transitions on the asymmetric traveling salesman problem ⋮ Maximum travelling salesman problem. I ⋮ Motion tracking as a constrained optimization problem. ⋮ A new approach to solving the multiple traveling salesperson problem using genetic algorithms ⋮ Lower bounds for the symmetric travelling salesman problem from Lagrangean relaxations ⋮ On the stochastic complexity of the asymmetric traveling salesman problem ⋮ Solving symmetric vehicle routing problems asymmetrically ⋮ An appraisal of computational complexity for operations researchers ⋮ An additive bounding procedure for the asymmetric travelling salesman problem ⋮ The traveling salesman problem: An overview of exact and approximate algorithms ⋮ Integer programming approaches to the travelling salesman problem ⋮ Models, relaxations and exact approaches for the capacitated vehicle routing problem ⋮ The traveling salesman problem: A duality approach ⋮ On the solutions of stochastic traveling salesman problems ⋮ A continuous variable representation of the traveling salesman problem ⋮ An approach for solving a class of transportation scheduling problems ⋮ The seriation problem and the travelling salesman problem ⋮ Cluster based branching for the asymmetric traveling salesman problem ⋮ A restricted Lagrangean approach to the traveling salesman problem ⋮ Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems ⋮ The optimum assignments and a new heuristic approach for the traveling salesman problem ⋮ Methods for routing with time windows ⋮ An algorithm for the traveling salesman problem with pickup and delivery customers ⋮ Establishing motion correspondence using extended temporal scope ⋮ Average-case analysis of best-first search in two representative directed acyclic graphs ⋮ A genetic algorithm with a mixed region search for the asymmetric traveling salesman problem