On the Approximation of Separable Nonconvex Optimization Programs to an Arbitrary Numerical Tolerance

References

• Assad AA (1978) Multicommodity network flows—A survey. Networks 8(1):37–91.Crossref, Google Scholar
• Bank RE, Sherman AH, Weiser A (1983) Some refinement algorithms and data structures for regular local mesh refinement. Stepleman RS, ed. Scientific Computing: Applications of Mathematics and Computing to the Physical Sciences (North-Holland, Amsterdam), 3–17.Google Scholar
• Beasley JE (1990) Or-library: Distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11):1069–1072.Crossref, Google Scholar
• Belotti P, Lee J, Liberti L, Margot F, Wächter A (2009) Branching and bounds tightening techniques for non-convex MINLP. Optim. Methods Softw. 24(4–5):597–634.Crossref, Google Scholar
• Bestuzheva K, Besançon M, Chen WK, Chmiela A, Donkiewicz T, van Doornmalen J, Eifler L, et al. (2023) Enabling research through the SCIP Optimization Suite 8.0. ACM Trans. Math. Softw. 49(2):1–21.Crossref, Google Scholar
• Bey J (2000) Simplicial grid refinement: On Freudenthal’s algorithm and the optimal number of congruence classes. Numer. Math. (Heidelb). 85(1):1–29.Crossref, Google Scholar
• Boland N, Hewitt M, Marshall L, Savelsbergh M (2017) The continuous-time service network design problem. Oper. Res. 65(5):1303–1321.Link, Google Scholar
• Boland N, Hewitt M, Marshall L, Savelsbergh M (2019) The price of discretizing time: A study in service network design. EURO J. Transp. Logist. 8(2):195–216.Crossref, Google Scholar
• Burlacu R (2022) On refinement strategies for solving MINLPs by piecewise linear relaxations: A generalized red refinement. Optim. Lett. 16(2):635–652.Crossref, Google Scholar
• Burlacu R, Geiβler B, Schewe L (2020) Solving mixed-integer nonlinear programmes using adaptively refined mixed-integer linear programmes. Optim. Methods Softw. 35(1):37–64.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. Prog. Comp. 17(2):265–306.Crossref, Google Scholar
• Contardo C, Ngueveu SU (2026) On the approximation of separable nonconvex optimization programs to an arbitrary numerical tolerance. https://doi.org/10.1287/ijoc.2022.0221.cd, https://github.com/INFORMSJoC/2022.0221.Google Scholar
• Cornuéjols G, Thizy JM (1982) Some facets of the simple plant location polytope. Math. Programming 23(1):50–74.Crossref, Google Scholar
• Crainic TG, Frangioni A, Gendron B (2001) Bundle-based relaxation methods for multicommodity capacitated fixed charge network design. Discrete Appl. Math. (1979) 112(1–3):73–99.Crossref, Google Scholar
• D’Ambrosio C, Frangioni A, Gentile C (2019) Strengthening the sequential convex MINLP technique by perspective reformulations. Optim. Lett. 13(4):673–684.Crossref, Google Scholar
• D’Ambrosio C, Lee J, Wächter A (2009) A global-optimization algorithm for mixed-integer nonlinear programs having separable non-convexity. Fiat A, Sanders P, eds. Algorithms - ESA 2009. ESA 2009, Lecture Notes in Computer Science, vol. 5757 (Springer, Berlin, Heidelberg), 107–118.Crossref, Google Scholar
• D’Ambrosio C, Lee J, Wächter A (2012) An algorithmic framework for MINLP with separable non-convexity. Mixed Integer Nonlinear Programming (Springer, New York), 315–347.Crossref, Google Scholar
• Ertel JE, Fowlkes EB (1976) Some algorithms for linear spline and piecewise multiple linear regression. J. Am. Stat. Assoc. 71(355):640–648.Crossref, Google Scholar
• Ford LR Jr, Fulkerson DR (1956) Solving the transportation problem. Management Sci. 3(1):24–32.Link, Google Scholar
• Freudenthal H (1942) Simplizialzerlegungen von beschrankter flachheit. Ann. Math. 43(3):580–582.Crossref, 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, New York), 287–314.Crossref, Google Scholar
• Günlük O, Linderoth J (2010) Perspective reformulations of mixed integer nonlinear programs with indicator variables. Math. Programming 124(1):183–205.Crossref, Google Scholar
• Gurobi Optimization, LLC (2024) Gurobi Optimizer Reference Manual. Accessed November 1, 2025, https://www.gurobi.com.Google Scholar
• Harkness J, ReVelle C (2003) Facility location with increasing production costs. Eur. J. Oper. Res. 145(1):1–13.Crossref, Google Scholar
• Holmberg K (1999) Exact solution methods for uncapacitated location problems with convex transportation costs. Eur. J. Oper. Res. 114(1):127–140.Crossref, Google Scholar
• Holmberg K, Rönnqvist M, Yuan D (1999) An exact algorithm for the capacitated facility location problems with single sourcing. Eur. J. Oper. Res. 113(3):544–559.Crossref, Google Scholar
• Huchette J, Vielma JP (2022) Nonconvex piecewise linear functions: Advanced formulations and simple modeling tools. Oper. Res. 71(5):1835–1856.Google Scholar
• Hwang F, Huang Y (2021) An effective logarithmic formulation for piecewise linearization requiring no inequality constraint. Comput. Optim. Appl. 79:601–631.Crossref, Google Scholar
• IBM (2020) CPLEX Optimization Studio 201.Google Scholar
• Kleinschmidt P, Schannath H (1995) A strongly polynomial algorithm for the transportation problem. Math. Programming 68(1–3):1–13.Crossref, Google Scholar
• Lu D, Gzara F, Elhedhli S (2014) Facility location with economies and diseconomies of scale: Models and column generation heuristics. IIE Trans. 46(6):585–600.Crossref, Google Scholar
• Marshall L, Boland N, Savelsbergh M, Hewitt M (2021) Interval-based dynamic discretization discovery for solving the continuous-time service network design problem. Transportation Sci. 55(1):29–51.Link, Google Scholar
• Martinelli R, Pecin D, Poggi M (2014) Efficient elementary and restricted non-elementary route pricing. Eur. J. Oper. Res. 239(1):102–111.Crossref, Google Scholar
• Nagarajan H, Lu M, Yamangil E, Bent R (2016) Tightening McCormick relaxations for nonlinear programs via dynamic multivariate partitioning. Internat. Conf. Principles Practice Constraint Programming (Springer, Cham, Switzerland), 369–387.Google Scholar
• Nagarajan H, Lu M, Wang S, Bent R, Sundar K (2019) An adaptive, multivariate partitioning algorithm for global optimization of nonconvex programs. J. Glob. Optim. 74:1573–2916.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
• O’Rourke J (1981) An on-line algorithm for fitting straight lines between data ranges. Comm. ACM. 24(9):574–578.Crossref, Google Scholar
• Paraskevopoulos DC, Gürel S, Bektaş T (2016) The congested multicommodity network design problem. Transportation Res. Part E Logist. Transportation Rev. 85:166–187.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 (2019) Piecewise linear function fitting via mixed-integer linear programming. INFORMS J. Comput. 32(2):507–530.Link, Google Scholar
• Righini G, Salani M (2008) New dynamic programming algorithms for the resource constrained elementary shortest path problem. Networks 51(3):155–170.Crossref, Google Scholar
• Stellato B, Banjac G, Goulart P, Bemporad A, Boyd S (2020) OSQP: An operator splitting solver for quadratic programs. Math. Prog. Comp. 12(4):637–672.Crossref, Google Scholar
• Tomek I (1974a) Piecewise-linear approximation with a bound on absolute error. Comput. Biomed. Res. 7(1):64–70.Crossref, Google Scholar
• Tomek I (1974b) Two algorithms for piecewise-linear continuous approximation of functions of one variable. IEEE Trans. Comput. 100(4):445–448.Crossref, Google Scholar
• Trindade RS, d’Ambrosio C, Frangioni A, Gentile C (2023) Comparing perspective reformulations for piecewise-convex optimization. Oper. Res. Let. 51(6):702–708.Crossref, Google Scholar
• Vielma JP, Nemhauser GL (2011) Modeling disjunctive constraints with a logarithmic number of binary variables and constraints. Math. Programming 128(1):49–72.Crossref, 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