CODEWITHSUNDEEP
pythonmathematical-optimizationlinear-programmingpulpmixed-integer-programming
wu2g
wu2g

Reputation: 23

Mixed Integer Linear Programming to And/Or Constraints

I'm looking to satisfy a set of constraints using PuLP and I'm not exactly sure how to set up the variables to do so.

For example, how would I set up variables for the following constraint:

((x_1 < x_2) AND (x_1 < x_3)) OR ((x_1 > x_2) AND (x_1 > x_3))

A variable x_1 is either less or greater than both, x_2 and x_3.

Any help would be appreciated. Thanks!

Upvotes: 1

Views: 2265

Answers (2)

Erwin Kalvelagen
Erwin Kalvelagen

Reputation: 16724

The constraint 

 ((x1 <= x2) AND (x1 <= x3)) OR ((x1 >= x2) AND (x1 >= x3))

can be formulated with just one extra binary variable:

 x1 <= x2 + delta*M
 x1 <= x3 + delta*M
 x1 >= x2 - (1-delta)*M
 x1 >= x3 - (1-delta)*M
 delta in {0,1}

Most advanced solvers have indicator constraints, allowing us to write this without big-M's:

 delta = 0 -> x1 <= x2
 delta = 0 -> x1 <= x3
 delta = 1 -> x1 >= x2
 delta = 1 -> x1 >= x3
 delta in {0,1}

Upvotes: 4

sascha
sascha

Reputation: 33532

First a remark: there is no < operator in Linear-programming. There is only <=. This means: if you want strict inequalities, you will need to add some small constant epsilon!

Now let's assume your task looks like: ((x1<=x2) && (x1<=x3)) || ((x1>x2) && (x1>x3)) (> is the logical negation of <= here which will make this work despite the above).

Let's call (x1>x2) = z1 and (x1>x3) = z2. Then this can be simplified to: (!z1 || z2) && (z1 || !z2) (i used the names A and B in the link).

  • Introduce two new binary-variables z1, z2
  • Use a bigM-based formulation like this page 4 to create an indicator for your relation:
    • x1 <= x2 + M * z1 where M is a big constant; (z1=0) -> x1 <= x2
    • x1 <= x3 + M * z2 where M is another big constant; (z2=0) -> x1 <= x3
  • Now we need the above: (!z1 || z2) && (z1 || !z2)
    • This is basically a !(z1 xor z2), here 1-(z1 xor z2) (look at the truth-table in the "simplified" link above ) and you can follow a very active Stackoverflow-user here to linearize the xor:
      • Introduce another binary-variable z3
      • Add linear constraints
        • z3 <= (1-z1) + (1-z2)
        • z3 >= (1-z1) - (1-z2)
        • z3 >= (1-z2) - (1-z1)
        • z3 <= 2 - (1-z1) - (1-z2)
    • z3 is now z1 xor z2
    • Add constraint: z3 == 0

(There might be some error in the above, but the concept should be ok. With code at hands you should be able to make it work)

Upvotes: 3

Related Questions