Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope

DOI10.1016/j.disopt.2013.07.001zbMath1474.90290OpenAlexW2086332879MaRDI QIDQ1662101

Y. Aharonov

Publication date: 17 August 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2013.07.001

zbMATH Keywords

symmetric traveling salesman problemmultistage insertion formulationnonadjacency testingpedigree polytope

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27)

Related Items (3)

The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract) ⋮ Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search ⋮ Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph

Uses Software

• Concorde

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Classification of travelling salesman problem formulations
• Hamiltonicity and combinatorial polyhedra
• An analytical comparison of different formulations of the travelling salesman problem
• Adjacency of the best and second best valued solutions in combinatorial optimization problems
• The traveling salesman problem and its variations
• Adjacency on combinatorial polyhedra
• An alternate formulation of the symmetric traveling salesman problem and its properties
• On pedigree polytopes and Hamiltonian cycles
• Integer Programming Formulation of Traveling Salesman Problems
• On the Membership Problem of the Pedigree Polytope
• Traveling Salesman Problem and Membership in Pedigree Polytope - A Numerical Illustration
• Adjacency of the Traveling Salesman Tours and $0 - 1$ Vertices
• The adjacency relation on the traveling salesman polytope is NP-Complete
• Separating over classes of TSP inequalities defined by 0 node-lifting in polynomial time
• Technical Note—An n-Constraint Formulation of the (Time-Dependent) Traveling Salesman Problem
• A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem
• Solution of a Large-Scale Traveling-Salesman Problem
• On the Tours of a Traveling Salesman
• Combinatorial optimization. Theory and algorithms.
• On the equivalence of the multistage-insertion and cycle-shrink formulations of the symmetric traveling salesman problem

This page was built for publication: Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope