For a large LP model a customer of mine wanted to have instead of a V shaped penalty around a goal, something that approximates a U shaped penalty. With standard slacks:
we essentially have a V shaped penalty:
We can approximate a more U shaped form by introducing extra slacks with a smaller penalty:
with unit penalty q smaller than p, e.q. q=0.1*p. This will give:
The idea is that the algorithm will select the cheap slacks t first, before spending on the expensive slacks s. This will keep the LP linear and we don’t need extra binary variables. For q=0 we essentially allow small deviations for free, but start paying when we go beyond the threshold T.
This approach can easily be extended to more piecewise linear segments (as long as we keep things convex). Also the range T for the slacks t may be generalized to:
Hi,
ReplyDeleteThis problem is a two stage stochastic model. From mathematical point of view, the addition of another surplus and deficit variables trims the feasible region (above the V) and increases the cost function. But what would be the reason for having two such variables? What would be the case in non-linear constraints?
Thanks,
Yousef
No, this is deterministic.
ReplyDeleteYes, I agree. It is the extensive deterministic representation of a two-stage stochastic model. From practical point of view I'd like to know why there are two sets of surplus and deficit (s and t). Would it be reasonable to have a second pair of variables (like s) if t does not have limit?
ReplyDelete