Patent ID: 7062729
Filing Date: 2006-06-13
Classification: G06F

Abstract:
1. A method of creating a circuit layout based on a plurality of constraints and at least one objective, comprising the steps of: (a) constructing a Boolean satisfiability problem containing a plurality of constraints and at least one objective; (b) determining if said at least one objective renders said Boolean satisfiability problem unsatisfiable; (c) if said at least one objective renders said Boolean satisfiability problem unsatisfiable, removing said at least one objective so as to form a reduced Boolean satisfiability problem, wherein said reduced Boolean satisfiability problem comprises a plurality of variables and the method further comprises: the step of rounding non-integer results of an linear program (LP) based on a truth assignment to said variables of said reduced Boolean satisfiability problem; and (d) creating a circuit layout as a function of said reduced Boolean satisfiability problem.