ABSTRACT

Nearly six decades of steady exponential improvement in the design and manufacture of very large-scale integrated circuits (VLSI) have produced some of the largest combinatorial optimization problems ever considered. Placement —arranging the elements of a circuit in the plane—is one of the most difficult of these. As of 2017, mixed integer nonconvex nonlinear-programming (NLP) formulations of placement with more than 100 million variables and constraints are not unusual, and problem sizes continue to grow with Moore’s Law. Realistic objectives and constraints for placement incorporate complex models of signal timing, power consumption, wiring routability, manufacturability, noise, temperature, and so on. A popular and very useful simplification is to minimize a standard estimate of total wirelength subject only to pairwise nonoverlap constraints. Although this abstract model problem cannot fully express the scope of the placement challenge, evidence suggests that it does capture a critical part of the core mathematical difficulty [1–4].