Express a "complex" IF-Statement to Linear Programming

Question

In our current project we need to model the following if-statement in linear programming:

If T1 < b < T2 then z = s else z = 0

where T1 and T2 are two integer values (e.g. T1 = 10 and T2 = 100) and s is also an integer value (e.g. 5).

We already know how to model a simpler if-statement with for example A > 0 but we can not figure out how to model an if-statement with a condition t1 < b < t2.

Can someone help us?

---

Here is a little more detailed explanation of the problem:

In our problem we have several different ranges, each range with a lower and an upper bound, and for each of these steps we have to multiply another value to a variable (lets call this variable k and the result of this multiplication z). For example we have the following range and if-statements:

Ranges:
0   - 10 : 0
11  - 100: 9
101 - 200: 8.5
201 - 300: 8

IF-Statements
if 0   < b < 10  then z = k * 0
if 11  < b < 100 then z = k * 9
if 101 < b < 200 then z = k * 8.5
if 201 < b < 300 then z = k * 8

The lower and the upper bounds as well as the multiplication values are constants and known upfront. The rest (i.e. b, z, k) are integer variables for which we don't know the exact upper bound (lower bound is 0), but we know that they will not get too big. So, we are able to define M values for the M technique.

We already figured out how to do an if-statement like the following (T1 and T2 are the thresholds of the ranges from above, e.g. T1=0 & T2=10):

if T1 < b then z = k * something

and

if b < T2 then z = k * something

For this we transform T1 < b to 0 < b - T1 and b < T2 to 0 < T2 - b and then we use the way described here.

But we are stuck at how we can do the:

0 < b - T1 && b < T2 to 0 < T2 - b

The whole problem is a mixed integer linear programming problem, because we have also boolean decision variables and integer values like for example b.

Answer 1

You can solve this by introducing some temporary variables ($t,u,v$) and applying the big-M method.

For each expression L <= b <= U, we'll introduce 0-or-1 variables $t,u,v$, with the intent that $u=1$ if and only if $L \le b$ holds, $v=1$ if and only if $b \le U$ holds, and $t=1$ if and only if $L \le b \le U$ holds. We'll enforce this with the inequalities

$$L \le b + M(1-u), L > b - Mu, b \le U + M(1-v), b > U - Mv, 0 \le u+v - 2t \le 1,$$

where $M$ is a sufficiently large constant (you can take it to be at least the largest possible value of $b$, and at least $L$ and at least $U$). How does this work? The first two inequalities define $u$ so that $u=1 \Leftrightarrow (L \le b)$ using the technique from Boolean variable true iff equation is satisfied in ILP. The next two inequalities define $v$, similarly. The last inequality ensures that $t$ is the logical-AND of $u$ and $v$, using the technique from https://cs.stackexchange.com/a/43884/755.

Now, we'll enforce the constraint if t=1 then z = k*c for some constant c. We can enforce this using the inequalities

$$ck - M(1-t) \le z \le ck + M(1-t)$$

where $M$ is a sufficiently large constant (in particular, it needs to be at least $c$ times the largest possible value of $k$, and at least the largest possible value of $z$). Why does this do what we want? The argument is similar. If $t=1$, then the inequality is equivalent to $ck \le z \le ck$, which implies $ck=z$; if $t=0$, the inequality is equivalent to $ck-M \le z \le ck+M$, which imposes no restrictions on $z$.

See Express boolean logic operations in zero-one integer linear programming (ILP) for more techniques for handling other sorts of inequalities.