[Help-glpk] Linearising LP constraints and SOS2

[Paolo Rossi]

Hi everyone,

 

 

I have two questions:

1)      How can I linearise a constraint of the type –

x1 <= x2*bx1

where bx1 is binary and x2 is a positive real which arises as a result of a linearisation through using SOS2 and  x1 is a positive real decision variable

 2)       It would be great if someone knowledgeable could confirm that what I am doing below is correct. Sorry for this and I am really grateful to anybody going through the lengthy note below but I am an ecometrician who didn’t even know what Linear Programming meant until a month ago, not mention SOS et al.

 

I will really appreciate any help anybody can provide. I have seen this tyope of analysis doen in other cademic papers so it can be done although I don't know how

 

Many Thankls in adavnce,

Paolo

 

 

 

 

 

I am modelling a storage facility and need to maximise value from it. The decision maker can change the flows into and from the facility to get as much money as he can

We have flows in and flows out, assessed at a different price (allowing for different price is particularly important) and cost. That suggest the use of two variables, one for inflows, the other for outflows. The obj function for 3 time-period problem would look like this:

 

Max    -IN1 x p1in   +   OUT1 x p1out  – c1in x IN1 – c1out x OUT1   

        +(-IN2 x p2in   +   OUT2 x p2out  – c2in x IN2 – c2out x OUT2 )   

       + (-IN3 x p3in   +   OUT3 x p3out  – c3in x IN3 – c3out x OUT3 )

 

IN and OUT variables are mutually exclusive, i.e. either you put things in or take things out, pxin is the price to buy gas at period x, pxout the price to sell gas. A number of people suggested modelling them like

 

IN1 <= MAX_IN1*BIN1

OUT1 <= MAX_OUT1*BOUT1

BIN1 + BOUT1 = 1  (where BIN1 and BOUT1 are binaries)

 

The 1 in the variables refers to time period 1. Similar constraints can be used for other time periods. I also reckon that use could use as SOS1, although for the moment being I am happy with the formulation above.

 

The problem is that MAXIN1 and MAXOUT1 are not constant but vary according to how much stuff I have got in my storage facility, i.e. inventory, in a non-linear way. A number of you suggested modelling this based on SOS2. I had a look at this very helpful note  http://lists.gnu.org/archive/html/help-glpk/2007-06/msg00005.html

 

Suppose I want to linearise the relationship according to three knots which don’t change across time. In each time period x, my binaries for the inventory will need to satisfy

 

BINV1,x + BINV2,x = 1 (z variable in http://lists.gnu.org/archive/html/help-glpk/2007-06/msg00005.html)

 

For each time period I have

1_-    1)    one independent variable INV (x variable in http://lists.gnu.org/archive/html/help-glpk/2007-06/msg00005.html) expressed as function of the three knots (indicated with a  name ending in k1, k2, k3). Formulation below is for time period 3.

 

INV3 = INVk1 * BINV1,3 + (INVk2 - INVk1) * S1,3 +

            INVk2 * BINV2,3 + (INVk3 - INVk2) * S2,3

 

In my case INVx is the sum of IN and OUT up to that point in time. In case of period 3

 

 

INV3  = OUT1 - IN1 + OUT2 – IN2 + OUT3 – IN3

 

 

So I believe that the constraint above would become

 

OUT1 - IN1 + OUT2 – IN2 + OUT3 – IN3    =   INVk1 * BINV1,3 + (INVk2 - INVk1) * S1,3  +   INVk2 * BINV2,2 + (INVk3 - INVk2) * S2,3

 

This essentially would link my decision variable in the lhs to the linearisation of the x variable in the rhs. To me it makes sense.

 

-          2)   two dependent variables MAX_OUT  and MAX_IN (y variable in http://lists.gnu.org/archive/html/help-glpk/2007-06/msg00005.html) expressed as function of the three knots (as above indicated with a  name ending in k1, k2, k3). As mentioned the three knots are constant across time. In the case of MAX_OUT, once gain for period 3

 

MAX_OUT3 = MAX_OUTk1 * BINV1,3 + (MAX_OUTk2 - MAX_OUTk1) * S1,3 +

                      MAX_OUTk2 * BINV2,3  + (MAX_OUTk3 - MAX_OUTk2) * S2,3

 

Similarly for MAX_IN.

 

There are other constraints which seem straightforward, once again expressed for period 3

 

0 <= S1,3 <= BINV1,3

0 <= S2,3 <= BINV2,3

 

 

Question 1: Is all of this correct? Have I misunderstood/ neglected anything?

 

 

Question2: assuming that everything is fine (and it may be  a big if!) I believe I ended up with a non-linear constraints again!

 

IN3 <= MAX_IN3 * BIN3   as both  MAX_In3 and BIN3 are variable form time period 3

 

Sorry but at this point I feel I have hit a bit of a dead-end, as far my skills are concerned, and would appreciate any help, either in the reformulation of the problem above to avoid the non-linearity or in any way to tackle it

 

 

Many Thanks

 

Paolo