Separation algorithms for classes of STSP inequalities arising from a new STSP relaxation

• 成果类型: Article
• 署名作者: Carr, R
• 署名单位: United States Department of Energy (DOE); Sandia National Laboratories
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1030.0058
• 发表日期: 2004
• 页码: 80-91
• 关键词: traveling salesman problem; comb inequalities; planar graphs; polytope; tsp

摘要

The problem of separating a class of inequalities that are valid for the symmetric traveling salesman problem (STSP) consists of devising an efficient method that, given a fractional point x* for a relaxation of the STSP, either finds an inequality in the given class of STSP inequalities that is violated by x* or determines that there are no such violated inequalities. We can define important classes of STSP inequalities by performing Naddef's and Rinaldi's (1993) node-lifting operation on STSP inequalities defined on small graphs. We present efficient methods for exactly separating large classes of STSP inequalities that arise from an STSP relaxation related to node lifting. In particular, we show how to find efficiently the most-violated inequality in the class of STSP inequalities having a backbone set with a constant number k of vertices, and thus separate in polynomial time the class of all STSP inequalities whose backbone set has at most k vertices.