1
$\begingroup$

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.

$\endgroup$

migrated from stackoverflow.com May 20 at 2:05

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ All x and y variables are continuous, correct? $\endgroup$ – LarrySnyder610 May 16 at 17:11
  • $\begingroup$ 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? $\endgroup$ – LarrySnyder610 May 16 at 19:55
  • $\begingroup$ I am not sure why this got migrated from SO ... programs about mathematical optimization are in scope there. Oh well. $\endgroup$ – LarrySnyder610 May 20 at 13:15
1
$\begingroup$

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:

  1. 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.

$\endgroup$
  • $\begingroup$ Thank you for your detailed and comprehensive answer, I think I got it know. $\endgroup$ – Claudi May 20 at 8:03
  • $\begingroup$ 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 ? $\endgroup$ – Claudi May 20 at 11:11
  • $\begingroup$ 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. $\endgroup$ – LarrySnyder610 May 20 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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