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

Research

Links

Text available via DOI:

Keywords

View graph of relations

Polynomial-time separation of simple comb inequalities

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Chapter (peer-reviewed) › peer-review

Published

Standard

Polynomial-time separation of simple comb inequalities. / Lodi, A; Letchford, A N.
Integer Programming and Combinatorial Optimization: Proceedings of the 9th International IPCO Conference. ed. / William J. Cook; Andreas S. Schulz. Berlin: Springer, 2002. p. 93-108 (Lecture Notes in Computer Science; Vol. 2337).

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Chapter (peer-reviewed) › peer-review

Harvard

Lodi, A & Letchford, AN 2002, Polynomial-time separation of simple comb inequalities. in WJ Cook & AS Schulz (eds), Integer Programming and Combinatorial Optimization: Proceedings of the 9th International IPCO Conference. Lecture Notes in Computer Science, vol. 2337, Springer, Berlin, pp. 93-108, 9th International IPCO Conference , Cambridge, Mass., United States, 27/05/02. https://doi.org/10.1007/3-540-47867-1_8

APA

Lodi, A., & Letchford, A. N. (2002). Polynomial-time separation of simple comb inequalities. In W. J. Cook, & A. S. Schulz (Eds.), Integer Programming and Combinatorial Optimization: Proceedings of the 9th International IPCO Conference (pp. 93-108). (Lecture Notes in Computer Science; Vol. 2337). Springer. https://doi.org/10.1007/3-540-47867-1_8

Vancouver

Lodi A, Letchford AN. Polynomial-time separation of simple comb inequalities. In Cook WJ, Schulz AS, editors, Integer Programming and Combinatorial Optimization: Proceedings of the 9th International IPCO Conference. Berlin: Springer. 2002. p. 93-108. (Lecture Notes in Computer Science). doi: 10.1007/3-540-47867-1_8

Author

Lodi, A ; Letchford, A N. / Polynomial-time separation of simple comb inequalities. Integer Programming and Combinatorial Optimization: Proceedings of the 9th International IPCO Conference. editor / William J. Cook ; Andreas S. Schulz. Berlin : Springer, 2002. pp. 93-108 (Lecture Notes in Computer Science).

Bibtex

@inbook{edc5bd3366d4423d92ed05eedd4e35f1,
title = "Polynomial-time separation of simple comb inequalities",
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.",
keywords = "travelling salesman problem",
author = "A Lodi and Letchford, {A N}",
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.; 9th International IPCO Conference ; Conference date: 27-05-2002 Through 29-05-2002",
year = "2002",
doi = "10.1007/3-540-47867-1_8",
language = "English",
isbn = "3-540-43676-6",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "93--108",
editor = "Cook, {William J.} and Schulz, {Andreas S.}",
booktitle = "Integer Programming and Combinatorial Optimization",

}

RIS

TY - CHAP

T1 - Polynomial-time separation of simple comb inequalities

AU - Lodi, A

AU - Letchford, A N

N1 - 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.

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

KW - travelling salesman problem

U2 - 10.1007/3-540-47867-1_8

DO - 10.1007/3-540-47867-1_8

M3 - Chapter (peer-reviewed)

SN - 3-540-43676-6

T3 - Lecture Notes in Computer Science

SP - 93

EP - 108

BT - Integer Programming and Combinatorial Optimization

A2 - Cook, William J.

A2 - Schulz, Andreas S.

PB - Springer

CY - Berlin

T2 - 9th International IPCO Conference

Y2 - 27 May 2002 through 29 May 2002

ER -