A cell-based hierarchical pitchmatching compaction using minimal LP

We describe a new linear programming (LP)-based hierarchical pitchmatching method. With a simplified treatment of the intercell constraints, the size of the LP problems is significantly reduced as compared to the best known results. In particular, the pitchmatching problem is decomposed into independent subproblems by exploiting the layout slicing structure. Each subproblem is further “folded” to reduce the LP problem size. We prove that the new method generates smaller LP problem than the previously best known approach. Experimental data show that the LP problem size can be 10 times smaller