OR Practice—Lagrangian Relaxation for Testing Infeasibility in VLSI Routing

Thomas A. Feo and Dorit S. Hochbaum
Additional contact information
Thomas A. Feo: University of California, Berkeley, California
Dorit S. Hochbaum: University of California, Berkeley, California

Operations Research, 1986, vol. 34, issue 6, 819-831

Abstract: We present a technique for very large scale integrated (VLSI) circuit design that recognizes the infeasibility of connecting pairs of terminals on modules placed on a chip. The method is based on a novel application of Lagrangian relaxation. Positive empirical results obtained from difficult problems found both in the literature and in industry strongly support the usefulness of this method. It has been incorporated in the proprietary computer-aided integrated circuit design package used at Bell Communications Research Inc., that allows systems engineers to design integrated circuits independent of the manufacturing processes specified by the foundries making the chips. The method has resulted in a faster turnaround time in the Bell design process.

Keywords: 482 VLSI routing problems; 625 Lagrangian relaxation approach (search for similar items in EconPapers)
Date: 1986
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.34.6.819 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:34:y:1986:i:6:p:819-831

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().