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

Question

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!

Answer 1

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.

Answer 2

The "low-tech" way to handle this would be to break it up into two linear programming problems, one with $x-a$ and constraint $x \le b$, the other with $b-a$ and constraint $x \ge b$, and take whichever optimal solution has the lower objective value. Of course, this doesn't scale well if you have lots of terms of this type.