3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I don't understand what you mean by 0 < b - T1 && b < T2 to 0 < T2 - b. $\endgroup$
    – D.W.
    Mar 5, 2017 at 12:05

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thank you very much for your response. But I have a question to your $t$ variable. If I understand your solution correct then if $b$ is NOT between $L$ and $U$ (e.g.: $b=0$, $L=1$ and $U=100$) then $t$ can only be 0. But if $b$ is between $L$ and $U$ (e.g. $b= 50$, $L=1$ and $U=100$) then $t$ can be 0 or 1. Is this correct? $\endgroup$
    – piwa
    Mar 5, 2017 at 17:20
  • $\begingroup$ @piwa, you're absolutely right. Sorry about that. See the edited answer -- does it work now? $\endgroup$
    – D.W.
    Mar 5, 2017 at 19:29
  • $\begingroup$ I tested the equations and they worked perfect! Thank you so much for your support and also the explanations of the formulas! $\endgroup$
    – piwa
    Mar 6, 2017 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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