Piecewise Linear Function Fitting via Mixed-Integer Linear Programming

Steffen Rebennack () and Vitaliy Krasko ()
Additional contact information
Steffen Rebennack: Institute of Operations Research, Karlsruhe Institute of Technology, 76185 Karlsruhe, Baden-Württemberg, Germany
Vitaliy Krasko: Division of Economics and Business, Colorado School of Mines, Golden, Colorado 80401

INFORMS Journal on Computing, 2020, vol. 32, issue 2, 507-530

Abstract: Piecewise linear (PWL) functions are used in a variety of applications. Computing such continuous PWL functions, however, is a challenging task. Software packages and the literature on PWL function fitting are dominated by heuristic methods. This is true for both fitting discrete data points and continuous univariate functions. The only exact methods rely on nonconvex model formulations. Exact methods compute continuous PWL function for a fixed number of breakpoints minimizing some distance function between the original function and the PWL function. An optimal PWL function can only be computed if the breakpoints are allowed to be placed freely and are not fixed to a set of candidate breakpoints. In this paper, we propose the first convex model for optimal continuous univariate PWL function fitting. Dependent on the metrics chosen, the resulting formulations are either mixed-integer linear programming or mixed-integer quadratic programming problems. These models yield optimal continuous PWL functions for a set of discrete data. On the basis of these convex formulations, we further develop an exact algorithm to fit continuous univariate functions. Computational results for benchmark instances from the literature demonstrate the superiority of the proposed convex models compared with state-of-the-art nonconvex models.

Keywords: piecewise; linear; function:; linear; spline:; splines; of; degree; 1:; polyhedral; function:; mixed-integer; linear; programming; (MILP):; mixed-integer; quadratic; programming; (MIQP):; function; fitting:; spline; regression:; global; optimization (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2019.0890 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:32:y:2020:i:2:p:507-530

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().