# Linearize LP constraints and SOS2

 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 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. 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 asked 25 May '11, 05:28 RandomOR 13●1●4 accept rate: 0% fbahr ♦ 4.6k●7●16

 3 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. answered 25 May '11, 06:29 gabs 76●2 accept rate: 25% 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
 3 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 answered 26 May '11, 09:33 SandipMax 31●2 accept rate: 0%
 toggle preview community wiki

### Follow this question

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,924 times

Last updated: 25 Nov '11, 12:29

### Related questions

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