Using semi-continuous var objects, piecewise linear expression objects, or something else?

good = relatively painless and safe to code, with minimal computational overhead.

asked 19 Aug '11, 12:08

shiva's gravatar image

accept rate: 0%

I'd go with an SOS1 approach. Suppose that the breakpoints are (a_1 < a_2 < dots < a_n < a_{n+1}le infty) (last interval closed on the right, and we need (x) bounded for this to work), with function value (f_j) when (a_j le x < a_{j+1}). Letting (y) be the variable capturing the value of the step function, add binary variables (u_1,dots,u_n) and constraints [egin{eqnarray} sum_{i=1}^n a_i u_i le x le sum_{i=1}^n a_{i+1} u_i \ y = sum_{i=1}^n f_i u_i \ sum_{i=1}^n u_i = 1.end{eqnarray}] You may also want to declare the (u) variables as an SOS1 to the solver, although it's not clear how much help the solver needs identifying an SOS1, nor how much benefit the solver gets from the fact.


answered 19 Aug '11, 13:48

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

edited 19 Aug '11, 16:54

Thanks for the feedback. Many, many points if i was allowed to give it :). some follow up doubts below as i try to wrap my head around this really nice line of attack. pls feel free to post here and/or link back to your blog if that's more convenient for u.

Q1. with binary u and 3rd constraint, isnt that = SOS1? would SOS1 be enough?

Q2. y = some weighted sum of up to 2 different f_i values (up to 3 if u is not binary)?

(19 Aug '11, 15:09) shiva

Sorry, I booted the original response (which your Q2 nails). The SOS2 model I gave was wrong, and fixing it might require "big M" constraints that would outweigh the value of the SOS2 set itself. I'ved edited the response to use SOS1, and (hopefully) be correct this time.

(19 Aug '11, 16:52) Paul Rubin ♦♦

Big thanks. The minor revisions seem to have solved the issue! If stair_i is active: a. x has be somewhere on that stair, b. f_i = corr constant stair function value, c. all other stairs are inactive.

Lots of well-known useful practical applications. e.g., A staircase incentive depending on volume of sales, increasing cost of satisfying demand as a seller due to more expensive vendors, lot sizes, etc.

(19 Aug '11, 20:00) shiva

One clarification: Since math programming admits only weak inequalities, if (x=a_i) then both (u_i=1,y=f_i) and (u_{i-1}=1,y=f_{i-1}) are feasible, and the solver will grab whichever yields the better objective value. There is no way to make the interval for each step semiopen.

(20 Aug '11, 09:22) Paul Rubin ♦♦

I did in fact do a blog post on this today (http://orinanobworld.blogspot.com/2011/08/piecewise-linear-functions-redux.html) to put it in context vis-a-vis continuous pw-linear functions.

(21 Aug '11, 16:00) Paul Rubin ♦♦
Your answer
toggle preview

Follow this question

By Email:

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



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



Asked: 19 Aug '11, 12:08

Seen: 3,711 times

Last updated: 21 Aug '11, 16:00

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