"Greater than AND smaller than" condition in integer linear program with a binary variable

Question

I found this related question, but that's not quite it

Is it possible to model this with integer programming:

$$A = \begin{cases} 1 & \text{if } B \geq C \geq D \\ 0 & \text{otherwise}\end{cases}$$

where $A \in \{0,1\}$, $B, D \in \mathbb R$ and $C \in \mathbb N$. We have upper and lower bounds on $B$, $C$ and $D$.

• MrHug: Since you have upper bounds on B,C, and D, can you not use the technique you have linked twice? $A_1 = 1$ iff $B \geq C,ドル and $A_2 = 1$ iff $C \geq D$. Then $A = A_1\cdot A_2$.
• DaWit: I can only have linear constraints, therefore it is not possible to calculate $A = A_1 * A_2$
• MrHug: Then how about $A_1 + A_2 \geq 2$?
• user1543037: You can implement any comparisons you like with big M trick. blog.adamfurmanek.pl/2015/09/12/ilp-part-4

Answer 1

Thanks MrHug, I should have thought of this myself after your first hint.

after using the solution from here twice with the resulting binaries $A_1$ and $A_2$ we can form another problem: $$A = \begin{cases} 1 & \text{if } A_1+A_2 \geq 2 \\ 0 & \text{otherwise}\end{cases}$$

This one can be solved with a little hint from there:

$$A_1 + A_2 \geq 2 - M * (1-A) \\ 2 - \epsilon \geq A_1 + A_2 - M * A$$

where $M$ is a big value and $\epsilon$ is a very small value (above 0, below 1).

It's a bit unfortunate that so many variables are needed as $A$, $A_1$ and $A_2$ are cubic in my case. But I'm glad about this solution.