LP METHOD AND APPARATUS FOR IDENTIFYING ROUTE PROPAGATIONS

Some embodiments provide an LP method that identifies route propagations. In some embodiments, this method is used by a router that hierarchically defines routes for nets within a region of a design layout. The router (1) partitions the region into a first set of sub-regions, and (2) for each particular net, identifies a route that traverses a set of the first-set sub-regions. In some embodiments, the invention's method partitions the first set of sub-regions into a second set of smaller sub-regions. It then identifies a plurality of propagation possibilities for propagating each route into the second set of smaller sub-regions of the first set sub-regions. The method next formulates a linear-programming (“LP”) problem based on the identified propagation possibilities. The method then solves the LP problem. In some embodiments, the formulated LP problem is an integer-linear-programming (“ILP”) problem, and solving the ILP problem returns integer solutions that specify one propagation permutation for each route in each first-set sub-region traversed by the route. In other embodiments, solving the LP problem returns real-numbered solutions. In some of these embodiments, the method converts the real-number solutions into integer solutions that specify one identified propagation permutation for each route in each first-set sub-region traversed by the route.