| Generalized domino-parity inequalities for the TSP (2008) | |||||||||||||||
Abstract | |||||||||||||||
| We extend the work of Letchford (2000) 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 h. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||