Sunday, October 31, 2010

U shaped penalties

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:

 

image

we essentially have a V shaped penalty:

image

We can approximate a more U shaped form by introducing extra slacks with a smaller penalty:

image

with unit penalty q smaller than p, e.q. q=0.1*p. This will give:

image

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:

image