Mixed Integer Linear Programming to And/Or Constraints

Question

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!

What have you tried so far? Please post your code (see How to create a Minimal, Complete, and Verifiable example) including error messages, you get. — Mr. T
– Mr. T, Commented Nov 25, 2017 at 22:44

Erwin Kalvelagen · Accepted Answer · 2017-11-26 04:41:57Z

4

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}

edited Nov 26, 2017 at 4:41

answered Nov 26, 2017 at 4:36

Erwin Kalvelagen

16.9k3 gold badges17 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

wu2g Over a year ago

I had to read through and implement the other answer first before I could understand this simplified answer. This is clean and helps a lot. Thank you! Even though LP doesn't generally handle inequalities I'm guessing this can be correct with some small constant value c? For example: x1 + c<= x2 + delta M; x1 + c<= x3 + delta M; x1 >= c + x2 - (1-delta)M; x1 >= c + x3 - (1-delta)M; delta in {0,1}

sascha · Accepted Answer · 2017-11-25 23:26:19Z

3

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)

edited Nov 25, 2017 at 23:26

answered Nov 25, 2017 at 22:55

sascha

33.7k6 gold badges80 silver badges117 bronze badges

1 Comment

wu2g Over a year ago

This is awesome! So we know that z3 = !(z1 XOR z2). What's the difference (1) introducing z3 and the additional constraints to linearize XOR, and (2) just adding the constraint that z1 == z2?

Collectives™ on Stack Overflow

Mixed Integer Linear Programming to And/Or Constraints

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related