TY - GEN

T1 - A linear search strategy using bounds

AU - Climer, Sharlee

AU - Zhang, Weixiong

PY - 2004

Y1 - 2004

N2 - Branch-and-bound and branch-and-cut use search trees to identify optimal solutions. In this paper, we introduce a linear search strategy which we refer to as cut-and-solve and prove optimality and completeness for this method. 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. Its memory requirements are nominal and, since there is no branching, there are no "wrong" subtrees in which the search may get lost. For these reasons, it may be potentially useful as an alternative approach for problems that are difficult to solve using search tree methods. In this paper, we demonstrate the cut-and-solve strategy by implementing it for the Asymmetric Traveling Salesman Problem (ATSP). We compare this implementation with state-of-the-art ATSP solvers to validate the potential of this novel search strategy. Our code is available at (Climer & Zhang).

AB - Branch-and-bound and branch-and-cut use search trees to identify optimal solutions. In this paper, we introduce a linear search strategy which we refer to as cut-and-solve and prove optimality and completeness for this method. 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. Its memory requirements are nominal and, since there is no branching, there are no "wrong" subtrees in which the search may get lost. For these reasons, it may be potentially useful as an alternative approach for problems that are difficult to solve using search tree methods. In this paper, we demonstrate the cut-and-solve strategy by implementing it for the Asymmetric Traveling Salesman Problem (ATSP). We compare this implementation with state-of-the-art ATSP solvers to validate the potential of this novel search strategy. Our code is available at (Climer & Zhang).

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

M3 - Conference contribution

AN - SCOPUS:13444281236

SN - 1577352009

SN - 9781577352006

T3 - Proceedings of the 14th International Conference on Automated Planning and Scheduling, ICAPS 2004

SP - 132

EP - 141

BT - Proceedings of the 14th International Conference on Automated Planning and Scheduling, ICAPS 2004

A2 - Zilberstein, S.

A2 - Koehler, J.

A2 - Koenig, S.

T2 - Proceedings of the 14th International Conference on Automated Planning and Scheduling, ICAPS 2004

Y2 - 3 June 2004 through 7 June 2004

ER -