## Abstract

We extend the work of Letchford [Letchford, A. N. 2000. Separating a superclass of comb inequalities in planar graphs. Math. Oper. Res. 25 443-454] by introducing a new class of valid inequalities for the traveling salesman problem, called the generalized domino-parity (GDP) constraints. Just as Letchford's domino-parity constraints generalize comb inequalities, GDP constraints generalize the most well-known multiple-handle constraints, including clique-tree, bipartition, path, and star inequalities. Furthermore, we show that a subset of GDP constraints containing all of the clique-tree inequalities can be separated in polynomial time, provided that the support graph G^{*} is planar, and provided that we bound the number of handles by a fixed constant.

Original language | English |
---|---|

Pages (from-to) | 479-493 |

Number of pages | 15 |

Journal | Mathematics of Operations Research |

Volume | 35 |

Issue number | 2 |

DOIs | |

State | Published - May 2010 |

## Keywords

- Cutting planes
- Secondary: 65K05
- Separating algorithms MSC2000 subject classification: Primary: 90C10, 90C27
- Traveling salesman problem