12,000

We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK

93%

93% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > Polynomial-time separation of simple comb inequ...
View graph of relations

« Back

Polynomial-time separation of simple comb inequalities

Research output: Contribution in Book/Report/ProceedingsChapter (peer-reviewed)

Published

Publication date2002
Host publicationInteger Programming and Combinatorial Optimization: Proceedings of the 9th International IPCO Conference
EditorsWilliam J. Cook, Andreas S. Schulz
Place of publicationBerlin
PublisherSpringer
Pages93-108
Number of pages16
ISBN (Print)3-540-43676-6
Original languageEnglish

Conference

Conference9th International IPCO Conference
CountryUnited States
CityCambridge, Mass.
Period27/05/0229/05/02

Publication series

NameLecture Notes in Computer Science
Volume2337

Conference

Conference9th International IPCO Conference
CountryUnited States
CityCambridge, Mass.
Period27/05/0229/05/02

Abstract

The comb inequalities are a well-known class of facet-inducing inequalities for the Traveling Salesman Problem, defined in terms of certain vertex sets called the handle and the teeth. We say that a comb inequality is simple if the following holds for each tooth: either the intersection of the tooth with the handle has cardinality one, or the part of the tooth outside the handle has cardinality one, or both. The simple comb inequalities generalize the classical 2-matching inequalities of Edmonds, and also the so-called Chv´atal comb inequalities. In 1982, Padberg and Rao gave a polynomial-time algorithm for separating the 2-matching inequalities – i.e., for testing if a given fractional solution to an LP relaxation violates a 2-matching inequality. We extend this significantly by giving a polynomial-time algorithm for separating the simple comb inequalities. The key is a result due to Caprara and Fischetti.

Bibliographic note

The full version of this paper appeared as: L.K. Fleischer, A.N. Letchford & A. Lodi (2006) Polynomial-time separation of a superclass of simple comb inequalities. Math. Oper. Res., 31(4), 696-713.