Constraint in Linear Programming

0
votes

I am trying to write a constraint for the problem:

if a=>0, and b=>0, then a=b.

So far, I have written, Let 

u >= a-b
u >= b-a

Now, I need to make sure that u = 0 if both a>0 and b>0, but cannot seem to figure it out.
Can you guys please give me a hint.

2
linear-programminginteger-programming
That's not possible with pure Linear-Programming. If you are building a Mixed-integer model, then look up the term indicator-constraint. (One more remark: the >-operator is not valid in terms of LPs, it's always >=) – sascha
Sorry, my bad it is a mixed-integer model. – novice
Then read this (part 7.1). – sascha
Thanks a ton for your help! – novice
@sascha : Got it finally: Applied the McCormick Envelope after using the information in the link and voila! – novice

2 Answers

0
votes

We can use binary variables to solve the problem. We already have a lower bound for u.

u >= 0

Providing an upper bound in terms of the binary variables x and y, we get

u <= M*(1 - xy)
u <= M*(1-z), where z = xy

where M is some arbitrarily large number(Can set M as sum of absolute values of a and b in certain situations)
xy = 1 corresponds to u =0 and thus a=b.

So, x = 1 should also correspond to a>=0,
and y = 1 should correspond to b>=0
for which we can use: 

x >= 0
x <= Upper bound of a
y >= 0
y <= Upper bound of b

Now, xy =1 to corresponds to ab>=0
Now we use the McCormick Envelope, to convert xy>0 to linear constraints, which is given as
Let Upper bound of x be XU, Upper bound of y be YU. Lower bound of x be XL, Lower bound of y be YL.
We get,

z <= XU*y + YL*x - XU*YL
z <= YU*x + XL*y - YU*XL
z >= XL*y + YL*x - XL*YL
z >= XU*y + YU*x - XU*YU

Lower bounds for x and y is 0, upper bound is 1, this simplifies to 

z <= y
z <= x
z >= 0
z >= x + y - 1

If anyone has another answer please do post, I would be happy to know!.

0
votes

I think you mean:

If a > 0 and b > 0 then a=b

or putting it differently

a=b or a=0 or b=0

Let me try:

enter image description here

I assumed a and b are non-negative variables, however it also works if we allow negative values for a and b.

The question has been edited to:

If a >= 0 and b >= 0 then a=b

This means a and b are free variables and

a=b or a<0 or b<0

Of course the above is easily adapted by adding a small tolerance term to the first two inequalities. However we can also model this more explicitly using a standard variable splitting technique:

enter image description here