Linear programming or mixed integer linear programming approximation

Question

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?

Answer 1

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.