Patent ID: 7761819

Claim:
A method, executed by at least one processor of a computer, for modifying an integrated circuit layout, comprising: receiving a plurality of geometrical components in the integrated circuit layout; allocating a plurality of geometrical variables to represent said geometrical components; constructing a plurality of constraints representing required relationships among said geometrical variables; constructing a plurality of mutually exclusive constraint groups with each mutually exclusive constraint group consisting of two or more of said constraints of which only one of said constraints can be satisfied while the remaining of said constraints must be unsatisfied; allocating a plurality of integer variables that can only take value of either 0 or 1 for each of said constraints in said mutually exclusive constraint groups; constructing a mixed integer programming formulation using said geometrical variables, said integer variables, said constraints, and said mutually exclusive constraint groups such that a selection of said satisfied constraint in said each mutually exclusive constraint group is allowed to change; solving said mixed integer programming formulation to compute new values for said geometrical variables and said integer variables; extracting a modified integrated circuit layout from said new values of said geometrical variables; and storing said modified integrated circuit layout in a tangible computer accessible medium.