I have the following decision variables:
- $x$, which is binary, and
- $a, b, c > 0$, which are continuous.
I would like to express in linear form for a linear programming model the following constraints:
(a) if $x=1$, then $b < a$ AND $a \leq c$ (i.e. $b < a \leq c$),
(b) else if $x=0$, then $a \leq b$ XOR $c < a$.
Note: It always holds that $b < c$ (I do not know if this can simplify things).
I came up with the following linear constraints, using the big-M method and a small tolerance constant $\epsilon$:
(1) $b + \epsilon \leq a + M(1-x)$
(2) $a \leq c + M(1-x)$
(3) $a \leq b +Mx$
(4) $c + \epsilon \leq a +Mx$
However, (3) and (4) do not correctly convey the meaning of constraint in (b), since when $x=0$, then $a \leq b$ and $c < a$, which is impossible. Is there an elegant way to correct this, preferably without introducing another binary variable? Maybe the fact that $b < c$ could help in some way?
Your (1) and (2) are correct. To enforce $$x=0 \implies (\text{$a \le b$ XOR $c < a$}),$$ first rewrite as $$x=1 \lor (a \le b \land c \ge a) \lor (a > b \land c < a),$$ and then introduce binary variables $y$ and $z$, together with linear constraints \begin{align} x + y + z &\ge 1 \tag5\label5 \\ a-b &\le M(1-y) \tag6\label6 \\ a-c &\le M(1-y) \tag7\label7 \\ b-a+\epsilon &\le M(1-z) \tag8\label8 \\ c-a+\epsilon &\le M(1-z) \tag9\label9 \end{align} If you also know that $b<c$, you can omit \eqref{7} and \eqref{8}, which are then dominated by \eqref{6} and \eqref{9}, respectively.
You cannot avoid introducing at least one binary variable because the feasible region for $x=0$ is not convex. For example, $(a,b,c)=(0,1,2)$ and $(a,b,c)=(3,1,2)$ are both feasible, but their average is not.
By request, here is an alternative formulation with only one additional binary variable $y$. The idea is to enforce $$(x=0 \land y=1) \implies a \le b$$ and $$(x=0 \land y=0) \implies c < a,$$ which you can do with linear constraints \begin{align} a-b &\le M(x+1-y)\tag{6’}\label{6p} \\ c-a+\epsilon &\le M(x+y) \tag{9’}\label{9p} \end{align}