Re: [Help-glpk] LP problem with variable coeffcients (parametric LPsimplex)

[Paolo Rossi]

Jeff,

 

With your help and some googling I am now at the next step. I hope so, at least!

 

Suppose that my cost function depends on a SOS with 4 variables, i.e. 4 regions where I decide to linearise my cost function. When I say cost function I mean a function describing total cost of production if production falls into that region, not unitary cost of production as I meant in my original post.

 

I understand I need 4 mutually exclusive binary variables, say INVi (inventory)

INV1 + INV2 + INV3 + INV4 = 1.

 

I have been thinking how to model the relationship between the value of the variable switching the binary INV on and off and the threshold values at which the binaries INV get switched on/off. Let’s call these thresholds T0, T1, T2, T3 and T4 so that when the switching variable x is between T0 and T1 INV1 gets switched on.

 

if x >=T0 and if x < T1, INV1 is on, if T1 <= x < T2, INV2 etc.

 

My constraints would look like

x >= T0 x INV1, x <= T1*INV1

x >= T1 x INV2,  x <= T2 x INV2

…

x >= T3 x INV4,  x <= T4 x INV4

 

Do they make sense?

I actually saw on the net that this can be simplified to

T1* INV1 + T2* INV2+ T3* INV3 + T4 * INV4– x = 0 with x > 0, X being the switching variable

 

but it would be nice to know if my reasoning makes sense.

 

The cost function which goes into the objective function is

becomes lc(x1) * INV1 + lc(x2) * INV2 + lc(x3) * INV3 + lc(x4) * INV4. So, being pedant, the cost function is actually not linearised but approximated by a step function. Is this true?

 

So in terms of the objective function, max total profits = max [ total revenues - total costs] = max [total revenues - lc(x1) * INV1 + lc(x2) * INV2 + lc(x3) * INV3 + lc(x4) * INV4 ].

 

If I wanted to use cost per unit of production, rather than  total cost, I would need to multiply an _expression_ similar to lc(x1) * INV1 + lc(x2) * INV2 + lc(x3) * INV3 + lc(x4) * INV4 (at least in spirit) by the variable x. That would make my problem non-linear. Is this the reason why it is better to model total costs?

  

Finally, this works for one time-period only, so if I have N time periods, I need N sets of mutually exclusive variables so that in each time period ith only one varibale in the ith set is on. My cost function becomes Sum with i from 1 to N (lc(x1) * INVi1 + lc(xi2) * INVi2 + lc(xi3) * INVi3 + lc(xi4) * INVi4). I am assuming the thresholds constants across time periods, which suits me fine.

Is this correct?

 

Thanks a lot for your help. I am exhausted. I cannot wait to start analysing data instead of doing this type of thinking!

 

Thanks again, 

Paolo

On 4 April 2011 20:15, Kelly, Jeff (ON0F) <address@hidden> wrote:

Paolo;

 

That’s ok, I’m a chemical engineer.

 

Unless you want to write your own MISLP you will have to linearize your cost profiles and then have the binaries select what region or segment the costs should be in.  It is actually a relatively easy thing to do.

 

Jeff

 

From: Paolo Rossi [mailto:address@hidden]
Sent: Monday, April 04, 2011 3:10 PM
To: Kelly, Jeff (ON0F)
Cc: address@hidden
Subject: Re: [Help-glpk] LP problem with variable coeffcients (parametric LPsimplex)

 

Hi Jeff,

 

thanks for that. I had figured it out in the meantime (while cradling my son to sleep!) that the first one could be solved by something like

 

INJi <= MaxInj * BInj

Withi <= MaxWith * BWith

BInj + BWith = 1

 

which is I think exactly what you mention. So thank you very much  for your reply, as I was wondering if my reasoning was making sense! At the very beginning I thought I'd need to introduce BInj*INJi in the objective function - that is why I stopped due to the introduction of non-linearity in the objective function.

 

I get the hint from your remark on my second question but I really have to think about how to implement it. Sorry my background is not in operations Research..

 

Paolo 

 

 

On 4 April 2011 19:23, Kelly, Jeff (ON0F) <address@hidden> wrote:

Paolo;

 

Your first issue of INJi * WITHi = 0 complementarity is easily modeled by adding two binary variables for each quantity i.e., yINJi and yWITHi then you need three constraints:

1.       INJi <= uINJi * yINJi

2.       WITHi <= uWITHi * yWITHi

3.       yINHi + yWITHi = 1 or <= 1

4.       yINJi, yWITHi are binary

The first two constraints are semi-continuous and third is a SOS1/GUB where the “u” prefix is the upper bound on the quantities.  A lower bound is an exercise for you.

 

Your second issue requires piecewise linear approximation of the cost curves due to most likely economizes/diseconomies-of-scale.  You will need to define regions of linearity and create extra binary variables for these regions with either SOS1 or SOS2 constraints depending on how you implement the “separable programming” aspects.

 

I hope this helps - Jeff

 

 

From: help-glpk-bounces+jeff.kelly=honeywell.com@gnu.org [mailto:help-glpk-bounces+jeff.kelly=honeywell.com@gnu.org] On Behalf Of Paolo Rossi
Sent: Monday, April 04, 2011 1:48 PM
To: address@hidden
Subject: [Help-glpk] LP problem with variable coeffcients (parametric LPsimplex)

 

Hi everyone,

 

I am trying to replicate the modelling Byers, 2006. Commodity Storage Valuation: A linear optimization based on Traded Instruments, Energy Economics. The author is quite concise on how the model has been specified but it says that he used LpSolve

 

The paper assesses the value of a gas storage facility. The value is a function of:

-          Injected quantity:                                INJ

-           Withdrawn quantity:                          WITH

-          Price paid for injections:                    Pi

-          Price paid for withdrawals:                Pw

-          cost ofinjecting one unit of gas:         ci

-          cost of withdrawing one unit of gas: cw

 

If one takes two periods,

 

Max    -INJ1 x pi,1   +   WITH1 x pw,1   –   ci,1 x INJ1   –  cw,1 x WITH1  –   INJ2 x pi,2    +   WITH2 x pw,2  –  ci,2 x INJ2– cw,2 x WITH2

 

Constraints

-          For each time period i, if INJi > 0 then WITHi = 0 and if WITHi > 0 then INJi = 0 - you can either withdraw or inject. I thought of using a binary variable but then I realised that it would need to multiply INJi and WITHi so I got stuck as it would violate linearity of objective functions

-           

-          For each time period I, cw,I and ci,I (cost of withdrawing and cost of injecting) are a function of the gas stored in the facility.  The right curve here would be something similar to an exponential function through the origin for ci, i.e. the more gas you have in the facility the more it costs to push an extra unit of gas in. If one works with strep functions, the formulation would be something like

ci =      1  if sum of (inj – with ) over the periods up to i  is         <= 3

              2  if sum of (inj – with ) over the periods up to i is          > 3 and <= 6

              3  if sum of (inj – with ) over the periods up to i is          >  6

 

For cw, the curve would be symmetric to the one above.

cw =     3  if sum of (inj – with ) over the periods up to i is            <= 3

              2  if sum of (inj – with ) over the periods up to i is           > 3 and <= 6

              1  if sum of (inj – with ) over the periods up to i is          >  6

 

I am pretty stuck here so thanks a lot for any help

 

Paolo