Separating maximally violated comb inequalities in planar graphs

• 成果类型: Article
• 署名作者: Fleischer, L; Tardos, É
• 署名单位: Columbia University; Cornell University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.24.1.130
• 发表日期: 1999
• 页码: 130-148
• 关键词: traveling salesman problem; edge-connectivity; cut

摘要

Traveling Salesman Problem (TSP) is a benchmark problem in combinatorial optimization. It was one of the very first problems used for developing and testing approaches to solving large integer programs. including cutting plane algorithms and branch-and-cut algorithms. Much of the research in this area has been focused on finding new classes of facets for the TSP polytope and much less attention has been paid to algorithms for separating from these classes of facets. In this paper, we consider the problem of finding violated comb inequalities. If there are no violated subtour constraints in a fractional solution of the TSP, a comb inequality may not be violated by more than 1. Given a fractional solution in the subtour elimination polytope whose graph is planar, we either find a violated comb inequality or determine that here are no comb inequalities violated by 1, Our algorithm mns in O(n + MC(n)) time. where MC(n) is the time to compute a cactus representation of all minimum cuts of a weighted planar graph on n vertices.