Building Formulations for Piecewise Linear Relaxations of Nonlinear Functions

References

• Ahmadi H, Martí JR, Moshref A (2013) Piecewise linear approximation of generators cost functions using max-affine functions. 2013 IEEE Power & Energy Soc. General Meeting (IEEE, Piscataway, NJ), 1–5.Crossref, Google Scholar
• Balas E (1975) Disjunctive programming: Cutting planes from logical conditions. Mangasarian OL, Meyer RR, Robinson SM, eds. Nonlinear Programming 2 (Academic Press, Cambridge, MA), 279–312.Crossref, Google Scholar
• Balas E (1979) Disjunctive programming. Hammer PL, Johnson EL, Korte BH, eds. Discrete Optimization II, Annals of Discrete Mathematics, vol. 5 (Elsevier, Amsterdam), 3–51.Crossref, Google Scholar
• Balas E (1998) Disjunctive programming: Properties of the convex hull of feasible points. Discrete Appl. Math. 89(1–3):3–44.Crossref, Google Scholar
• Beale EML, Tomlin JA (1970) Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables. Oper. Res. 69(447–454):99.Google Scholar
• Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4(1):238–252.Crossref, Google Scholar
• Bergamini ML, Aguirre P, Grossmann I (2005) Logic-based outer approximation for globally optimal synthesis of process networks. Comput. Chemical Engrg. 29(9):1914–1933.Crossref, Google Scholar
• Bergamini ML, Grossmann I, Scenna N, Aguirre P (2008) An improved piecewise outer-approximation algorithm for the global optimization of MINLP models involving concave and bilinear terms. Comput. Chemical Engrg. 32(3):477–493.Crossref, Google Scholar
• Bertsimas D, Mišić VV (2017) Robust product line design. Oper. Res. 65(1):19–37.Link, Google Scholar
• Bestuzheva K, Besançon M, Chen WK, Chmiela A, Donkiewicz T, van Doornmalen J, Eifler L, et al. (2021) The SCIP optimization suite 8.0. Preprint, submitted December 16, https://arxiv.org/abs/2112.08872.Google Scholar
• Bezanson J, Edelman A, Karpinski S, Shah VB (2017) Julia: A fresh approach to numerical computing. SIAM Rev. 59(1):65–98.Crossref, Google Scholar
• Bondy JA, Murty USR (2008) Graph Theory (Springer, London).Crossref, Google Scholar
• Braun K, Burlacu R (2023) A computational study for piecewise linear relaxations of mixed-integer nonlinear programs. Accessed December 3, 2024, https://optimization-online.org/2023/09/a-computational-study-for-piecewise-linear-relaxations-of-mixed-integer-nonlinear-programs.Google Scholar
• Camm JD, Cochran JJ, Curry DJ, Kannan S (2006) Conjoint optimization: An exact branch-and-bound algorithm for the share-of-choice problem. Management Sci. 52(3):435–447.Link, Google Scholar
• Camponogara E, Nazari LF (2015) Models and algorithms for optimal piecewise-linear function approximation. Math. Problems Engrg. 2015(1):876862.Crossref, Google Scholar
• Castillo Castillo PA, Castro PM, Mahalec V (2018) Global optimization of MIQCPs with dynamic piecewise relaxations. J. Global Optim. 71:691–716.Crossref, Google Scholar
• Castro PM (2015) Tightening piecewise McCormick relaxations for bilinear problems. Comput. Chemical Engrg. 72:300–311.Crossref, Google Scholar
• Castro PM (2016) Normalized multiparametric disaggregation: An efficient relaxation for mixed-integer bilinear problems. J. Global Optim. 64(4):765–784.Crossref, Google Scholar
• Codas A, Camponogara E (2012) Mixed-integer linear optimization for optimal lift-gas allocation with well-separator routing. Eur. J. Oper. Res. 217(1):222–231.Crossref, Google Scholar
• Codas A, Campos S, Camponogara E, Gunnerud V, Sunjerga S (2012) Integrated production optimization of oil fields with pressure and routing constraints: The Urucu field. Comput. Chemical Engrg. 46:178–189.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. https://doi.org/10.1007/s12532-024-00274-8.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
• Dai H, Izatt G, Tedrake R (2019) Global inverse kinematics via mixed-integer convex optimization. Internat. J. Robotics Res. 38(12–13):1420–1441.Crossref, Google Scholar
• D’Ambrosio C, Lodi A, Martello S (2010) Piecewise linear approximation of functions of two variables in MILP models. Oper. Res. Lett. 38(1):39–46.Crossref, Google Scholar
• Dantzig GB, Wolfe P (1960) Decomposition principle for linear programs. Oper. Res. 8(1):101–111.Link, Google Scholar
• de Farias IR, Zhao M Jr, 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 I, Kozyreff E, Gupta R, Zhao M (2013) Branch-and-cut for separable piecewise linear optimization and intersection with semi-continuous constraints. Math. Programming Comp. 5(1):75–112.Crossref, Google Scholar
• de la Torre P, Greenlaw R, Schäffer AA (1995) Optimal edge ranking of trees in polynomial time. Algorithmica 13(6):592–618.Crossref, Google Scholar
• Deits R, Tedrake R (2014) Footstep planning on uneven terrain with mixed-integer convex optimization. 2014 IEEE-RAS Internat. Conf. Humanoid Robots (IEEE, Piscataway, NJ), 279–286.Google Scholar
• Dong H, Du Z (2015) Obstacle avoidance path planning of planar redundant manipulators using workspace density. Internat. J. Adv. Robotic Systems 12(2):9.Crossref, Google Scholar
• Dunning I, Huchette J, Lubin M (2017) JuMP: A modeling language for mathematical optimization. SIAM Rev. 59(2):295–320.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, The IMA Volumes in Mathematics and Its Applications, vol. 154 (Springer, New York), 287–314.Crossref, Google Scholar
• Gurobi Optimization, LLC (2023) Gurobi optimizer reference manual. https://www.gurobi.com.Google Scholar
• He T, Tawarmalani M (2021) A new framework to relax composite functions in nonlinear programs. Math. Programming 190:427–466.Crossref, Google Scholar
• He T, Tawarmalani M (2022) Tractable relaxations of composite functions. Math. Oper. Res. 47(2):1110–1140.Link, Google Scholar
• He T, Tawarmalani M (2024) MIP relaxations in factorable programming. SIAM J. Optim. 34(3):2856–2882.Crossref, Google Scholar
• Huchette J, Vielma JP (2019) A combinatorial approach for small and strong formulations of disjunctive constraints. Math. Oper. Res. 44(3):793–820.Link, 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
• Iyer AV, Ratliff HD, Vijayan G (1991) On an edge ranking problem of trees and graphs. Discrete Appl. Math. 30(1):43–52.Crossref, Google Scholar
• Jeroslow RG, Lowe JK (1984) Modelling with integer variables. Korte B, Ritter K, eds. Mathematical Programming at Oberwolfach II, Mathematical Programming Studies, vol. 22 (Springer, Berlin, Heidelberg), 167–184.Crossref, Google Scholar
• Jeroslow RG, Lowe JK (1985) Experimental results on the new techniques for integer programming formulations. J. Oper. Res. Soc. 36(5):393–403.Crossref, Google Scholar
• Keha AB, de Farias IR Jr, 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 Jr, 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
• Kim J, Richard JPP, Tawarmalani M (2024) Piecewise polyhedral relaxations of multilinear optimization. SIAM J. Optim. 34(4):3167–3193.Crossref, Google Scholar
• Kucuk S, Bingul Z (2006) Robot Kinematics: Forward and Inverse Kinematics (INTECH Open Access Publisher, London).Google Scholar
• Lam TW, Yue FL (2001) Optimal edge ranking of trees in linear time. Algorithmica 30(1):12–33.Crossref, Google Scholar
• Lyu B, Hicks IV (2023) Maximal clique and edge-ranking bounds of biclique cover number. Preprint, submitted February 24, https://arxiv.org/abs/2302.12775.Google Scholar
• Lyu B, Hicks IV, Huchette J (2024) Modeling combinatorial disjunctive constraints via junction trees. Math. Programming 204:385–413.Google Scholar
• McCormick GP (1976) Computability of global solutions to factorable nonconvex programs: Part I—Convex underestimating problems. Math. Programming 10(1):147–175.Crossref, Google Scholar
• Minkowski H (1897) Allgemeine lehrsatze uber die konvexen polyeder. Nachr. Ges. Wiss. Gottingen, Math.-Phys. KL. 1897(1897):198–219.Google Scholar
• Misener R, Floudas CA (2012) Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations. Math. Programming 136(1):155–182.Crossref, Google Scholar
• Misener R, Thompson JP, Floudas CA (2011) APOGEE: Global optimization of standard, generalized, and extended pooling problems via linear and logarithmic partitioning schemes. Comput. Chemical Engrg. 35(5):876–892.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 (1998) Computational Geometry in C, 2nd ed. (Cambridge University Press, Cambridge, UK).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
• 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
• Silva TL, Camponogara E (2014) A computational analysis of multidimensional piecewise-linear models with applications to oil production optimization. Eur. J. Oper. Res. 232(3):630–642.Crossref, 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
• Sundar K, Nagarajan H, Linderoth J, Wang S, Bent R (2021) Piecewise polyhedral formulations for a multilinear term. Oper. Res. Lett. 49(1):144–149.Crossref, Google Scholar
• Trindade RS, d’Ambrosio C, Frangioni A, Gentile C (2023) Comparing perspective reformulations for piecewise-convex optimization. Oper. Res. Lett. 51(6):702–708.Crossref, Google Scholar
• Vielma JP (2018) Embedding formulations and complexity for unions of polyhedra. Management Sci. 64(10):4721–4734.Link, 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
• Wang X, Camm JD, Curry DJ (2009) A branch-and-price approach to the share-of-choice product line design problem. Management Sci. 55(10):1718–1728.Link, Google Scholar
• Weyl H (1934) Elementare theorie der konvexen polyeder. Commentarii Math. Helvetici 7(1):290–306.Crossref, Google Scholar
• Yahya S, Moghavvemi M, Mohamed HA (2011) Geometrical approach of planar hyper-redundant manipulators: Inverse kinematics, path planning and workspace. Simulation Modeling Practice Theory 19(1):406–422.Crossref, Google Scholar
• Zhou X, Nishizeki T (1995) Finding optimal edge-rankings of trees. Proc. Sixth Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 122–131.Google Scholar