Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
From MaRDI portal
Publication:3888840
DOI10.1287/MNSC.26.5.495zbMath0444.90068OpenAlexW2114552889MaRDI QIDQ3888840
Harlan P. Crowder, Manfred W. Padberg
Publication date: 1980
Published in: Management Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/mnsc.26.5.495
combinatorial optimizationbranch-and-boundvalid inequalitiescomputational studylinear integer programminglarge-scale test problemscutting-plane approachcomb constraintssubtour- eliminationsymmetric travelling salesman problems
Related Items (63)
Generating subtour elimination constraints for the TSP from pure integer solutions ⋮ Two-edge connected spanning subgraphs and polyhedra ⋮ Solving matching problems with linear programming ⋮ The hierarchical network design problem ⋮ A branch-and-cut algorithm for vehicle routing problems ⋮ Representability in mixed integer programming. I: Characterization results ⋮ Optimization of a 532-city symmetric traveling salesman problem by branch and cut ⋮ A polyhedral approach to the rural postman problem ⋮ Tabu search performance on the symmetric travelling salesman problem ⋮ Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday) ⋮ Unnamed Item ⋮ A new class of cutting planes for the symmetric travelling salesman problem ⋮ A polynomial-time solution to Papadimitriou and Steiglitz's ``traps ⋮ Cutting plane versus compact formulations for uncertain (integer) linear programs ⋮ A continuous linear optimization model for the exact solution of travelling-salesman-problems in connexion with expansion planning of ring networks ⋮ Strong formulations for mixed integer programming: A survey ⋮ Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies ⋮ Facets of the balanced (acyclic) induced subgraph polytope ⋮ A cutting plane algorithm for a clustering problem ⋮ Combining simulated annealing with local search heuristics ⋮ A partitioning column approach for solving LED sorter manipulator path planning problems ⋮ Ailsa H. Land and her 1979 study of the traveling salesman problem: personal reminiscences and historical remarks ⋮ Computational experience with a branch-and-cut algorithm for flowshop scheduling with setups. ⋮ Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times ⋮ Heuristics and their design: A survey ⋮ Lower bounds for the symmetric travelling salesman problem from Lagrangean relaxations ⋮ Facet identification for the symmetric traveling salesman polytope ⋮ Exact and inexact solution procedures for the order picking in an automated carousal conveyor ⋮ An efficient algorithm for the minimum capacity cut problem ⋮ The symmetric traveling salesman problem and edge exchanges in minimal 1- trees ⋮ The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities ⋮ Euclidean semi-matchings of random samples ⋮ The traveling salesman problem in graphs with some excluded minors ⋮ Classical cuts for mixed-integer programming and branch-and-cut ⋮ On solving cycle problems with branch-and-cut: extending shrinking and exact subcycle elimination separation algorithms ⋮ Separating maximally violated comb inequalities in planar graphs ⋮ The traveling salesman problem: An overview of exact and approximate algorithms ⋮ On the vehicle routing problem ⋮ Large-step Markov chains for the TSP incorporating local search heuristics ⋮ The complexity of lifted inequalities for the knapsack problem ⋮ Branch and cut methods for network optimization ⋮ Facets of the three-index assignment polytope ⋮ Minimum-weight two-connected spanning networks ⋮ An efficient procedure for the N-city traveling salesman problem ⋮ An efficient procedure for obtaining feasible solutions to the n-city traveling salesman problem ⋮ A diagonal completion and 2-optimal procedure for the travelling salesman problem ⋮ Rearrangement of DNA fragments: a branch-and-cut algorithm. ⋮ Multi stage Monte Carlo optimization applied to a six hundred point travelling salesman problem ⋮ Provably good solutions for the traveling salesman problem ⋮ Valid inequalities and facets of the capacitated plant location problem ⋮ Using rank-1 lift-and-project closures to generate cuts for 0-1 MIPs, a computational investigation ⋮ Cutting-plane proofs in polynomial space ⋮ Polyhedral techniques in combinatorial optimization I: Theory ⋮ A cutting plane algorithm for minimum perfect 2-matchings ⋮ Facets and algorithms for capacitated lot sizing ⋮ Computing in combinatorial optimization ⋮ A successful algorithm for solving directed Hamiltonian path problems ⋮ An improved assignment lower bound for the Euclidean traveling salesman problem ⋮ A branch and bound algorithm for symmetric 2-peripatetic salesman problems ⋮ Genetic algorithms for the traveling salesman problem based on a heuristic crossover operation ⋮ A technique for speeding up the solution of the Lagrangean dual ⋮ Solution of large-scale symmetric travelling salesman problems ⋮ A cutting plane procedure for the travelling salesman problem on road networks
This page was built for publication: Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
