TY - JOUR

T1 - Cut-and-solve

T2 - An iterative search strategy for combinatorial optimization problems

AU - Climer, Sharlee

AU - Zhang, Weixiong

N1 - Funding Information:
This research was supported in part by NDSEG and Olin Fellowships, by NSF grants IIS-0196057, ITR/EIA-0113618, and IIS-0535257, and in part by DARPA Cooperative Agreement F30602-00-2-0531. We are grateful to the anonymous reviewers of this paper, as well as a preliminary conference paper, who provided a number of valuable insights. We thank Matthew Levine, for the use of his minimum cut code, and David Applegate, Robert Bixby, Vašek Chvátal, and William Cook for the use of Concorde. We also extend thanks to Matteo Fischetti, who generously shared his expertise in several discussions.

PY - 2006/6

Y1 - 2006/6

N2 - Branch-and-bound and branch-and-cut use search trees to identify optimal solutions to combinatorial optimization problems. In this paper, we introduce an iterative search strategy which we refer to as cut-and-solve and prove optimality and termination for this method. This search is different from traditional tree search as there is no branching. At each node in the search path, a relaxed problem and a sparse problem are solved and a constraint is added to the relaxed problem. The sparse problems provide incumbent solutions. When the constraining of the relaxed problem becomes tight enough, its solution value becomes no better than the incumbent solution value. At this point, the incumbent solution is declared to be optimal. This strategy is easily adapted to be an anytime algorithm as an incumbent solution is found at the root node and continuously updated during the search. Cut-and-solve enjoys two favorable properties. Since there is no branching, there are no "wrong" subtrees in which the search may get lost. Furthermore, its memory requirement is negligible. For these reasons, it has potential for problems that are difficult to solve using depth-first or best-first search tree methods. In this paper, we demonstrate the cut-and-solve strategy by implementing a generic version of it for the Asymmetric Traveling Salesman Problem (ATSP). Our unoptimized implementation outperformed state-of-the-art solvers for five out of seven real-world problem classes of the ATSP. For four of these classes, cut-and-solve was able to solve larger (sometimes substantially larger) problems. Our code is available at our websites.

AB - Branch-and-bound and branch-and-cut use search trees to identify optimal solutions to combinatorial optimization problems. In this paper, we introduce an iterative search strategy which we refer to as cut-and-solve and prove optimality and termination for this method. This search is different from traditional tree search as there is no branching. At each node in the search path, a relaxed problem and a sparse problem are solved and a constraint is added to the relaxed problem. The sparse problems provide incumbent solutions. When the constraining of the relaxed problem becomes tight enough, its solution value becomes no better than the incumbent solution value. At this point, the incumbent solution is declared to be optimal. This strategy is easily adapted to be an anytime algorithm as an incumbent solution is found at the root node and continuously updated during the search. Cut-and-solve enjoys two favorable properties. Since there is no branching, there are no "wrong" subtrees in which the search may get lost. Furthermore, its memory requirement is negligible. For these reasons, it has potential for problems that are difficult to solve using depth-first or best-first search tree methods. In this paper, we demonstrate the cut-and-solve strategy by implementing a generic version of it for the Asymmetric Traveling Salesman Problem (ATSP). Our unoptimized implementation outperformed state-of-the-art solvers for five out of seven real-world problem classes of the ATSP. For four of these classes, cut-and-solve was able to solve larger (sometimes substantially larger) problems. Our code is available at our websites.

KW - Anytime algorithms

KW - Branch-and-bound

KW - Branch-and-cut

KW - Linear programming

KW - Search strategies

KW - Traveling Salesman Problem

UR - http://www.scopus.com/inward/record.url?scp=33646106102&partnerID=8YFLogxK

U2 - 10.1016/j.artint.2006.02.005

DO - 10.1016/j.artint.2006.02.005

M3 - Article

AN - SCOPUS:33646106102

SN - 0004-3702

VL - 170

SP - 714

EP - 738

JO - Artificial Intelligence

JF - Artificial Intelligence

IS - 8-9

ER -