(598b) On the Derivation of Piecewise Linear Continuous Approximating Functions

Continuous piecewise linear functions have been widely used in fitting data points or approximating nonlinear functions. While many papers have focused on how to model continuous piecewise linear functions and how to incorporate them into mixed-integer programing (MIP) models, there has been limited research on how to obtain the piecewise linear functions. For example, how many segments are needed, given an error tolerance, to approximate data; or given a fixed number of segments, where to place the break points so that the fitting error is minimized. In this work, we consider the problem of fitting one-dimensional (i.e., one independent variable) data set with continuous piecewise linear functions with variable number/location of break points. While some papers have considered optimizing the number and/or location of break points [1-4], none has addressed the same problem as in this work. For example, the approach by Toriello and Vielma [1] deals only with convex piecewise linear functions; the MINLP models in Rebennack and Kallrath [2, 3] are for approximating functions, instead of data points; and the approach by Yang et al. [4] leads to discontinuous piecewise linear approximation.

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.

Reference

[1] A. Toriello and J. P. Vielma, "Fitting piecewise linear continuous functions," European Journal of Operational Research, vol. 219, pp. 86-95, May 16 2012.

[2] 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.

[3] 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.

[4] 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.