(598b) On the Derivation of Piecewise Linear Continuous Approximating Functions
In this paper, we present two mixed-integer models. The first one (M1) minimizes the fitting error given a fixed number of break points, while the second one (M2) finds the minimum number of break points to satisfy an error tolerance for every data point. In both models, binary variables and mixed-integer constraints are introduced to assign data points to the correct interval/segment of the piecewise linear functions. Most importantly, unlike known approaches that enforce continuity via nonlinear constraints, we first derive a proposition that allow us to enforce continuity through an equivalent condition, which involves comparing the approximations of two special data points with piecewise linear functions from two adjacent intervals. Then, we present linear constraints to enforce that the obtained approximation satisfies this condition. Thus, we propose a mixed-integer linear fitting model, rather than mixed integer nonlinear model, which is significantly faster than all previously proposed approaches.
Further, we show how the proposed models can be extended to approximate continuous functions. In particular, we show how to find the minimum number of linear segments required such that error between the piecewise linear approximation and the original function is within a tolerance. This involves solving M2 iteratively, with the data set coming from evaluating the original function at discrete locations.
The models are tested with a series of real-world examples using data that come from experiments. The models are also applied to find piecewise linear approximations of some benchmark univariate functions with different error tolerances. Solution quality and computational performance are compared against known approaches.
 A. Toriello and J. P. Vielma, "Fitting piecewise linear continuous functions," European Journal of Operational Research, vol. 219, pp. 86-95, May 16 2012.
 S. Rebennack and J. Kallrath, "Continuous Piecewise Linear Delta-Approximations for Univariate Functions: Computing Minimal Breakpoint Systems," Journal of Optimization Theory and Applications, vol. 167, pp. 617-643, Nov 2015.
 S. Rebennack and J. Kallrath, "Continuous Piecewise Linear Delta-Approximations for Bivariate and Multivariate Functions," Journal of Optimization Theory and Applications, vol. 167, pp. 102-117, Oct 2015.
 L. J. Yang, S. S. Liu, S. Tsoka, and L. G. Papageorgiou, "Mathematical programming for piecewise linear regression analysis," Expert Systems with Applications, vol. 44, pp. 156-167, Feb 2016.