×

zbMATH — the first resource for mathematics

Piecewise linear function fitting via mixed-integer linear programming. (English) Zbl 07290859
Summary: 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.
Reviewer: Reviewer (Berlin)

MSC:
90C Mathematical programming
Software:
CRIO; GloMIQO; LINDO; SCIP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg T (2009) SCIP: Solving constraint integer programs. Math. Programming Comput. 1(1):1-41.Crossref, Google Scholar · Zbl 1171.90476
[2] Bellman R, Roth R (1969) Curve fitting by segmented straight lines. J. Amer. Statist. Assoc. 64(327):1079-1084.Crossref, Google Scholar · Zbl 1302.90239
[3] Bertsimas D, King A (2016) OR Forum—An algorithmic approach to linear regression. Oper. Res. 64(1):2-16.Link, Google Scholar · Zbl 1338.90272
[4] Bertsimas D, Mazumder R (2014) Least quantile regression via modern optimization. Ann. Statist. 42(6):2494-2525.Crossref, Google Scholar · Zbl 1302.62154
[5] Bertsimas D, Shioda R (2007) Classification and regression via integer optimization. Oper. Res. 55(2):252-271.Link, Google Scholar · Zbl 1167.90593
[6] Bertsimas D, King A, Mazumder R (2016) Best subset selection via a modern optimization lens. Ann. Statist. 44(2):813-852.Crossref, Google Scholar · Zbl 1335.62115
[7] Chen DZ, Wang H (2009) Approximating points by a piecewise linear function: I. Dong Y, Du DZ, Ibarra O, eds. Algorithms and Computation—ISAAC 2009, Lecture Notes in Computer Science, vol. 5878 (Springer, Berlin), 224-233.Google Scholar
[8] Croxton KL, Gendron B, Magnanti TL (2003) A comparison of mixed-integer programming models for nonconvex piecewise linear cost minimization problems. Management Sci. 49(9):1268-1273.Link, Google Scholar · Zbl 1232.90311
[9] De Boor C, Rice JR (1968) Least squares cubic spline approximation, II-variable knots. Technical Report, Computer Science Technical Reports, Purdue University, West Lafayette, IN.Google Scholar
[10] Ertel JE, Fowlkes EB (1976) Some algorithms for linear spline and piecewise multiple linear regression. J. Amer. Statist. Assoc. 71(355):640-648.Crossref, Google Scholar · Zbl 0343.62058
[11] Feijoo B, Meyer RR (1988) Piecewise-linear approximation methods for nonseparable convex optimization. Management Sci. 34(3):411-419.Link, Google Scholar · Zbl 0648.90059
[12] Geißler B (2011) Towards globally optimal solutions for minlps by discretization techniques with applications in gas network optimization. Dissertation, Friedrich-Alexander-Universität Erlangen-Nürnberg, Erlangen-Nürnberg, Germany.Google Scholar
[13] Geißler B, Martin A, Morsi A, Schewe L (2012) Using Piecewise linear functions for solving MINLPs. Lee J, Leyffer S, eds. Mixed Integer Nonlinear Programming, The IMA Volumes in Mathematics and its Applications, vol. 154 (Springer, New York), 287-314.Crossref, Google Scholar · Zbl 1242.90132
[14] Goldberg N, Kim Y, Leyffer S, Veselka TD (2014) Adaptively refined dynamic program for linear spline regression. Comput. Optim. Appl. 58(3):523-541.Crossref, Google Scholar · Zbl 1305.90403
[15] Guthery SB (1974) Partition regression. J. Amer. Statist. Assoc. 69(348):945-947.Crossref, Google Scholar · Zbl 0296.62059
[16] Hamann B, Chen JL (1994) Data point selection for piecewise linear curve approximation. Comput. Aided Geometric Design 11(3):289-301.Crossref, Google Scholar · Zbl 0804.65019
[17] Jupp DLB (1978) Approximation to data by splines with free knots. SIAM J. Numerical Anal. 15(2):328-343.Crossref, Google Scholar · Zbl 0403.65004
[18] Kallrath J, Rebennack S (2014) Computing area-tight piecewise linear overestimators, underestimators and tubes for univariate functions. Butenko S, Floudas CA, Rassias TM, eds. Optimization in Science and Engineering (Springer, New York), 273-292.Crossref, Google Scholar · Zbl 1336.90064
[19] Lohmann T, Rebennack S (2017) Tailored Benders decomposition for a long-term power expansion model with short-term demand response. Management Sci. 63(6):2027-2048.Link, Google Scholar
[20] MacGregor JF, Harris TJ (1993) The exponentially weighted moving variance. J. Quality Tech. 25(2):106-118.Crossref, Google Scholar
[21] Magnani A, Boyd SP (2009) Convex piecewise-linear fitting. Optim. Engrg. 10(1):1-17.Crossref, Google Scholar · Zbl 1273.65086
[22] Maranas C, Floudas CA (1994) Global minimum potential energy conformations of small molecules. J. Global Optim. 4(2):135-170.Crossref, Google Scholar · Zbl 0797.90114
[23] McCoy K, Krasko V, Santi P, Kaffine D, Rebennack S (2016) Minimizing economic impacts from post-fire debris flows in the Western United States. Natl. Hazards 83(1):149-176.Crossref, Google Scholar
[24] McGee VE, Carleton WT (1970) Piecewise regression. J. Amer. Statist. Assoc. 65(331):1109-1124.Crossref, Google Scholar
[25] Misener R, Floudas CA (2013) GloMIQO: Global mixed-integer quadratic optimizer. J. Global Optim. 57(1):3-50.Crossref, Google Scholar · Zbl 1272.90034
[26] Muggeo VMR (2003) Estimating regression models with unknown break-points. Statist. Medicine 22(19):3055-3071.Crossref, Google Scholar
[27] Padberg M (2000) Approximating separable nonlinear functions via mixed zero-one programs. Oper. Res. Lett. 27(1):1-5.Crossref, Google Scholar · Zbl 0960.90065
[28] Rebennack S (2016a) Combining sampling-based and scenario-based nested benders decomposition methods: Application to stochastic dual dynamic programming. Math. Programming 156(1/2):343-389.Crossref, Google Scholar · Zbl 1342.90116
[29] Rebennack S (2016b) Computing tight bounds via piecewise linear functions through the example of circle cutting problems. Math. Methods Oper. Res. 84(1):3-57.Crossref, Google Scholar · Zbl 1396.90051
[30] Rebennack S (2016c) Piecewise linear functions. OR News 58 (November), 7-8.Google Scholar
[31] Rebennack S, Kallrath J (2015) Continuous piecewise linear delta-approximations for univariate functions: Computing minimal breakpoint systems. J. Optim. Theory Appl. 167(2):617-643.Crossref, Google Scholar · Zbl 1327.90245
[32] Rosen JB, Pardalos PM (1986) Global minimization of large-scale constrained concave quadratic problems by separable programming. Math. Programming 34(2):163-174.Crossref, Google Scholar · Zbl 0597.90066
[33] Schrage L (2004) LindoAPI. Software, Lindo Systems, Chicago.Google Scholar
[34] Sherali HD (2001) On mixed-integer zero-one representations for separable lower-semicontinuous piecewise-linear functions. Oper. Res. Lett. 28(4):155-160.Crossref, Google Scholar · Zbl 0992.90049
[35] Tawarmalani M, Sahinidis NV (2005) A polyhedral branch-and-cut approach to global optimization. Math. Programming 103(2):225-249.Crossref, Google Scholar · Zbl 1099.90047
[36] Toriello A, Vielma JP (2012) Fitting piecewise linear continuous functions. Eur. J. Oper. Res. 219(1):86-95.Crossref, Google Scholar · Zbl 1244.90166
[37] Vielma JP, Nemhauser GL (2011) Modeling disjunctive constraints with a logarithmic number of binary variables and constraints. Math. Programming 128(1-2):49-72.Crossref, Google Scholar · Zbl 1218.90137
[38] Vielma JP, Ahmed S, Nemhauser G (2010) Mixed-integer models for nonseparable piecewise-linear optimization: Unifying framework and extensions. Oper. Res. 58(2):303-315.Link, Google Scholar · Zbl 1226.90046
[39] Williams CM (1978) An efficient algorithm for the piecewise linear approximation of planar curves. Comput. Graphics Image Processing 8(2):286-293.Crossref, Google Scholar
[40] Wood SN (2001) Minimizing model fitting objectives that contain spurious local minima by bootstrap restarting. Biometrics 57(1):240-244.Crossref, · Zbl 1209.62368
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.