Some results on node lifting of TSP inequalities

DOI10.1023/A:1009830409833MaRDI QIDQ1592839zbMATH OpenOpenAlexFDO

Authors R. Smith

Publication date 19 November 2002

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1009830409833

zbMATH Keywords

facetsinequalitiesnode liftingpolytopetraveling salesman problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Review text

This paper deals with facet-defining inequalities for the symmetric traveling salesman polytope, in particular those that can be obtained by performing \textit{D. Naddef} and \textit{G. Rinaldi}'s node lifting operation [Math. Program. 58A, 53-88 (1992; Zbl 0780.90103)]. 0-node lifting and generalizations are reviewed in sections 2 and 3. The main results are in sections 3 and 4, where it is shown -- that 1-node lifting of cut-based inequalities always has a geometric interpretation if a certain claw-free condition (satisfied by most of these TSP inequalities) is met, -- that simultaneous node liftings of a subtour elimination inequality are all subtour elimination inequalities, and where a non-geometric 1-node lifting of a cut based inequality with claws, the Petersen inequality, is examined.

Recommendations

• The Symmetric Traveling Salesman Polytope Revisited
• A lifting procedure for asymmetric traveling salesman polytope and a large new class of facets
• Separating over classes of TSP inequalities defined by 0 node-lifting in polynomial time
• Separation Algorithms for Classes of STSP Inequalities Arising from a New STSP Relaxation
• An extended approach for lifting clique tree inequalities

Cited in

(3)

• Separating over classes of TSP inequalities defined by 0 node-lifting in polynomial time
• An extended approach for lifting clique tree inequalities
• The Symmetric Traveling Salesman Polytope Revisited

This page was built for publication: Some results on node lifting of TSP inequalities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1592839)