# If $x_1 \geq 4$ then **one** out of the following three constraints must hold: $x_2 \leq 3, x_3 \leq 4, x_4=5$

How does one linearize the following constraints:

If $$x_1 \geq 4$$ then one out of the following three constraints must hold: $$x_2 \leq 3, x_3 \leq 4, x_4=5$$.

$$x_1 \leq 4 + Mz_1$$ $$x_2 \leq 3 + M(1-z_2) + M(1-z_1)$$ $$x_3 \leq 4 + M(1-z_3) + M(1-z_1)$$ $$x_4 \leq 5 + M(1-z_4) + M(1-z_1)$$ $$x_4 + M(1-z_4) + M(1-z_1) \geq 5$$ $$z_2 + z_3 + z_4 = 1$$ $$z_i \text{ binary, }M\text{ large}$$

Is this correct?

Assuming that (a) you are OK with some ambiguity when $$x_1=4$$ (in which case $$z_1$$ can be either 0 or 1) and (b) you want at least one rather than exactly one of the three constraints to hold (nothing in your formulation prevents all three from being satisfied), then this is correct. It would also be correct to change the last constraint to $$z_2+z_3+z_4=z_1.$$ I don't know if that would help solver performance or not.

You can avoid several occurrences of $$M$$ as follows: \begin{align} x_1 &\leq 4 + Mz_1 \\ x_2 &\leq 3 + M(1-z_2) \\ x_3 &\leq 4 + M(1-z_3) \\ x_4 &\leq 5 + M(1-z_4) \\ x_4 &\geq 5 - M(1-z_4) \\ z_2 + z_3 + z_4 &\ge z_1 \end{align} The idea is that $$x_1 > 4 \implies z_1$$, and $$z_1 \implies (z_2 \lor z_3 \lor z_4)$$

• Dear @RobPratt, whats happened if we have ($z_2 \oplus z_3 \oplus z_4$) instead of ($z_2 \lor z_3 \lor z_4$)? Commented Jun 1 at 8:32
• @A.Omidi If you want exactly one of the three constraints to hold when $z_1=1$, then you would instead impose $z_1 \le z_2+z_3+z_4 \le 3-2z_1$ and then enforce $z_2\iff x_2\le 3$, $z_3\iff x_3\le 4$, and $z_4\iff x_4=5$. Commented Jun 1 at 14:19
• Dear @RobPratt, is what you mentioned in the first expression linearization of the logical xor as I wrote in the comments? Commented Jun 1 at 19:49
• @A.Omidi Yes, it enforces $z_1=1 \implies z_2+z_3+z_4=1$. Commented Jun 1 at 20:19
• Dear @RobPratt, thanks for the clarification. Commented Jun 2 at 4:35

Trying to be creative, what about:
$$x_1 - 4 \le M(12- x_2-x_3-x_4)$$ and
$$x_2+x_3 \le 7$$

• $x=(3,5,5,5)$ satisfies the OP's requirements (since $3=x_1 < 4$, the other three constraints are not required to hold) but would violate your first constraint unless $M$ were really small, as well as violating your second constraint.
– prubin
Commented Jan 10, 2023 at 19:48