I have the following constraint I'm trying to model in Mixed Integer Programming with Python's PuLP module:
Given linear programming variables: x1,x2,y1,y2 where x1, x2, y1, y2 eventually solve to integer values
if (x1<=y2 and y1<=x2) then a=1 else b=0
I'm not sure how to handle the Logical AND in the IF condition. If the AND wasn't present I know I have to use the Big-M notation.
First of all, this is not Linear Programming but rather Mixed Integer Programming, since an AND constraint is not linear and neither is an implication. I also assumed that both a and b are binary variables. You can then reformulated your problem as follows:
x1 > y2 + m*z1
y1 > x2 + m*z2
a + 1 >= z1 + z2
a <= z1
a <= z2
a - b >= 0
Here, m needs to be some (negative) lower bound, i.e. m < x1-y2 and m < y1-x2. Both z1 and z2 are binary variables. To get around the < inequality you might want to add some small epsilon to the first two constraints:
x1 >= y2 + (m-eps)*z1 + eps
y1 >= x2 + (m-eps)*z2 + eps
if a=1 then b=0, and if a=0 then b=1. I want b=0 only if we're in the else condition. And a=1 only if we're in the if-then condition. In other cases, all values are allowed. Would a-b>=0 as the last constraint work instead of b=1-a?
(1-z) extra condition on each of the first two conditions to make sure it works. I've still upvoted your answer because I used the z1, z2 concept in addition to the new constraints to allow for the AND condition.I found a formulation that works the IF-THEN-ELSE irrespective of the problem given.
In the later part of the answer, I'm using the z1, z2 variables as described in @mattmilten's answer to handle the AND condition in the if statement
Assume the problem is the following specification:
if α > 0 then β >= 0 else γ >= 0
then,
α - z * U_α <= 0 # (1)
α - (1 - z)(L_α - 1) > 0 # (2)
β - (1 - z)L_β >= 0 # (3)
γ - z * L_γ >= 0 # (4)
where,
L_α, L_β, L_γ # are constant lower bounds on α, β, γ (or values smaller than the lowest value they can take)
U_α # is a constant lower bounds on α
z # is a LP variable that can take values {0,1}
Then equations (1) and (4) are redundant, and the then condition or (3) is enforced
Then equations (2), and (3) are redundant, and the else condition or (4) is enforced
We run this twice, the first time with α=α1 and the second with α=α2.
where,
α1 = y2 - x1
z1 = decision variable for α1 with values {0,1}
α2 = y1 - x2
z2 = decision variable for α2 with values {0,1}
β # Currently unnecessary for my particular question.
γ # Currently unnecessary for my particular question.
So our constraints become:
α1 - z1 * U_α1 <= 0 # (1-1)
α1 - (1 - z1)(L_α1 - 1) > 0 # (1-2)
α2 - z2 * U_α2 <= 0 # (2-1)
α2 - (1 - z2)(L_α2 - 1) > 0 # (2-2)
If z1=1, then the first part of our if-condition is true. ie. x1<=y2
If z2=1, then the second part of our if-condition is true. ie. x2<=y1
Now, using @mattmilten's formulation for ensuring both conditions:
a + 1 >= z1 + z2
a <= z1
a <= z2
a - b >= 0
This ensures that both z1 and z2 have to be >= 1 in order for a=1. If a=1 then b can be either b=1 or b=0 without violating the last condition.
If a=0 then we're in the else condition, and therefore b has to be 0.