Introduction

 People

 Research themes:

   Embedded Systems

   Hybrid Systems

   Deep Submicron

   Logic Synthesis

 Other links:

   EE249

   CHESS

   GSRC

   BWRC

Negative Thinking for Exact Discrete Optimization

Robert Brayton, University of California at Berkeley 
Luca Carloni, University of California at Berkeley
Evguenii I. Goldberg, Cadence Berkeley Laboratories
Alberto Sangiovanni-Vincentelli, University of California at Berkeley
Tiziano Villa, Parades, Rome


We introduce a new technique for solving some discrete optimization problems 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 reached 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 no improvement in the cost function. This suggests that more powerful lower bounding would speed up the search dramatically. More radically, it would be 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 solution (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 where it tries to prove that solving the subproblem does not improve the solution. The latter is achieved by a new search procedure invoked when the Such a procedure is complete: 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 our new search procedure on top of {\sc espresso} and {\sc scherzo}, two state-of-art covering solvers used for CAD applications, showing that in both cases we obtain new search engines (respectively, {\sc aura} and {\sc aura~II}) much more efficient than the original ones.

Publications:

E.I. Goldberg, L.P. Carloni, T. Villa, R. K. Brayton and A.L. Sangiovanni-Vincentelli, Negative Thinking in Branch-and-Bound: the Case of Unate Covering, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 19, No. 3, March 2000.

L.P. Carloni, E.I. Goldberg, T. Villa, R.K. Brayton and A.L. Sangiovanni-Vincentelli, Aura II: Combining Negative Thinking and Branch-and-Bound in Unate Covering Problems, In "VLSI: Systems on a Chip" (L.M. Silveira, R. Reis, S. Devadas editors), Kluwer 1999.

E.I. Goldberg, L.P. Carloni, T. Villa, R.K. Brayton and A.L. Sangiovanni-Vincentelli, Negative Thinking in Search Methods: Application to Unate Covering, The Proceedings of the International Conference on Computer-Aided Design, 1997.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.

Contact 
©2002-2018 U.C. Regents