Method and system for translating logical constraints to linear constraints
US8321370B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Mar 6, 2009 |
| Grant date | Nov 27, 2012 |
| Priority date | — |
| Expiry date | Jun 30, 2031 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06N5/01
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A system and method is provided for translating one or more logical expressions E is TRUE, or statements of the form IF E1 is TRUE THEN E2 is TRUE, to a set of linear constraints. Examples in accordance with the present invention contribute to systems and methods for solving optimization problems that include constraints in the form of arbitrarily complex logical relationships between binary variables. Examples are also applicable to solving general optimization problems that have arbitrarily complex relationships between sets of linear constraints. The systems and methods combine simplification and ordering of logical expressions, factorization, direct translations of expressions, substitution of auxiliary variables, and substitution of auxiliary variables for phrases that would otherwise lead to an unacceptable number of linear constraints. The systems and methods also include mechanisms that reduce the number of required auxiliary variables by use of simplification, consolidation, Boolean identities, and auxiliary variable reuse.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.