Optimal Layout via Boolean Satisfiability
Abstract
Most optimization problems in layout have been shown to be NP- complete, resulting in researchers abandoning the search for optimum solutions even for small-scale problem instances. In this paper we transform various NP- complete problems in layout, namely two-and multi-layer dogleg routing, two-way partitioning, one-dimensional and two-dimensional placement, into Boolean satisfiability problems. The transformations are efficient in that the number of inputs to the Boolean function, for which we have to find a satisfying assignment, only grows linearly or quasi-linearly with the layout problem size. These transformations also produce a minimal-sized Boolean function, in order to speed up satisfiability check performance. We apply sophisticated test generation and logic verification strategies that can be used to check for Boolean function satisfiability to these layout problems. We present experimental results which indicate that problems of significant size can be solved optimally using this approach. This approach to optimal layout is considerably more efficient than exhaustive search. Further, we show that this approach to layout optimization offers an elegant means of representing and searching the entire space of feasible solutions in an attempt to optimize a complex cost function with associated constraints. Keywords: Reprints; Electronic design.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1989
- Accession Number
- ADA216777
Entities
People
- Srinivas Devadas
Organizations
- Massachusetts Institute of Technology