Document Type

Technical Report

Publication Date

2005-08-25

Filename

WUCSE-2005-1.pdf

Technical Report Number

WUCSE-2005-1

Abstract

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. This search is different from traditional tree searching 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 whihc the search may get lost. Furthermore, its memory requirements are nominal. For these reasons, it may be potentially useful as an alternative approach 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 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 our websites.

Comments

Permanent URL: http://dx.doi.org/10.7936/K72J697H

Download

Share

COinS