OR Practice—Lagrangian Relaxation for Testing Infeasibility in VLSI Routing

Operations Research · 1986 · Volume 34 · Issue 6

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

Enable JavaScript for citation tools and additional paper interactions.