Generalized Domino-Parity Inequalities for the Symmetric Traveling Salesman Problem

• 成果类型: Article
• 署名作者: Cook, William J.; Espinoza, Daniel G.; Goycoolea, Marcos
• 署名单位: University System of Georgia; Georgia Institute of Technology; Universidad de Chile; Universidad Adolfo Ibanez
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1100.0451
• 发表日期: 2010
• 页码: 479-493
• 关键词: comb inequalities; facets

摘要

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 h.