Tightening the Difference-of-Convex Formulation for the Piecewise Linear Approximation in General Dimensions

References

• Bärmann A, Burlacu R, Hager L, Kutzer K (2023) An approximation algorithm for optimal piecewise linear interpolations of bounded variable products. J. Optim. Theory Appl. 199(2):569–599.Google Scholar
• Bertsimas D, Tsitsiklis J (1997) Introduction to Linear Optimization (Athena Scientific, Nashua, NH).Google Scholar
• Boyd S, Vandenberghe L (2004) Convex Optimization (Cambridge University Press, Cambridge, UK).Google Scholar
• Bureau of Reclamation (2024) HDB data service. Accessed April 3, 2025, https://www.usbr.gov/lc/region/g4000/riverops/_HdbWebQuery.html.Google Scholar
• Chen KL, Garudadri H, Rao BD (2023) Improved bounds on neural complexity for representing piecewise linear functions. Preprint, submitted January 16, https://arxiv.org/abs/2210.07236.Google Scholar
• D’Ambrosio C, Lodi A, Martello S (2010) Piecewise linear approximation of functions of two variables in MILP models. Oper. Res. Let. 38(1):39–46.Google Scholar
• Davis PJ (1975) Interpolation and Approximation (Courier Corporation, North Chelmsford, MA).Google Scholar
• DeVore R, Hanin B, Petrova G (2021) Neural network approximation. Acta Numer. 30:327–444.Google Scholar
• Duguet A, Ngueveu SU (2022) Piecewise linearization of bivariate nonlinear functions: Minimizing the number of pieces under a bounded approximation error. Ljubić I, Barahona F, Dey SS, Mahjoub AR, eds. Combinatorial Optimization (Springer International Publishing, Cham, Switzerland), 117–129.Google Scholar
• Edelsbrunner H, O’Rourke J, Seidel R (1986) Constructing arrangements of lines and hyperplanes with applications. SIAM J. Comput. 15(2):341–363.Google Scholar
• Frenzen CL, Sasao T, Butler JT (2010) On the number of segments needed in a piecewise linear approximation. J. Comput. Appl. Math. 234(2):437–446.Google Scholar
• 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 (Springer, New York), 287–314.Google Scholar
• Gurobi Optimization LLC (2024a) Gurobi Optimizer reference manual. Accessed April 3, 2025, https://www.gurobi.com.Google Scholar
• Gurobi Optimization LLC (2024b) Model.addGenConstrIndicator(). Accessed April 3, 2025, https://www.gurobi.com/documentation/current/refman/py_model_agc_indicator.html.Google Scholar
• Huang C (2020) ReLU networks are universal approximators via piecewise linear or constant functions. Neural Comput. 32(11):2249–2278.Google Scholar
• Hughes RB, Anderson MR (1996) Simplexity of the cube. Discrete Math. 158(1):99–150.Google Scholar
• Kazda K, Li X (2021) Nonconvex multivariate piecewise-linear fitting using the difference-of-convex representation. Comput. Chemical Engrg. 150:107310.Google Scholar
• Kazda K, Li X (2024) A linear programming approach to difference-of-convex piecewise linear approximation. Eur. J. Oper. Res. 312(2):493–511.Google Scholar
• Kong L, Maravelias CT (2020) On the derivation of continuous piecewise linear approximating functions. INFORMS J. Comput. 32(3):531–546.Link, Google Scholar
• Kripfganz A, Schulze R (1987) Piecewise affine functions as a difference of two convex functions. Optimization 18(1):23–29.Google Scholar
• Marfatia Z, Li X (2022) Data-driven natural gas compressor models for gas transport network optimization. Digital Chem. Engrg. 3:100030.Google Scholar
• Misener R, Floudas CA (2010) Piecewise-linear approximations of multidimensional functions. J. Optim. Theory Appl. 145(1):120–147.Google Scholar
• Ploussard Q (2024) Piecewise linear approximation with minimum number of linear segments and minimum error: A fast approach to tighten and warm start the hierarchical mixed integer formulation. Eur. J. Oper. Res. 315(1):50–62.Google Scholar
• Ploussard Q (2025) Continuous piecewise linear fitting: Code repository. Accessed April 3, 2025, https://github.com/quentinplsrd/cpwl-nd-optimization.Google Scholar
• Rebennack S, Kallrath J (2015) Continuous piecewise linear delta-approximations for bivariate and multivariate functions. J. Optim. Theory Appl. 167(1):102–117.Google Scholar
• Rebennack S, Krasko V (2020) Piecewise linear function fitting via mixed-integer linear programming. INFORMS J. Comput. 32(2):507–530.Link, Google Scholar
• Toriello A, Vielma JP (2012) Fitting piecewise linear continuous functions. Eur. J. Oper. Res. 219(1):86–95.Google Scholar
• Vielma JP (2015) Mixed integer linear programming formulation techniques. SIAM Rev. 57(1):3–57.Google Scholar
• 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
• Warwicker JA, Rebennack S (2022) A comparison of two mixed-integer linear programs for piecewise linear function fitting. INFORMS J. Comput. 34(2):1042–1047.Link, Google Scholar
• Warwicker JA, Rebennack S (2023) Generating optimal robust continuous piecewise linear regression with outliers through combinatorial Benders decomposition. IISE Trans. 55(8):755–767.Google Scholar
• Warwicker JA, Rebennack S (2025) Efficient continuous piecewise linear regression for linearising univariate non-linear functions. IISE Trans. 57(3):231–245.Google Scholar