Thread: NonNegative Bounds in Linear Programming problem

Hello everyone,

I am not really sure where to post about Linear Programming. I am trying to program an LP problem using PuLP, as I am very familiar with Python.

I faced the issue of having decision variables which can take negative value,
i.e. they are bound between -k1 and K2. I have seen the advice of introducing
a new variable into the problem, so the original cosntraint is shifted in
order for the new variable to be non-negative only. I'd guess that the
substitution has to be carried out throughout the problem, i.e anywhere the
original variable appears (including objective function) but I would be
grateful if someone could confirm this.

Below I have written a simple problem and the reformulated proble.

I would like to know:
- is what I am doing correct?
- is there a better approach to this problem?

Many Thanks in advance

Paolo

Original problem,

Max -p1x1 - p2x2
x1 >= -10
x1 <= 20
x2 >= -30
x2 <= 40
Inv + x1 >= 0
Inv + x1 + x2 >= 0
Inv + x1 <= TC
Inv + x1 + x2 <= TC

with TC and Inv being positive constants

Reformulated Problem:

Given L1 = -10, y1 = x1 - L1 x1 = y1 + L1
x1 >= -10 y1 + L1 >= -10 y1 >= 0 (change var and subtract L1)
x1 <= 20 y1 + L1 <= 20 y1 <= 20 + 10 (change var and subtract L1)
Inv + x1 >= 0 Inv + y1 + L1 >= 0 Inv + y1 >= 10 (change var and
subtract L1)
Inv + x1 <= TC Inv + y1 + L1 <= TC Inv + y1 <= TC + 10 (change var and
subtract L1)

Given L2 = -30, y2 = x2 - L2 x2 = y2+ L2
x2 >= -30 y2 + L2 >= -30 y2 >= 0 (change var and subtract L2)
x2 <= 40 y1 + L2 <= 40 y1 <= 40 + 30 (change var and subtract L2)

Given L1 = -10 and L2 = -30
Inv + x1 + x2 >= 0 Inv + y1 + L1 + y2 + L2

>= 0
Inv + y1 + y2 >= -(L1 + L2) Inv + y1 + y2 >= 40
Inv + x1 + x2 <= TC Inv + y1 + L1 + y2 + L2
<= TC
Inv + y1 + y2 >= -(L1+L2) + TC Inv + y1 + y2 <= 40 + TC

Finally, Max -p1x1 - p2x2 Max -p1(y1+L1) - p2(y2+L2)

Originally Posted by LutherBlissett

Hello everyone,

I am not really sure where to post about Linear Programming. I am trying to program an LP problem using PuLP, as I am very familiar with Python.

I faced the issue of having decision variables which can take negative value,
i.e. they are bound between -k1 and K2. I have seen the advice of introducing
a new variable into the problem, so the original cosntraint is shifted in
order for the new variable to be non-negative only. I'd guess that the
substitution has to be carried out throughout the problem, i.e anywhere the
original variable appears (including objective function) but I would be
grateful if someone could confirm this.

Below I have written a simple problem and the reformulated proble.

I would like to know:
- is what I am doing correct?
- is there a better approach to this problem?

Many Thanks in advance

Paolo

Original problem,

Max -p1x1 - p2x2
x1 >= -10
x1 <= 20
x2 >= -30
x2 <= 40
Inv + x1 >= 0
Inv + x1 + x2 >= 0
Inv + x1 <= TC
Inv + x1 + x2 <= TC

with TC and Inv being positive constants

Put:

y1=x1+10
y2=x2+30

now rewrite the problem replacing x1 by (y1-10) and x2 by (y2-30) throughout.

CB