Negative Thinking by Incremental Problem Solving: Application to Unate Covering
Evguenii I. Goldberg, Luca P. Carloni, Tiziano Villa, Robert K. Brayton, Alberto L. Sangiovanni-vincentelli · 1997
We introduce a new technique to solve exactly a discrete optimization problem, based on the paradigm of "negative" thinking. The motivation is that when searching the space of solutions, often a good solution is reached quickly and then improved only a few times before the optimum is found: hencemost of the solution space is explored to certify optimality, but it does not yield any improvement of the cost function. So it is quite natural for an algorithm to be "skeptical" about the chance to improve the current best solution. For illustration we have applied our approach to the unate covering problem. We designed a procedure, raiser, implementing a negative thinking search, which is incorporated into a common branch-and-bound procedure. Raiser is invoked at a node of the search tree which is deep enough to justify negative thinking. Raiser tries to detect a hard core of the matrix corresponding to the node by augmenting an independent set of rows in order to increase incrementally the ...