CODEWITHSUNDEEP
pythonconstraintslinear-programmingpulp
SashaZd
SashaZd

Reputation: 3319

If-Then-ElseIf-Then In Mixed Integer Linear Programming

I'm trying to frame If-Then-Else-If... conditions in Python's PuLP.

I've looked at If-Then and If-Then-Else in MIP. However, I'm trying to understand how to propagate the choices further down to the next set of constraints and how to handle more than 2 decision branches.

To explain, consider the conditional constraints shown in the image shown here:

x and y are my decision variables. Basically, this reads as: 

if x=0: C2>0 
elif x=1: C10>0
elif x=2: C3>0

if x=0 and y=0: 
    C4>0; 
    C8>0; 
    C10>0
elif x=0 and y=1: 
    C5>0; 
    C8>0; 
    C10>0
elif x=2 and y=0: 
    C6>0; 
    C9>0; 
    C10>0
elif x=2 and y=1: 
    C7>0; 
    C9>0; 
    C10>0

I know how to use the "Big M" technique for simple if-then-else situations. So for instance, if the problem was: 

Problem: 
   if (x = 1) then (A < 0) else (B < 0)
Solution: 
   problem += A < M1*(1-x)
   problem += B < M2*x

What I don't understand is, how to change this for:

  1. If there's more than 2 branches, so it's no longer a multiplication with x and (1-x).
  2. If there are subsequent branches below the original decision, with more decisions that all depend on values from above.

Upvotes: 3

Views: 3300

Answers (1)

LarrySnyder610
LarrySnyder610

Reputation: 2397

There are really three steps involved here:

FIRST:

Reformulate the x variables so they are binary instead of in {0,1,2}. (Strictly speaking, this isn't necessary, but I think it makes the solution cleaner and easier to generalize.)

So, introduce three new binary variables x0, x1, x2 and constrain them as follows:

x0 >= 1 - x
x0 <= 1 - 0.5x

x2 >= x - 1
x2 <= 0.5 x

x1 = x - 2x2

So: If x = 0, then the first two constraints require x0 = 1, the second two require x2 = 0 and the last requires x1 = 0. And similarly if x = 1 or x = 2. (You should double-check my logic.)

Your model will include your original x variables plus the new binary variables.

SECOND:

Create a new binary decision variable called, say w_ijkl, which equals 1 if x0 = i, x1 = j, x2 = k, and y = l, for i, j, k, l in {0,1}. Enforce this definition through the following constraints:

w_ijkl >= i*x0 + (1-i)*(1-x0) + j*x1 + (1-j)*(1-x1) +
          k*x2 + (1-k)*(1-x2) + l*y + (1-l)*(1-y) - 3
w_ijkl <= 0.25 * [i*x0 + (1-i)*(1-x0) + j*x1 + (1-j)*(1-x1) +
                  k*x2 + (1-k)*(1-x2) + l*y + (1-l)*(1-y)]

The first constraint says that if all four variables equal their targets (i, j, etc.) then w_ijkl must equal 1, and otherwise it can equal 0. The second constraint says that if all four equal their targets, then w_ijkl may equal 1, otherwise it must equal 0.

So, for example, w_0110 gets these constraints:

w_0110 >= 1-x0 + x1 + x2 + (1-y) - 3
w_0110 <= 0.25 * [1-x0 + x1 + x2 + (1-y)]

THIRD:

Use big-Ms as desired to turn constraints on and off. So, for example, to require C6 >= 0 if x=2 and y=0, use:

C6 >= M * (w_0010 - 1)

(By the way, in general you can't use strict inequality constraints in a MIP -- you need greater-than-or-equal or less-than-or-equal constraints.)

Upvotes: 4

Related Questions