Engineering Commons^™

Cut-And-Solve: A Linear Search Strategy For Combinatorial Optimization Problems, Sharlee Climer, Weixiong Zhang

All Computer Science and Engineering Research

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 …