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.
|Number of pages||15|
|Journal||Mathematics of Operations Research|
|State||Published - May 2010|
- Cutting planes
- Secondary: 65K05
- Separating algorithms MSC2000 subject classification: Primary: 90C10, 90C27
- Traveling salesman problem