Article ID: | iaor20104595 |
Volume: | 35 |
Issue: | 2 |
Start Page Number: | 479 |
End Page Number: | 493 |
Publication Date: | May 2010 |
Journal: | Mathematics of Operations Research |
Authors: | Goycoolea Marcos, Espinoza Daniel G, Cook William J |
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