I am trying to linearize the following constraint:
$x*y*z + a*b + s*t = 1$,
where all variables are binary.
I read that this is possible using the "big-M" method, but was not sure how to apply it when there are multiple terms, or perhaps, there is another method?
Thanks!
Rewriting the desired logical proposition $$[(x \land y \land z) \land \neg (a \land b) \land \neg(s \land t)] \lor [\neg (x \land y \land z) \land (a \land b) \land \neg(s \land t)] \lor [\neg (x \land y \land z) \land \neg (a \land b) \land (s \land t)] $$ in conjunctive normal form yields $$(\neg a\lor \neg b\lor \neg s\lor \neg t)\land (\neg a\lor \neg b\lor \neg x\lor \neg y\lor \neg z)\land (a\lor s\lor x)\land (a\lor s\lor y)\land (a\lor s\lor z)\land (a\lor t\lor x)\land (a\lor t\lor y)\land (a\lor t\lor z)\land (b\lor s\lor x)\land (b\lor s\lor y)\land (b\lor s\lor z)\land (b\lor t\lor x)\land (b\lor t\lor y)\land (b\lor t\lor z)\land (\neg s\lor \neg t\lor \neg x\lor \neg y\lor \neg z),$$ which corresponds to linear constraints \begin{align} 1- a+ 1- b+ 1- s+ 1- t&\ge 1\\ 1- a+ 1- b+ 1- x+ 1- y+ 1- z&\ge 1\\ a+ s+ x&\ge 1\\ a+ s+ y&\ge 1\\ a+ s+ z&\ge 1\\ a+ t+ x&\ge 1\\ a+ t+ y&\ge 1\\ a+ t+ z&\ge 1\\ b+ s+ x&\ge 1\\ b+ s+ y&\ge 1\\ b+ s+ z&\ge 1\\ b+ t+ x&\ge 1\\ b+ t+ y&\ge 1\\ b+ t+ z&\ge 1\\ 1- s+ 1- t+ 1- x+ 1- y+ 1- z&\ge 1 \end{align}
An alternative approach introduces a new variable for each product and then linearizes the products: \begin{align} u+v+w &= 1\\ u &\le x\\ u &\le y\\ u &\le z\\ u &\ge x + y + z - 2 \\ v &\le a\\ v &\le b\\ v &\ge a + b - 1 \\ w &\le s\\ w &\le t\\ w &\ge s + t - 1 \\ u,v,w &\ge 0 \end{align}