Generalized domino-parity inequalities for the symmetric traveling salesman problem

William J. Cook, Daniel G. Espinoza, Marcos Goycoolea

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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 languageEnglish
Pages (from-to)479-493
Number of pages15
JournalMathematics of Operations Research
Issue number2
StatePublished - May 2010


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


Dive into the research topics of 'Generalized domino-parity inequalities for the symmetric traveling salesman problem'. Together they form a unique fingerprint.

Cite this