2
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ Is the piecewise linear function convex? $\endgroup$
    – RobPratt
    Commented Jun 24 at 17:54
  • $\begingroup$ @RobPratt not necessarily, but it's increasing (not necessarily strictly though) $\endgroup$
    – Apostolos
    Commented Jun 24 at 17:56
  • $\begingroup$ @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. $\endgroup$
    – Apostolos
    Commented Jun 24 at 19:00
  • $\begingroup$ (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"? $\endgroup$
    – prubin
    Commented Jun 24 at 19:03
  • $\begingroup$ 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 $\endgroup$ Commented Jun 27 at 5:05

1 Answer 1

1
$\begingroup$

I don't think you can gainfully avoid the binary variables (or SOS constraints). Some solvers directly support piecewise linear functions, but I'm pretty sure that means added binary variables under the hood in most cases.

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.

If the function is increasing but not concave, a heuristic approach (not guaranteed to generate an optimal solution) is to start with a PWL concave outer approximation to each PWL function (adding variables and constraints as above). The first time out, you still have an LP. Once you get a solution, check whether it overestimates the PWL objective contributions of any time points. If yes, introduce binary variables to break up the approximations there (essentially splitting the function at the nearest breakpoint and using outer approximations of the left and right portions. Now you are into a MIP model. Solve, check for superoptimality, split (adding binary variables) and repeat until either nothing changes or (more likely) you run out of time or memory. The hope is that (a) you don't end up adding anywhere near 500K binary variables, (b) you don't die of exhaustion trying this and (c) the final solution is, if not optimal, at least decent.

Personally, I would try the 500K binary variables (or SOS1 constraints if supported) and hope for the best.

$\endgroup$
2
  • $\begingroup$ Thanks for the detailed reply. Could you also suggest some good solvers for such large problems? I found some libraries online among others, PuLP, pyomo, cvxpy, ortools which I can combine with solvers like GLPK, GLOP. I would also be interested in using the Interior Point method instead of Simplex. Would you think this would increase the speed? $\endgroup$
    – Apostolos
    Commented Jun 24 at 19:24
  • $\begingroup$ I'm not good at predicting when interior point speeds things up. It certainly could not hurt to try it (assuming your solver supports it). As far as solvers go, CPLEX, Gurobi and Xpress (listed in alphabetical order so as not to offend their respective fans) would be good choices, but they are all commercial (unless you qualify for an academic license). I don't have any experience with open-source MIP solvers on problems that size. I've heard good things about HiGHS, and SCIP is highly regarded (if you qualify for its somewhat restrictive open-source license). $\endgroup$
    – prubin
    Commented Jun 24 at 19:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.