Continuous Piecewise Linear δ-Approximations for MINLP Problems. I. Minimal Breakpoint Systems for Univariate Functions

For univariate functions, we compute optimal breakpoint systems subject to the condition that the piecewise linear approximation (or, under- and overestimator) never deviates more than a given δ-tolerance from the original function, over a given finite interval. The linear approximators, under- and overestimators involve shift variables at the breakpoints leading to a small number of breakpoints while still ensuring continuity over the full interval. We develop two mixed integer non-linear programming models: one which yields the minimal number of breakpoints, and another in which, for a fixed number of breakpoints, their values are computed. Alternatively, we use two heuristics in which we compute the breakpoints subsequently, solving small mixed integer non-linear programming problems, with significantly fewer variables. The optimal breakpoints for the nonlinear functions can be used in the mixed integer linear programming problem replacement of the original non-linear programming problem or the mixed integer non-linear programming problem. Due to the δ-limited discretization error and the minimal number of breakpoints, the solution of the mixed integer linear programming problem can be obtained in reasonable time and serves a good approximation to the global optimum, which can be fed into a local non-linear programming or mixed integer non-linear programming solver for the final refinement.