If-Then with disjunctions (OR) in Integer Linear Programming (ILP)

Question

I have the following constraints I'm trying to model in Linear Integer Programming. I will try out diverse solvers for this later, but first I need to model the problem.

Given the integer variables: x1, x2, x3, x4, y1, y2, y3, y4, I have the following constraints:

IF (y1 ≤ y3 ≤ y2 OR y1 ≤ y4 ≤ y2)
THEN (x1 ≥ x4 OR x2 ≥ x3)

Additionally for all of these variables I have upper and lower bounds.

I think I have to use the "big M" technique, but I'm not sure how to handle the logical OR in the IF condition and in the THEN condition and how to built up one complete model.

Does anyone of you know how to resolve this? Many thanks in advance.

• LarrySnyder610: All x and y variables are continuous, correct?
• LarrySnyder610: Oh wait, you said they are integer. You also said they have upper and lower bounds. So they are general integer (0, 1, 2, 3, ...), not binary?
• LarrySnyder610: I am not sure why this got migrated from SO ... programs about mathematical optimization are in scope there. Oh well.
• gnasher729: Wondering: A simple method for integer programming problems is to solve without the integer condition, then add one of two conditions. For example "x17 must be an integer", you find x17 = 123.17 is optimal, you solve with an added condition either x ≤ 123 or x ≥ 124. Could you do the same with these constraints? Let the "if" constraints be i1 and i2, and the "then" constraints t1 and t2, then you duplicate the problem with constraints i1 and t1, i1 and t2, i2 and t1, i2 and t2, and "not(i1 or i2)", and take the best of the five solutions.
• gnasher729: @LarrySnyder610, the x and y are integers, otherwise the condition that the IF is false would be hard to check.

Answer 1

You have the following condition:

IF ((y1 <= y3) AND (y3 <= y2)) OR ((y1 <= y4) AND (y4 <= y2))
THEN (x1 >= x4) OR (x2 >= x3)

For each logical term, you'll need a new binary variable. At each "level" of the logical statements, you'll use the binary variables from the previous level. So:

1. z1 = 1 iff y1 <= y3
2. z2 = 1 iff y3 <= y2
3. z3 = 1 iff z1 = 1 AND z2 = 1
4. z4 = 1 iff y1 <= y4
5. z5 = 1 iff y4 <= y2
6. z6 = 1 iff z3 = 1 AND z4 = 1
7. z7 = 1 iff x1 >= x4
8. z8 = 1 iff x2 >= x3

Then you'll have a constraint that says:

9. if z3 = 1 OR z6 = 1 then z7 = 1 OR z8 = 1

Let's take one type of constraint at a time.

z1 = 1 iff y1 <= y3:

y3 - y1 + 1 <= Mz1
y1 - y3 <= M(1 - z1)

The logic is: If y3 > y1 - 1, i.e., y3 >= y1, then z1 must equal 1. If y1 > y3 + 1, i.e., y1 > y3, then z1 must equal 0.

Note that if the y variables are continuous, not integer, then replace the 1s with some small number. This isn't ideal from a numerical perspective though.

Constraints 2, 4, 5, 7, and 8 are similar.

z3 = 1 iff z1 = 1 AND z2 = 1:

z1 + z2 <= 2z3
z3 <= z1
z3 <= z2

The logic is: If z1 and z2 both equal 1, then z3 must equal 1. If either of them equals 0, then z3 must equal 0.

Constraint 6 is similar.

if z3 = 1 OR z6 = 1 then z7 = 1 OR z8 = 1:

z3 + z6 <= 2(z7 + z8)

The logic is: If z3 = 1 or z6 = 1, then z7 or z8 must equal 1.

• Claudi: Thank you for your detailed and comprehensive answer, I think I got it know.
• Claudi: Shouldn't it rather be: y3 - y1 + 1 <= Mz1, y1 - y3 - 1 < M(1 - z1) --> with a < instead of a <= in the second line, for the case when y1 > y3 and y1 - y3 = 1 ?
• LarrySnyder610: You're right that the constraint was incorrect, but you can't use strict inequalities in ILPs; so the correct constraint should be y1 - y3 <= M(1 - z1); I have edited it above.