|
Using semi-continuous var objects, piecewise linear expression objects, or something else? good = relatively painless and safe to code, with minimal computational overhead. |
|
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 \[\begin{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. 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)?
(Aug 19 '11 at 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.
(Aug 19 '11 at 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.
(Aug 19 '11 at 20:00)
shiva
1
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.
(Aug 20 '11 at 09:22)
Paul Rubin ♦
1
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.
(Aug 21 '11 at 16:00)
Paul Rubin ♦
|
