Facet identification for the symmetric traveling salesman polytope

DOI10.1007/BF01580861zbMath0706.90050OpenAlexW1991119408WikidataQ58002958 ScholiaQ58002958MaRDI QIDQ918865

Giovanni Rinaldi, Manfred W. Padberg

Publication date: 1990

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

identificationcliquecomb inequalitiessymmetric traveling salesman2-matching inequalitiesfacet inducing inequalitiespolytopal cutting plane algorithmReduction techniquessequence of linear relaxationssubtour elimination inequalities

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (42)

A fast optimization method based on a hierarchical strategy for the travelling salesman problem ⋮ A lifting procedure for asymmetric traveling salesman polytope and a large new class of facets ⋮ The static bicycle relocation problem with demand intervals ⋮ The precedence-constrained asymmetric traveling salesman polytope ⋮ Routing problems: A bibliography ⋮ Obtaining minimum-correlation Latin hypercube sampling plans using an IP-based heuristic ⋮ The pickup and delivery problem: Faces and branch-and-cut algorithm ⋮ Mincut sensitivity data structures for the insertion of an edge ⋮ A branch-and-cut algorithm for the equicut problem ⋮ Multi-depot multiple TSP: a polyhedral study and computational results ⋮ Genetic algorithms for the traveling salesman problem ⋮ Separating clique tree and bipartition inequalities in polynomial time ⋮ The consistent production routing problem ⋮ Modeling the flying sidekick traveling salesman problem with multiple drones ⋮ An efficient branch-and-cut algorithm for the parallel drone scheduling traveling salesman problem ⋮ On the generation of metric TSP instances with a large integrality gap by branch-and-cut ⋮ Generating partitions of a graph into a fixed number of minimum weight cuts ⋮ On facet-inducing inequalities for combinatorial polytopes ⋮ On solving cycle problems with branch-and-cut: extending shrinking and exact subcycle elimination separation algorithms ⋮ The traveling salesman problem: An overview of exact and approximate algorithms ⋮ Exact methods for solving the elementary shortest and longest path problems ⋮ Computing finest mincut partitions of a graph and application to routing problems ⋮ Branch and cut methods for network optimization ⋮ Shuffling heuristics for the storage location assignment in an AS/RS ⋮ Combinatorial structure and adjacency of vertices of polytope of \(b\)-factors ⋮ On the domino-parity inequalities for the STSP ⋮ A branch-and-cut algorithm for the undirected prize collecting traveling salesman problem ⋮ Solving the Job Sequencing and Tool Switching Problem as a nonlinear least cost Hamiltonian cycle problem ⋮ Improved branch-and-cut for the inventory routing problem based on a two-commodity flow formulation ⋮ Exact and Heuristic Algorithms for Capacitated Vehicle Routing Problems with Quadratic Costs Structure ⋮ Provably good solutions for the traveling salesman problem ⋮ The graphical relaxation: A new framework for the symmetric traveling salesman polytope ⋮ An optimality cut for mixed integer linear programs ⋮ The Branch and Cut Method for the Clique Partitioning Problem ⋮ Polyhedral techniques in combinatorial optimization I: Theory ⋮ Combinatorial optimization and small polytopes ⋮ New inequalities for the general routing problem ⋮ Vehicle routing with stochastic demands and restricted failures ⋮ The attractive traveling salesman problem ⋮ A branch-and-cut algorithm for the capacitated profitable tour problem ⋮ Survey of facial results for the traveling salesman polytope ⋮ Solution of large-scale symmetric travelling salesman problems

Cites Work

• Unnamed Item
• Unnamed Item
• An efficient algorithm for the minimum capacity cut problem
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• A construction for binary matroids
• The ellipsoid method and its consequences in combinatorial optimization
• A cutting plane algorithm for minimum perfect 2-matchings
• Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
• On the symmetric travelling salesman problem II: Lifting theorems and facets
• Solving matching problems with linear programming
• Multi-Terminal Network Flows
• On the symmetric travelling salesman problem: A computational study
• Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
• Odd Minimum Cut-Sets and b-Matchings
• A man-machine approach toward solving the traveling salesman problem
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem

This page was built for publication: Facet identification for the symmetric traveling salesman polytope