Friday, April 17, 2009

How to linearize

> I have this expression x1⋅x2⋅x3, where all variables are binary. How can I linearize this?

The nonlinear equation z=x1⋅x2⋅x3 with xi ∈ {0,1} can be linearized as:

z ≤ x1
z ≤ x2
z ≤ x3
z ≥ x1+x2+x3−2

z can be continuous with z ∈ [0,1]. See also http://yetanothermathprogrammingconsultant.blogspot.com/2008/05/multiplication-of-binary-variables.html.