Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - Separating a superclass of comb inequalities in planar graphs
AU - Letchford, A. N.
PY - 2000
Y1 - 2000
N2 - Many classes of valid and facet-inducing inequalities are known for the family of polytopes associated with the Symmetric Travelling Salesman Problem (STSP), including subtour elimination, 2-matching and comb inequalities. For a given class of inequalities, an exact separation algorithm is a procedure which, given an LP relaxation vector x*, finds one or more inequalities in the class which are violated by x*, or proves that none exist. Such algorithms are at the core of the highly successful branch-and-cut algorithms for the STSP. However, whereas polynomial time exact separation algorithms are known for subtour elimination and 2-matching inequalities, the complexity of comb separation is unknown. A partial answer to the comb problem is provided in this paper. We define a generalization of comb inequalities and show that the associated separation problem can be solved efficiently when the subgraph induced by the edges with x*_e > 0 is planar. The separation algorithm runs in O(n^3) time, where n is the number of vertices in the graph.
AB - Many classes of valid and facet-inducing inequalities are known for the family of polytopes associated with the Symmetric Travelling Salesman Problem (STSP), including subtour elimination, 2-matching and comb inequalities. For a given class of inequalities, an exact separation algorithm is a procedure which, given an LP relaxation vector x*, finds one or more inequalities in the class which are violated by x*, or proves that none exist. Such algorithms are at the core of the highly successful branch-and-cut algorithms for the STSP. However, whereas polynomial time exact separation algorithms are known for subtour elimination and 2-matching inequalities, the complexity of comb separation is unknown. A partial answer to the comb problem is provided in this paper. We define a generalization of comb inequalities and show that the associated separation problem can be solved efficiently when the subgraph induced by the edges with x*_e > 0 is planar. The separation algorithm runs in O(n^3) time, where n is the number of vertices in the graph.
KW - Symmetric travelling salesman problem
KW - branch-and-cut
KW - valid inequalities
KW - Separation algorithm
U2 - 10.1287/moor.25.3.443.12213
DO - 10.1287/moor.25.3.443.12213
M3 - Journal article
VL - 25
SP - 443
EP - 454
JO - Mathematics of Operations Research
JF - Mathematics of Operations Research
SN - 0364-765X
IS - 3
ER -