Can I linearize this piecewise function so it can be used in an objective function for the LP optimization model

linear programminglinearizationmixed-integer programmingnon-convex-optimizationoptimization

Thanks for taking the time to read this.

I am looking for methods to linearize this piecewise function so that it can be added to an optimization function of a linear programming problem. I figured out how to do this for mixed integer programming, but I would ideally be able to make it work with linear programming.

$$
\min f(x)
$$

When $0\leq x \leq b$
$$
f(x) = x – a
$$

when $x > b$
$$
f(x) = b – a
$$

$a$ and $b$ are constants. $x$ is the decision variable. I want to minimize $f(x)$. Can just plug in $a=4$, $b=10$, or something like that.

From what I have read online in blogs and papers, it seems like it would require a binary variable or an SOS set. I am using PuLP as my solver, which does not have SOS sets. Is it possible to linearize this function without having to use mixed integer programming?

Thank you!

Best Answer

Your piecewise-linear function is concave and so cannot be linearized without introducing a binary variable. If it were instead convex, you could use linear programming.

Related Question