Introduction
People Research
themes: Embedded Systems
Hybrid Systems
Deep Submicron
Logic Synthesis
Other links:
EE249
CHESS
GSRC
BWRC
|
Negative Thinking for Exact Discrete Optimization
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.
|