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?
-
$\begingroup$ Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to. $\endgroup$– José Carlos SantosApr 30, 2020 at 10:06
1 Answer
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)$.