0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Erwin Kalvelagen Jan 5 '18 at 11:12
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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