Conditional statement in mixed integer linear programming

Question

I have been trying to enforce the following conditional statement in a MILP:

If $X_1 + 2(X_2 + X_3) = 4$, then $X_4 = 1$.

where $X_1, X_2, X_3, X_4$ are binary. How can I write this in conventional constraints, so that I could use a MILP solver?

Best regards, Hans

Answer 1

If they are all binary, the only way $X_1 + 2 (X_2 + X_3) = 4$ is $X_1 = 0$, $X_2 = X_3 = 1$. So your constraint could be $$-X_1 + X_2 + X_3 - X_4 \le 1$$

Answer 2

As @RobertIsrael noted, your proposition is equivalent to $$(\lnot X_1 \land X_2 \land X_3) \implies X_4.$$ Rewriting in conjunctive normal form yields $$ \lnot (\lnot X_1 \land X_2 \land X_3) \lor X_4 \\ X_1 \lor \lnot X_2 \lor \lnot X_3 \lor X_4 \\ X_1 + (1 - X_2) + (1 - X_3) + X_4 \ge 1 \\ X_1 - X_2 - X_3 + X_4 \ge -1 $$