×

Global optimization algorithms for VLSI compaction problems. (English) Zbl 0793.68081

Summary: An important optimization problem in VLSI design arises repeatedly in the process of solving the circuit compaction problem. We model this nonconvex programming problem as a jointly constrained bilinear program and present a linear programming relaxation which is equivalent to convexifying the bilinear program over a bounded region. In the overall VLSI design process, we propose using these linear programs in lieu of heuristics to determine circuit compaction. We also indicate how the bilinear programs can be solved to optimality using an available global optimization code, thereby obtaining even better VLSI designs. The purpose of this note is to indicate how some new global optimization techniques can be used in the process of VLSI technology.

MSC:

68W35 Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.)
68N17 Logic programming