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

Polynomial-time separation of simple comb inequalities

Research output: Working paper

Published

Standard

Polynomial-time separation of simple comb inequalities. / Letchford, A N; Lodi, A.
Lancaster University: The Department of Management Science, 2003. (Management Science Working Paper Series).

Research output: Working paper

Harvard

Letchford, AN & Lodi, A 2003 'Polynomial-time separation of simple comb inequalities' Management Science Working Paper Series, The Department of Management Science, Lancaster University.

APA

Letchford, A. N., & Lodi, A. (2003). Polynomial-time separation of simple comb inequalities. (Management Science Working Paper Series). The Department of Management Science.

Vancouver

Letchford AN, Lodi A. Polynomial-time separation of simple comb inequalities. Lancaster University: The Department of Management Science. 2003. (Management Science Working Paper Series).

Author

Letchford, A N ; Lodi, A. / Polynomial-time separation of simple comb inequalities. Lancaster University : The Department of Management Science, 2003. (Management Science Working Paper Series).

Bibtex

@techreport{3fe991fb051a4206882589677b47102c,
title = "Polynomial-time separation of simple comb inequalities",
abstract = "The comb inequalities are a well-known class of facet-inducing inequalities for the Travelling 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 Chvatal comb inequalities. In 1982, Padberg and Rao [29] 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.",
keywords = "travelling salesman problem, cutting planes, separation",
author = "Letchford, {A N} and A Lodi",
note = "This was eventually published 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.",
year = "2003",
language = "English",
series = "Management Science Working Paper Series",
publisher = "The Department of Management Science",
type = "WorkingPaper",
institution = "The Department of Management Science",

}

RIS

TY - UNPB

T1 - Polynomial-time separation of simple comb inequalities

AU - Letchford, A N

AU - Lodi, A

N1 - This was eventually published 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.

PY - 2003

Y1 - 2003

N2 - The comb inequalities are a well-known class of facet-inducing inequalities for the Travelling 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 Chvatal comb inequalities. In 1982, Padberg and Rao [29] 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.

AB - The comb inequalities are a well-known class of facet-inducing inequalities for the Travelling 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 Chvatal comb inequalities. In 1982, Padberg and Rao [29] 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.

KW - travelling salesman problem

KW - cutting planes

KW - separation

M3 - Working paper

T3 - Management Science Working Paper Series

BT - Polynomial-time separation of simple comb inequalities

PB - The Department of Management Science

CY - Lancaster University

ER -