Spatial Branch-and-Bound for Nonconvex Separable Piecewise Linear Optimization

References

• Achterberg T, Koch T, Martin A (2005) Branching rules revisited. Oper. Res. Lett. 33(1):42–54.Crossref, Google Scholar
• Adams W, Gupte A, Xu Y (2019) Error bounds for monomial convexification in polynomial optimization. Math. Programming 175(1–2):355–393.Crossref, Google Scholar
• Adjiman CS, Dallwig S, Floudas CA, Neumaier A (1998) A global optimization method, αBB, for general twice-differentiable constrained NLPs—I. Theoretical advances. Comput. Chemical Engrg. 22(9):1137–1158.Crossref, Google Scholar
• Al-Khayyal FA, Sherali HD (2000) On finitely terminating branch-and-bound algorithms for some global optimization problems. SIAM J. Optim. 10(4):1049–1057.Crossref, Google Scholar
• Barber CB, Dobkin DP, Huhdanpaa H (1996) The quickhull algorithm for convex hulls. ACM Trans. Math. Software 22(4):469–483.Crossref, Google Scholar
• Bärmann A, Burlacu R, Hager L, Kleinert T (2023) On piecewise linear approximations of bilinear terms: Structural comparison of univariate and bivariate mixed-integer programming formulations. J. Global Optim. 85(4):789–819.Crossref, Google Scholar
• Beach B, Hildebrand R, Huchette J (2022) Compact mixed-integer programming formulations in quadratic optimization. J. Global Optim. 84(4):869–912.Crossref, Google Scholar
• Beale E, Forrest JJ (1976) Global optimization using special ordered sets. Math. Programming 10(1):52–69.Crossref, Google Scholar
• Benson HP (1990) Separable concave minimization via partial outer approximation and branch and bound. Oper. Res. Lett. 9(6):389–394.Crossref, Google Scholar
• Burer S, Letchford AN (2012) Non-convex mixed-integer nonlinear programming: A survey. Surveys Oper. Res. Management Sci. 17(2):97–106.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 Software 35(1):37–64.Crossref, Google Scholar
• Casado LG, Martínez JA, García I, Sergeyev YD (2003) New interval analysis support functions using gradient information in a global minimization algorithm. J. Global Optim. 25(4):345–362. Crossref, Google Scholar
• Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to Algorithms (MIT Press, Cambridge, MA).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
• Croxton KL, Gendron B, Magnanti TL (2007) Variable disaggregation in network flow problems with piecewise linear costs. Oper. Res. 55(1):146–157.Link, Google Scholar
• D’Ambrosio C, Lee J, Skipper D, Thomopulos D (2020) Handling separable non-convexities using disjunctive cuts. Baiou, M Gendron B, Gunluk O, Mahjoub A, eds. Combinatorial Optimization: ISCO 2020, Lecture Notes in Computer Science, vol. 12176 (Springer, Cham, Switzerland), 102–114.Crossref, Google Scholar
• Dantzig GB (1960) On the significance of solving linear programming problems with some integer variables. Econometrica 28(1):30–44.Crossref, Google Scholar
• de Farias IR Jr, Zhao M, Zhao H (2008) A special ordered set approach for optimizing a discontinuous separable piecewise linear function. Oper. Res. Lett. 36(2):234–238.Crossref, Google Scholar
• de Farias IR, Kozyreff E, Gupta R, Zhao M (2013) Branch-and-cut for separable piecewise linear optimization and intersection with semi-continuous constraints. Math. Programming Comput. 5(1):75–112.Crossref, Google Scholar
• Dey SS, Gupte A (2015) Analysis of MILP techniques for the pooling problem. Oper. Res. 63(2):412–427.Link, Google Scholar
• Duguet A, Ngueveu SU (2022) Piecewise linearization of bivariate nonlinear functions: Minimizing the number of pieces under a bounded approximation error. Ljubíc I, Barahona F, Dey SS, Mahjoub AR, eds. Combinatorial Optimization: ISCO 2022, Lecture Notes in Computer Science, vol. 13526 (Springer, Cham, Switzerland), 117–129.Crossref, Google Scholar
• Falk JE, Soland RM (1969) An algorithm for separable nonconvex programming problems. Management Sci. 15(9):550–569.Link, Google Scholar
• Feijoo B, Meyer R (1988) Piecewise-linear approximation methods for nonseparable convex optimization. Management Sci. 34(3):411–419.Link, Google Scholar
• Fourer R (1985) A simplex algorithm for piecewise-linear programming I: Derivation and proof. Math. Programming 33(2):204–233.Crossref, 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.Crossref, Google Scholar
• Füllner C, Rebennack S (2022) Non-convex nested Benders decomposition. Math. Programming 196(1):987–1024.Crossref, Google Scholar
• Geisler B, Martin A, Morsi A, Schewe L (2012) Using piecewise linear functions for solving MINLPs. Lee J, Leyffer S, eds. Mixed Integer Nonlinear Programming, IMA Volumes in Mathematics and Its Applications, vol. 154 (Springer, Cham, Switzerland), 287–314.Crossref, Google Scholar
• Ghaddar B, Gómez-Casares I, González-Díaz J, González-Rodríguez B, Pateiro-López B, Rodríguez-Ballesteros S (2023) Learning for spatial branching: An algorithm selection approach. INFORMS J. Comput. 35(5):1024–1043.Link, Google Scholar
• Gorissen BL (2022) Interior point methods can exploit structure of convex piecewise linear functions with application in radiation therapy. SIAM J. Optim. 32(1):256–275.Crossref, Google Scholar
• Gounaris CE, Floudas CA (2008) Tight convex underestimators for C2-continuous functions: I. Univariate functions. J. Global Optim. 42(1):51–67.Crossref, Google Scholar
• Graham RL (1972) An efficient algorithm for determining the convex hull of a finite planar set. Inform. Processing Lett. 1(4):132–133.Crossref, Google Scholar
• Grimstad B, Knudsen BR (2020) Mathematical programming formulations for piecewise polynomial functions. J. Global Optim. 77(3):455–486.Crossref, Google Scholar
• Gupte A, Koster AM, Kuhnke S (2022) An adaptive refinement algorithm for discretizations of nonconvex QCQP. Schulz C, Ucar B, eds. 20th International Symposium on Experimental Algorithms: SEA 2022, Leibniz International Proceedings in Informatics (LIPIcs), vol. 233 (Schloss Dagstuhl Publishing, Wadern, Germany), 24:1–24:14.Google Scholar
• Gurobi Optimization (2024) Documentation—General constraints. https://www.gurobi.com/documentation/current/refman/general_constraints.html.Google Scholar
• Horst R (1986) A general class of branch-and-bound methods in global optimization with some new approaches for concave minimization. J. Optim. Theory Appl. 51(2):271–291.Crossref, Google Scholar
• Hübner T, Gupte A, Rebennack S (2025) Spatial branch and bound for nonconvex separable piecewise linear optimization. https://github.com/INFORMSJoC/2024.0755.Google Scholar
• Huchette J, Vielma JP (2023) Nonconvex piecewise linear functions: Advanced formulations and simple modeling tools. Oper. Res. 71(5):1835–1856.Link, Google Scholar
• Keha AB, de Farias IR, Nemhauser GL (2004) Models for representing piecewise linear cost functions. Oper. Res. Lett. 32(1):44–48.Crossref, Google Scholar
• Keha AB, de Farias IR, Nemhauser GL (2006) A branch-and-cut algorithm without binary variables for nonconvex piecewise linear optimization. Oper. Res. 54(5):847–858.Link, Google Scholar
• Kesavan P, Allgor RJ, Gatzke EP, Barton PI (2004) Outer approximation algorithms for separable nonconvex mixed-integer nonlinear programs. Math. Programming 100(3):517–535.Crossref, Google Scholar
• Kim J, Richard J-PP, Tawarmalani M (2024) Piecewise polyhedral relaxations of multilinear optimization. SIAM J. Optim. 34(4):3167–3193.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
• Kontogiorgis S (2000) Practical piecewise-linear approximation for monotropic optimization. INFORMS J. Comput. 12(4):324–340.Link, Google Scholar
• Leyffer S, Sartenaer A, Wanufelle E (2008) Branch-and-refine for mixed-integer nonconvex global optimization. Working Paper No. ANL/MCS-P1547-0908, Mathematics and Computer Science Division, Argonne National Laboratory, Lemont, IL.Google Scholar
• Locatelli M, Schoen F (2013) Global Optimization: Theory, Algorithms, and Applications, MOS-SIAM Series on Optimization, vol. MO15 (SIAM, Philadelphia).Crossref, Google Scholar
• Lyu B, Hicks IV, Huchette J (2025) Building formulations for piecewise linear relaxations of nonlinear functions. Oper. Res., ePub ahead of print April 24, https://doi.org/10.1287/opre.2023.0187.Google Scholar
• Magnanti TL, Stratila D (2004) Separable concave optimization approximately equals piecewise linear optimization. Bienstock D, Nemhauser G, eds. Integer Programming and Combinatorial Optimization: IPCO 2004, Lecture Notes in Computer Science, vol. 3064 (Springer, Berlin), 234–243.Crossref, Google Scholar
• Markowitz HM, Manne AS (1957) On the solution of discrete programming problems. Econometrica 25(1):84–110.Crossref, Google Scholar
• Meyer RR (1976) Mixed integer minimization models for piecewise-linear functions of a single variable. Discrete Math. 16(2):163–171.Crossref, 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. Global Optim. 74(4):639–675.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
• Posypkin M, Usov A, Khamisov O (2020) Piecewise linear bounding functions in univariate global optimization. Soft Comput. 24(23):17631–17647.Crossref, Google Scholar
• Rebennack S (2016) 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
• 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
• Rebennack S, Nahapetyan A, Pardalos PM (2009) Bilinear modeling solution approach for fixed charge network flow problems. Optim. Lett. 3(3):347–355.Crossref, Google Scholar
• Shectman JP, Sahinidis NV (1998) A finite algorithm for global minimization of separable concave programs. J. Global Optim. 12(1):1–36. Crossref, Google Scholar
• 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
• Soland RM (1971) An algorithm for separable nonconvex programming problems II: Nonconvex constraints. Management Sci. 17(11):759–773.Link, Google Scholar
• Sundar K, Sanjeevi S, Nagarajan H (2022) Sequence of polyhedral relaxations for nonlinear univariate functions. Optim. Engrg. 23(2):877–894.Crossref, Google Scholar
• Tawarmalani M, Sahinidis NV (2004) Global optimization of mixed-integer nonlinear programs: A theoretical and computational study. Math. Programming 99(3):563–591.Crossref, Google Scholar
• Thakur LS (1978) Error analysis for convex separable programs: The piecewise linear approximation and the bounds on the optimal objective value. SIAM J. Appl. Math. 34(4):704–714.Crossref, Google Scholar
• Toriello A, Vielma JP (2012) Fitting piecewise linear continuous functions. Eur. J. Oper. Res. 219(1):86–95.Crossref, Google Scholar
• Tuy H (2016) Convex Analysis and Global Optimization, 2nd ed., Springer Optimization and Its Applications, vol. 110 (Springer, Cham, Switzerland).Crossref, Google Scholar
• Tuy H, Horst R (1988) Convergence and restart in branch-and-bound algorithms for global optimization. Application to concave minimization and D.C. Optimization problems. Math. Programming 41(1):161–183.Crossref, Google Scholar
• 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
• 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
• Vielma JP, Keha AB, Nemhauser GL (2008) Nonconvex, lower semicontinuous piecewise linear optimization. Discrete Optim. 5(2):467–488.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 (2024) Efficient continuous piecewise linear regression for linearising univariate non-linear functions. IISE Trans. 57(3):231–245.Crossref, Google Scholar
• Wechsung A, Barton PI (2014) Global optimization of bounded factorable functions with discontinuities. J. Global Optim. 58(1):1–30.Crossref, Google Scholar
• Yıldız S, Vielma JP (2013) Incremental and encoding formulations for mixed integer programming. Oper. Res. Lett. 41(6):654–658.Crossref, Google Scholar
• Zhao M, de Farias IR Jr (2013) The piecewise linear optimization polytope: New inequalities and intersection with semi-continuous constraints. Math. Programming 141(1–2):217–255.Crossref, Google Scholar