Negative thinking in branch-and-bound: The case of unate covering

We introduce a new technique for solving some discrete optimization problem s exactly. The motivation is that when searching the space of solutions by a standard branch-and-bound (B&B) technique, often a good solution is reach ed quickly and then improved only a few times before the optimum is found: hence, most of the solution space is explored to certify optimality, with n o improvement in the cost function. This suggests that more powerful lower bounding would speed up the search dramatically. More radically, it would b e desirable to modify the search strategy with the goal of proving that the given subproblem cannot yield a solution better than the current best one (negative thinking), instead of branching further in search for a better so lution (positive thinking). For illustration we applied our approach to the unate covering problem. The algorithm starts in the positive-thinking mode by a standard B&B procedure that generates recursively smaller subproblems. If the current subproblem is "deep" enough, the algorithm switches to the negative thinking mode wher e it tries to prove that solving the subproblem does not improve the soluti on. The latter is achieved by a new search procedure invoked when the diffe rence between the upper and Lower bound is "small," Such a procedure is com plete: either it yields a Lower bound that matches the current upper bound, or it yields a new solution better than the current one. We implemented ou r new search procedure on top of ESPRESSO and SCHERZO, two state-of-art cov ering solvers used for computer-aided design applications, showing that in both cases we obtain new search engines (respectively, AURA and AURA II) mu ch more efficient than the original ones.