METHOD AND SYSTEM FOR TRANSLATING LOGICAL CONSTRAINTS TO LINEAR CONSTRAINTS

摘要

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.