I am working on a linear programming problem where some of the terms of the objective function to maximize are expressed as a piecewise linear function of variables:

$$ z = \begin{cases} c^- \times x & x\leq 0 \\ c^+ \times x & x > 0 \\ \end{cases} $$

When I have $c^- \geq c^+$, I can solve the problem by adding a new variable $x'$, and two constraints:

• $x' \leq c^- \times x $
• $x' \leq c^+ \times x $

But what do I do when $c^- < c^+$ ? I don't think there is a way to express the problem as a linear programming problem in that case, is there ?

I have heard about SOS constraints. Are there the canonical way to solve this kind of problem ? If my problem contains many such piecewise linear functions, is it reasonable to expect a free solver from being able to solve such a problem with thousands of SOS1 constraints ?