Some embodiments provide an LP method that identities routes. In some embodiments,
this method is used by a router that defines routes for nets within a region of
a design layout. Each net has a set of pins in the region. The method partitions
the region into a set or sub-regions. For each particular net, the method identifies
a set or route. Each route for a net traverses the sub-regions that contain the
net's pins. Each route includes a set of route edge, and each route edge connects
two sub-regions. Also, some of the identified routes have route edges that are
at least partially diagonal. The method formulates a linear-programming ("LP")
problem based on the identified sets of routes for the nets. The method then solves
the LP problem to identify one route for each net. 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 route for each net. 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 route for each net.
