Constructing Optimal Piecewise Quadratic Approximations for Enhancing Deterministic Global Optimization

References

• Alkhalifa L, Mittelmann H (2022) New algorithm to solve mixed integer quadratically constrained quadratic programming problems using piecewise linear approximation. Mathematics 10(2):198.Crossref, Google Scholar
• Andrei N (2013) Nonlinear Optimization Applications Using the GAMS Technology (Springer, New York).Crossref, Google Scholar
• Astorino A, Frangioni A, Gaudioso M, Gorgone E (2011) Piecewise-quadratic approximations in convex numerical optimization. SIAM J. Optim. 21(4):1418–1438.Crossref, Google Scholar
• Bertsimas D, Shioda R (2007) Classification and regression via integer optimization. Oper. Res. 55(2):252–271.Link, Google Scholar
• Billionnet A, Elloumi S, Lambert A (2016) Exact quadratic convex reformulations of mixed-integer quadratically constrained problems. Math. Programming 158(1):235–266.Crossref, Google Scholar
• Braun K, Burlacu R (2023) Benchmarking piecewise linear reformulations for MINLPs: A computational study based on the open-source framework PWL-T-REX. Optimization Online (September 29), https://optimization-online.org/?p=24335.Google Scholar
• Bussieck MR, Drud AS, Meeraus A (2003) MINLPLib—A collection of test models for mixed-integer nonlinear programming. INFORMS J. Comput. 15(1):114–119.Link, Google Scholar
• Butler JT, Frenzen CL, Macaria N, Sasao T (2011) A fast segmentation algorithm for piecewise polynomial numeric function generators. J. Comput. Appl. Math. 235(14):4076–4082.Crossref, Google Scholar
• Castro PM, Liao Q, Liang Y (2022) Comparison of mixed-integer relaxations with linear and logarithmic partitioning schemes for quadratically constrained problems. Optim. Engrg. 23:717–747.Crossref, Google Scholar
• Ceccon F, Baltean-Lugojan R, Bynum ML, Li C, Misener R (2020) GALINI: An extensible mixed-integer quadratically-constrained optimization solver. Technical report, Sandia National Laboratory (SNL-NM), Albuquerque, NM.Google Scholar
• Cheng X, Li X (2022) Discretization and global optimization for mixed integer bilinear programming. J. Global Optim. 84(4):843–867.Crossref, Google Scholar
• Codsi J, Ngueveu SU, Gendron B (2025) LinA: A faster approach to piecewise linear approximations using corridors and its application to mixed-integer optimization. Math. Programming Comput. 17:265–306.Crossref, Google Scholar
• 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
• Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math. Programming 91:201–213.Crossref, Google Scholar
• Furini F, Traversi E, Belotti P, Frangioni A, Gleixner A, Gould N, Liberti L, et al. (2019) QPLIB: Library of quadratic programming instances. Math. Programming Comput. 11:237–265.Crossref, Google Scholar
• Geißler B, Martin A, Morsi A, Schewe L (2011) Using piecewise linear functions for solving MINLPs. Lee J, Leyffer S, eds. Mixed Integer Nonlinear Programming (Springer, New York), 287–314.Google Scholar
• Goldberg N, Kim Y, Leyffer S, Veselka TD (2014) Adaptively refined dynamic program for linear spline regression. Comput. Optim. Appl. 58:523–541.Crossref, Google Scholar
• Goldberg N, Rebennack S, Kim Y, Krasko V, Leyffer S (2021) MINLP formulations for continuous piecewise linear function fitting. Comput. Optim. Appl. 79:223–233.Crossref, Google Scholar
• Goodrich MT (1995) Efficient piecewise-linear function approximation using the uniform metric. Discrete & Comput. Geometry 14:445–462.Crossref, Google Scholar
• Gorban AN, Mirkes EM, Zinovyev A (2016) Piece-wise quadratic approximations of arbitrary error functions for fast and robust machine learning. Neural Networks 84:28–38.Crossref, Google Scholar
• Graham RL (1975) The largest small hexagon. J. Combin. Theory Ser. A 18(2):165–170.Crossref, Google Scholar
• Gurobi Optimization, LLC (2024) Gurobi optimizer reference manual. Accessed June 28, 2024, https://www.gurobi.com.Google Scholar
• Hakimi SL, Schmeichel EF (1991) Fitting polygonal functions to a set of points in the plane. CVGIP Graphical Models Image Processing 53(2):132–136.Crossref, Google Scholar
• Hamann B, Chen JL (1994) Data point selection for piecewise linear curve approximation. Comput. Aided Geometric Design 11(3):289–301.Crossref, Google Scholar
• Imai H, Iri M (1986) An optimal algorithm for approximating a piecewise linear function. J. Inform. Processing 9(3):159–162.Google Scholar
• Jupp DL (1978) Approximation to data by splines with free knots. SIAM J. Numer. Anal. 15(2):328–343.Crossref, Google Scholar
• Kallrath J, Rebennack S (2014) Computing area-tight piecewise linear overestimators, underestimators and tubes for univariate functions. Rassias TM, Floudas CA, Butenko S, eds. Optimization in Science and Engineering: In Honor of the 60th Birthday of Panos M. Pardalos (Springer, New York), 273–292.Crossref, Google Scholar
• Karia T, Adjiman CS, Chachuat B (2021) Global optimization of mixed-integer polynomial programs via quadratic reformulation. Comput. Aided Chemical Engrg. 50:655–661.Crossref, Google Scholar
• Karia T, Adjiman CS, Chachuat B (2022) Assessment of a two-step approach for global optimization of mixed-integer polynomial programs using quadratic reformulation. Comput. Chemical Engrg. 165:107909.Crossref, 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
• Li Q, Zhang W, Bai Y, Wang G (2023) A non-convex piecewise quadratic approximation of ℓ0 regularization: Theory and accelerated algorithm. J. Global Optim. 86(2):323–353.Crossref, Google Scholar
• Magnani A, Boyd SP (2009) Convex piecewise-linear fitting. Optim. Engrg. 10:1–17.Crossref, Google Scholar
• Mangasarian O, Rosen JB, Thompson M (2006) Nonconvex piecewise-quadratic underestimation for global minimization. J. Global Optim. 34:475–488.Crossref, Google Scholar
• Misener R, Smadbeck JB, Floudas CA (2015) Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2. Optim. Methods Software 30(1):215–249.Crossref, Google Scholar
• Mittelmann H (2021) Latest benchmark results. Presentation, INFORMS Annual Conference, October 24–27, Anaheim, CA.Google Scholar
• Muggeo VM (2003) Estimating regression models with unknown break-points. Statist. Medicine 22(19):3055–3071.Crossref, Google Scholar
• Natali JM, Pinto JM (2009) Piecewise polynomial interpolations and approximations of one-dimensional functions through mixed integer linear programming. Optim. Methods Software 24(4–5):783–803.Crossref, Google Scholar
• Ngueveu SU (2019) Piecewise linear bounding of univariate nonlinear functions and resulting mixed integer linear programming-based solution methods. Eur. J. Oper. Res. 275(3):1058–1071.Crossref, Google Scholar
• Padberg M (2000) Approximating separable nonlinear functions via mixed zero-one programs. Oper. Res. Lett. 27(1):1–5.Crossref, Google Scholar
• Pastore de Lima AE, Ryu J, Maravelias CT (2024) Accounting for costs in attainable-region-based reactor–separation network synthesis: Models, tradeoffs, and insights. AIChE J. 70(4):e18341.Crossref, 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.Crossref, Google Scholar
• Powell MJ, Sabin MA (1977) Piecewise quadratic approximations on triangles. ACM Trans. Math. Software 3(4):316–325.Crossref, Google Scholar
• 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
• Rebennack S, Krasko V (2020) Piecewise linear function fitting via mixed-integer linear programming. INFORMS J. Comput. 32(2):507–530.Link, Google Scholar
• Ryu J, Maravelias CT (2020) Computationally efficient optimization models for preliminary distillation column design and separation energy targeting. Comput. Chemical Engrg. 143:107072.Crossref, Google Scholar
• Saxena A, Bonami P, Lee J (2011) Convex relaxations of non-convex mixed integer quadratically constrained programs: Projected formulations. Math. Programming 130:359–413.Crossref, Google Scholar
• Song Y, Maravelias CT (2024) Linear programming-based preprocessing algorithm and tightening constraints for multiperiod blend scheduling problems. Indust. Engrg. Chemistry Res. 63(9):4030–4045.Crossref, Google Scholar
• Song Y, Maravelias CT (2025) Constructing optimal piecewise quadratic approximations for enhancing deterministic global optimization. https://doi.org/10.1287/ijoc.2024.0909.cd, https://github.com/INFORMSJoC/2024.0909.Google Scholar
• Toriello A, Vielma JP (2012) Fitting piecewise linear continuous functions. Eur. J. Oper. Res. 219(1):86–95.Crossref, 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.Crossref, Google Scholar
• Warwicker JA, Rebennack S (2024) Efficient continuous piecewise linear regression for linearising univariate non-linear functions. IISE Trans. 57(3):231–245.Crossref, Google Scholar
• Yang L, Liu S, Tsoka S, Papageorgiou LG (2016) Mathematical programming for piecewise linear regression analysis. Expert Systems Appl. 44:156–167.Crossref, Google Scholar