Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies

DOI10.1016/0167-6377(95)00038-0zbMath0855.90087OpenAlexW2014514762MaRDI QIDQ1919186

Shirley Shmerling, Agha Iqbal Ali

Publication date: 11 February 1997

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

Full work available at URL: https://doi.org/10.1016/0167-6377(95)00038-0

zbMATH Keywords

travelling salesmanHamiltonian pathsroutingspanning treesduality gapsfacet-inducing inequalitiesgraphical-construct-based Lagrangian relaxation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10)

Related Items

Solving linear programming relaxations associated with Lagrangean relaxations by Fenchel cutting planes

Cites Work

• Unnamed Item
• Unnamed Item
• Optimizing over the subtour polytope of the travelling salesman problem
• Solution of large-scale symmetric travelling salesman problems
• A dual ascent algorithm for the 1-tree relaxation of the symmetric traveling salesman problem
• The asymmetric m-travelling salesman problem: A duality based branch-and- bound algorithm
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• A new class of cutting planes for the symmetric travelling salesman problem
• The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities
• A cutting plane algorithm for minimum perfect 2-matchings
• Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
• On the symmetric travelling salesman problem I: Inequalities
• An Optimal Solution Method for Large-Scale Multiple Traveling Salesmen Problems
• Graphical-structure-based models for routing problems
• On the symmetric travelling salesman problem: Solution of a 120-city problem
• On the symmetric travelling salesman problem: A computational study
• Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Odd Minimum Cut-Sets and b-Matchings
• Improvements of the Held—Karp algorithm for the symmetric traveling-salesman problem
• Solution of a Large-Scale Traveling-Salesman Problem
• On a Linear-Programming, Combinatorial Approach to the Traveling-Salesman Problem
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II