Mixed Integer Programming Models for Detailed Placement

Existing detailed placement optimization methods typically involve the use of enumeration to determine the optimal location of a small number of cells. We propose two Mixed Integer Programming (MIP) models that can optimize the detailed placement of more cells efficiently. Compared with existing models, the first proposed model has fewer integer variables. The second proposed model, derived based on Dantzig-Wolfe decomposition principle, is with tighter bounds during its solution. Experimental results show that both models are capable of optimizing in reasonable time the detailed placement of much larger problem instances than existing models. Experiments on large-scale real benchmark circuits also show that detailed placer based on advanced MW models can effectively reduce half-perimeter wirelengh (HPWL), as well as routed wirelength and vertical via, of the original placement results generated by enumeration approach.