1
1

Hi everyone,

I have two questions:

  • 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

  • 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 type of analysis done in other academic papers so it can be done although I don't know how

Many Thanks in advance,

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

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.

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

asked 25 May '11, 05:28

RandomOR's gravatar image

RandomOR
1314
accept rate: 0%

retagged 25 Nov '11, 12:29

fbahr's gravatar image

fbahr ♦
4.6k716


You may use SOS1 to linearize the term x2 * bx1, or use big M technique:

x1 <= x2

x1 <= M*bx1

where M is at least the largest value x2 could attain.

link

answered 25 May '11, 06:29

gabs's gravatar image

gabs
762
accept rate: 25%

edited 25 May '11, 06:49

Thanks for this - it makes a lot of sense. Thanks again for spending your time on my question Paolo

(26 May '11, 08:13) RandomOR

Linearization of a product term where one variable is binary can be done by the addition of three sets of constraints and a real variable that denotes:

x2*bx1 = z

Where x2 is the real continuous variable, bx1 is the binary variable and z is the variable that denotes the product of x2 and bx1.

z <= Ubx1 z <= x2 z >= x2 - U(1-bx1)

Where U is the upper bound of x2. Hope this helps

link

answered 26 May '11, 09:33

SandipMax's gravatar image

SandipMax
312
accept rate: 0%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×231
×65
×37
×1

Asked: 25 May '11, 05:28

Seen: 2,933 times

Last updated: 25 Nov '11, 12:29

OR-Exchange! Your site for questions, answers, and announcements about operations research.