The symmetric traveling salesman polytope: New facets from the graphical relaxation

• 成果类型: Article
• 署名作者: Naddef, Denis; Rinaldi, Giovanni
• 署名单位: Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Consiglio Nazionale delle Ricerche (CNR); Istituto di Analisi dei Sistemi ed Informatica Antonio Ruberti (IASI-CNR)
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1060.0244
• 发表日期: 2007
• 页码: 233-256
• 关键词: efficient separation; inequalities; routines

摘要

The path, the wheelbarrow, and the bicycle inequalities have been shown by Cornuejols, Fonlupt, and Naddef to be facet-defining for the graphical relaxation of STSP(n), the polytope of the symmetric traveling salesman problem on an n-node complete graph. We show that these inequalities, and some generalizations of them, define facets also for STSP(n). In conclusion, we characterize a large family of facet-defining inequalities for STSP(n) that include, as special cases, most of the inequalities currently known to have this property as the comb, the clique tree, and the chain inequalities. Most of the results given here come from a strong relationship of STSP(n) with its graphical relaxation that we have pointed out in another paper, where the basic proof techniques are also described.