0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.