A Comparison of two Mixed-Integer Linear Programs for Piecewise Linear Function Fitting

The problem of fitting continuous piecewise linear (PWL) functions to discrete data has applications in pattern recognition and engineering, amongst many others. To find an optimal PWL function, it is required that the positioning of the breakpoints connecting adjacent linear segments are not constrained, and are allowed to be placed freely. While the PWL fitting problem has often been approached from a global optimisation perspective, recently two mixed-integer linear programming (MILP) approaches have been presented which solve for optimal PWL functions. In this paper, we compare the two approaches: the first was presented by [Rebennack and Krasko, IJOC, 2020], the second by [Kong and Maravelias, IJOC, 2020]. Both formulations are similar in that they use binary variables and logical implications modelled by Big-M constraints to ensure the continuity of the PWL function, yet the former model uses fewer binary variables. We present experimental results comparing the time taken to find optimal PWL functions with differing numbers of breakpoints across five data sets for three different objective functions. While neither of the two formulations is superior on all data sets, the presented computational results suggest that the formulation presented by Rebennack and Krasko is faster. This might be explained by the fact that it contains fewer complicating binary variables.

Citation

June 2020

Article

Download

View A Comparison of two Mixed-Integer Linear Programs for Piecewise Linear Function Fitting