# Optimal way to formulate a piecewise linear function

I am working on LP problem whose objective function includes a piecewise linear function. I would like to figure out the optimal way to formulate the piecewise linear function in order to minimize the complexity and hence the runtime.

One way to work around this is to introduce as many binary variables as the function's linear segments (defined by its breakpoints) and then impose some constraints to such that only one segment is active each time. However, this shifts the LP problem to a MIP and increases the runtime significantly; the function has more than 500 breakpoints and more than 1000 timepoints, meaning there have to be introduced more than 500'000 binary variables.

From literature online I know that SOS constraints can also be used in such cases, but not all solvers support them and some others just introduce the binary variables in the backend.

Could you please advise on the best way to approach this complex problem? What is the best open-source solver to use in this case?

• Is the piecewise linear function convex? Commented Jun 24 at 17:54
• @RobPratt not necessarily, but it's increasing (not necessarily strictly though) Commented Jun 24 at 17:56
• @prubin I am minimizing. The argument is scalar per timepoint; if you consider it over all timepoints it is a vector, however the equations/inequalities are calculated and hold per timepoint. The breakpoints change per timepoint, so the function is not the same per se across different timepoints. Commented Jun 24 at 19:00
• (I'm restoring this comment, which I deleted, so that the answer above has context.) Are you maximizing or minimizing, is the argument of the PWL functions scalar or vector, and is the same PWL applied to each of the 1000 "timepoints"?
– prubin
Commented Jun 24 at 19:03
• There are techniques to use a logarithmic number of binary variables. In some cases, this makes a real difference. Juan Pablo Vielma and George L. Nemhauser, Modelling Disjunctive Constraints with a Logarithmic Number of Binary Variables and Constraints, Mathematical Programming 128 (2011), pp. 49-72 Commented Jun 27 at 5:05

It might be worth looking at a simplest case: you are maximizing and the PWL function $$f_t$$ for time point $$t$$ is always concave. A concave PWL function is the minimum of a bunch of linear functions (one per segment). For each $$t$$, you can replace the corresponding PWL function in the objective with a surrogate variable $$z_t$$ and then constrain $$z_t$$ to be less than or equal to each segment function. The good news is that you only need 1000 new continuous variables. The bad news is that you just added ~500,000 new inequality constraints.