Integer programming in VLSI design

This paper surveys some recent developments in the application of combinatorial optimization to VLSI design. It focuses on integer programs arising in wire routing and PLA partitioning. Typically, the integer programs of most interest are computationally difficult. The paper presents approaches to approximately solving them by rounding the solutions to the relaxed linear programs. The resulting algorithms run in polynomial time and have provable performance guarantees. The paper also introduces the notion of multiterminal multicommodity flows, and points out their relevance to VLSI routing.