# Linear programming or mixed integer linear programming approximation

This may well be a stupid question. Given a one-dimensional non-convex/concave piecewise linear $\mathbf R\to\mathbf R$ function, is there a way to translate its minimization problem into a linear programming one? Do I have to resort to mixed integer linear programming writing the constraint as, say $a\delta \le x\le b\delta$ where $\delta\in\{0,1\}$ and $\{a,b\}$ is given?

• If the resulting problem is convex you can use LP, otherwise you need a MIP. Note that a MIP formulation will solve fast if the problem is convex, so if things are data dependent just use a MIP formulation. – Erwin Kalvelagen Jan 5 '18 at 11:12

You did not specify what if any constraints might apply. Assuming that any constraints on the decision variable $x$ are linear (and that any other variables tied to $x$ through those constraints are continuous), you could determine the feasible domain of $x$ by solving two LPs, one that minimizes $x$ subject to those constraints and the other that maximizes $x$. Since the minimum of your p.w.l. function $f$ on any individual segment must occur at one of the endpoints of that segment, you can just intersect the breakpoints of $f$ with the domain of $x$ obtained from the two LPs, enumerate the values of $f$ on the feasible breakpoints, and pick a winner.