Converting a conditional constraint (if-then) to integer linear programming.

Question

How can I linearly express the following conditional constraint: If x1 = 1 (x1 is selected) then x2+x3 = 0 (x2 and x3 is not selected) if x1,x2 and x3 are binary?

Answer 1

Rewriting your logical proposition in conjunctive normal form somewhat automatically yields two linear constraints: \begin{equation} x_1 \implies (\neg x_2 \land \neg x_3) \\ \neg x_1 \lor (\neg x_2 \land \neg x_3) \\ (\neg x_1 \lor \neg x_2) \land (\neg x_1 \lor \neg x_3) \\ ((1- x_1) + (1- x_2) \ge 1) \land ((1- x_1) + (1- x_3) \ge 1) \\ (x_1 + x_2 \le 1) \land (x_1 + x_3 \le 1) \end{equation} Another approach is to form a single big-M constraint: $$x_2+x_3\le 2(1-x_1).$$ But that is weaker, being an aggregation of the previous two constraints. For example, the big-M constraint does not cut off $x=(1/2,1/4,3/4)$.