Search code examples
linear-programminginteger-programming

Is there a way to set a decision variable to true iff a variable is in a range in an integer linear program?


I have an integer-valued bounded variable, call it X. (Somewhere around 0<=X<=100)

I want to have a binary variable, call it Y, such that Y=1 if X >= A and X <= B, otherwise Y=0.

The best I've come up with thus far is the following (where T<x> are introduced binary variables, and M is a large number)

(minimize Y)
(X - A) <= M*Ta
(B - X) <= M*Tb
Y <= Ta
Y <= Tb
Y >= Ta + Tb - 1

(In other words, introducing two binary variables that are true if the variable satisfies the lower and upper bounds of the range, respectively, and setting the result to the binary multiplication of those variables)

This... Works, sort of, but has a couple major flaws. In particular, it's not rigorously defined - Y can be 1 even if X is outside the range.

So: is there a better way to do this? In particular: is there a way to rigorously define it, or if not, a way to at least prevent false positives?


Edit: to clarify: A and B are variables, not parameters.


Solution

  • Rewriting loannis's answer in a linear form by expanding out multiplication of binary variables with a continuous variable:

    1. Tc <= M*Y
    2. Tc <= A
    3. Tc >= A - M*(1-Y)
    4. Tc >= 0
    5. Tc <= X
    6. Td <= M*Y
    7. Td <= B
    8. Td >= B - M*(1-Y)
    9. Td >= 0
    10. X <= Td + 100*(1-Y)
    11. (X - A + 1) <= M * Ta
    12. (B - X + 1) <= M * Tb
    13. Y >= Ta + Tb - 1

    This seems to work, although I have not yet had the chance to expand it out to prove it. Also, some of these constraints may be unnecessary; I have not checked.


    The expansion I did was according to the following rule:

    If b is a binary variable, and c is a continuous one, and 0 <= c <= M, then y=b*c is equivalent to the following:

    1. y <= M*b
    2. y <= c
    3. y >= c - M*(1 - b)
    4. y >= 0