Patent ID: 7761818

Claim:
A method, performed on a computer system, for obtaining a feasible integer solution in a hierarchical circuit layout optimization, the method comprising: using the computer system to perform the following: receiving a hierarchical circuit layout and ground rule files; representing constraints in the hierarchical circuit layout as an original integer linear programming problem; deriving a relaxed linear programming problem from the original integer linear programming problem by relaxing integer constraints and using relaxation variables on infeasible constraints, wherein infeasible constraints are constraints that are unsatisfied for the hierarchical circuit layout; solving the relaxed linear programming problem to obtain a linear programming solution; rounding a subset of variables from the relaxed linear programming problem to integer values according to the linear programming solution, wherein the rounding of a subset of variables comprises partitioning the subset of variables into at least one of three groups comprising edge variables in equal constraints involving only one edge variable, transform variables and other edge variables; rounding variables partitioned into each of the three groups in a predetermined manner; determining if all of the variables are rounded to integer values, wherein unrounded variables are iterated back through the deriving of a relaxed linear programming problem, solving of the relaxed linear programming problem, and rounding of a subset of variables; and generating a modified hierarchical circuit layout in response to a determination that all the variables are rounded to integer values.