Strong Partitioning and a Machine Learning Approximation for Accelerating the Global Optimization of Nonconvex Quadratically Constrained Quadratic Programs

References

• Achterberg T (2007) Constraint integer programming. PhD thesis, TU Berlin, Berlin.Google Scholar
• Al-Khayyal FA, Falk JE (1983) Jointly constrained biconvex programming. Math. Oper. Res. 8(2):273–286.Link, Google Scholar
• Alvarez AM, Louveaux Q, Wehenkel L (2017) A machine learning-based approximation of strong branching. INFORMS J. Comput. 29(1):185–195.Link, Google Scholar
• Baltean-Lugojan R, Bonami P, Misener R, Tramontani A (2019) Scoring positive semidefinite cutting planes for quadratic optimization via trained neural networks. Optim. Online (November 26), https://optimization-online.org/2018/11/6943/.Google Scholar
• Bao X, Sahinidis NV, Tawarmalani M (2011) Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons. Math. Programming 129(1):129–157.Crossref, Google Scholar
• Bengio Y, Lodi A, Prouvost A (2021) Machine learning for combinatorial optimization: A methodological tour d’horizon. Eur. J. Oper. Res. 290(2):405–421.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
• Bestuzheva K, Besançon M, Chen W-K, Chmiela A, Donkiewicz T, van Doornmalen J, Eifler L, et al. (2021) The SCIP optimization suite 8.0. Preprint, submitted December 16, https://doi.org/10.48550/arXiv.2112.08872.Google Scholar
• Bienstock D, Escobar M, Gentile C, Liberti L (2022) Mathematical programming formulations for the alternating current optimal power flow problem. Ann. Oper. Res. 314(1):277–315.Crossref, Google Scholar
• Billionnet A, Elloumi S, Lambert A (2012) Extending the QCR method to general mixed-integer programs. Math. Programming 131(1):381–401.Crossref, Google Scholar
• Bonami P, Lodi A, Zarpellon G (2018) Learning a classification of mixed-integer quadratic programming problems. van Hoeve WJ, ed. Internat. Conf. Integration Constraint Programming Artificial Intelligence Oper. Res. (Springer, Cham, Switzerland), 595–604.Google Scholar
• Breiman L, Friedman JH, Olshen RA, Stone CJ (2017) Classification and Regression Trees (Routledge, Milton Park, UK).Crossref, Google Scholar
• Burer S, Vandenbussche D (2008) A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Math. Programming 113(2):259–282.Crossref, Google Scholar
• Cappart Q, Chételat D, Khalil EB, Lodi A, Morris C, Veličković P (2023) Combinatorial optimization and reasoning with graph neural networks. J. Machine Learn. Res. 24(130):1–61.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
• Cengil F, Nagarajan H, Bent R, Eksioglu S, Eksioglu B (2022) Learning to accelerate globally optimal solutions to the AC optimal power flow problem. Electric Power Systems Res. 212:108275.Crossref, Google Scholar
• De Wolf D, Smeers Y (2021) Generalized derivatives of the optimal value of a linear program with respect to matrix coefficients. Eur. J. Oper. Res. 291(2):491–496.Crossref, Google Scholar
• Di Liberto G, Kadioglu S, Leo K, Malitsky Y (2016) DASH: Dynamic approach for switching heuristics. Eur. J. Oper. Res. 248(3):943–953.Crossref, Google Scholar
• Drucker H (1997) Improving regressors using boosting techniques. ICML‘97 Proc. Fourteenth Internat. Conf. Machine Learn., vol. 97 (Morgan Kaufmann Publishers Inc., San Francisco), 107–115.Google Scholar
• Freund Y, Schapire RE (1997) A decision-theoretic generalization of on-line learning and an application to boosting. J. Comput. System Sci. 55(1):119–139.Crossref, Google Scholar
• Furini F, Traversi E, Belotti P, Frangioni A, Gleixner A, Gould N, Liberti L, et al. (2019) QPLIB: A library of quadratic programming instances. Math. Programming Comput. 11:237–265.Crossref, Google Scholar
• Gasse M, Chételat D, Ferroni N, Charlin L, Lodi A (2019) Exact combinatorial optimization with graph convolutional neural networks. Adv. Neural Inform. Processing Systems, vol. 32 (Curran Associates Inc., Red Hook, NY). 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
• González-Rodríguez B, Alvite-Pazó R, Alvite-Pazó S, Ghaddar B, González-Díaz J (2022) Polynomial optimization: Enhancing RLT relaxations with conic constraints. Preprint, submitted August 11, https://doi.org/10.48550/arXiv.2208.05608.Google Scholar
• He H, Daume H III, Eisner JM (2014) Learning to search in branch and bound algorithms. Adv. Neural Inform. Processing Systems 27:3293–3301.Google Scholar
• Im J (2018) Sensitivity analysis and robust optimization: A geometric approach for the special case of linear optimization. Master’s thesis, University of Waterloo, Waterloo, ON, Canada.Google Scholar
• Jungen D, Zingler A, Djelassi H, Mitsos A (2023) libDIPS—Discretization-based semi-infinite and bilevel programming solvers. Optim. Online (December 4), https://optimization-online.org/?p=24914.Google Scholar
• Kannan R (2018) Algorithms, analysis and software for the global optimization of two-stage stochastic programs. PhD thesis, Massachusetts Institute of Technology, Cambridge.Google Scholar
• Kannan R, Barton PI (2017) The cluster problem in constrained global optimization. J. Global Optim. 69(3):629–676.Crossref, Google Scholar
• Kannan R, Barton PI (2018) Convergence-order analysis of branch-and-bound algorithms for constrained problems. J. Global Optim. 71(4):753–813.Crossref, Google Scholar
• Kannan R, Nagarajan H, Deka D (2025) Strong partitioning and a machine learning approximation for accelerating the global optimization of nonconvex QCQPs. https://doi.org/10.1287/ijoc.2023.0424.cd, https://github.com/INFORMSJoC/2023.0424.Google Scholar
• Khalil E, Le Bodic P, Song L, Nemhauser G, Dilkina B (2016) Learning to branch in mixed integer programming. Proc. AAAI Conf. Artificial Intelligence, vol. 30 (AAAI Press, Palo Alto, CA), 724–731.Google Scholar
• Kim J, Richard J-PP, Tawarmalani M (2024) Piecewise polyhedral relaxations of multilinear optimization. SIAM J. Optim. 34(4):3167–3193.Crossref, Google Scholar
• Koopmans TC, Beckmann M (1957) Assignment problems and the location of economic activities. Econometrica 25(1):53–76.Crossref, Google Scholar
• Lee M, Ma N, Yu G, Dai H (2021) Accelerating generalized Benders decomposition for wireless resource allocation. IEEE Trans. Wireless Comm. 20(2):1233–1247.Crossref, Google Scholar
• Liu J, Ploskas N, Sahinidis NV (2019) Tuning BARON using derivative-free optimization algorithms. J. Global Optim. 74(4):611–637.Crossref, Google Scholar
• Lodi A, Zarpellon G (2017) On learning and branching: A survey. TOP 25(2):207–236.Crossref, Google Scholar
• Lu M, Nagarajan H, Bent R, Eksioglu SD, Mason SJ (2018) Tight piecewise convex relaxations for global optimization of optimal power flow. 2018 Power Systems Comput. Conf. (IEEE, Piscataway, NJ), 1–7.Google Scholar
• Luedtke J, D’Ambrosio C, Linderoth J, Schweiger J (2020) Strong convex nonlinear relaxations of the pooling problem. SIAM J. Optim. 30(2):1582–1609.Crossref, Google Scholar
• Mäkelä MM (2003) Multiobjective proximal bundle method for nonconvex nonsmooth optimization: Fortran subroutine MPBNGC 2.0. Reports of the Department of Mathematical Information Technology, Series B. Scientific Computing B 13/2003, University of Jyväskylä, Jyväskylä, 1–18.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
• Misener R, Floudas CA (2013) GloMIQO: Global mixed-integer quadratic optimizer. J. Global Optim. 57(1):3–50.Crossref, Google Scholar
• Misener R, Floudas CA (2014) ANTIGONE: Algorithms for continuous/integer global optimization of nonlinear equations. J. Global Optim. 59(2):503–526.Crossref, Google Scholar
• Nagarajan H, Lu M, Yamangil E, Bent R (2016) Tightening McCormick relaxations for nonlinear programs via dynamic multivariate partitioning. Rueher M, ed. 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. Global Optim. 74(4):639–675.Crossref, Google Scholar
• Nair V, Bartunov S, Gimeno F, von Glehn I, Lichocki P, Lobov I, O’Donoghue B, et al. (2020) Solving mixed integer programs using neural networks. Preprint, submitted July 29, https://doi.org/10.48550/arXiv.2012.13349.Google Scholar
• Nannicini G, Belotti P, Lee J, Linderoth J, Margot F, Wächter A (2011) A probing algorithm for MINLP with failure prediction by SVM. Achterberg T, ed. Internat. Conf. AI Techniques Constriant Programming Combin. Optim. Problems (Springer, Berlin, Heidelberg), 154–169.Google Scholar
• Nohra CJ, Raghunathan AU, Sahinidis N (2021) Spectral relaxations and branching strategies for global optimization of mixed-integer quadratic programs. SIAM J. Optim. 31(1):142–171.Crossref, Google Scholar
• Nohra CJ, Raghunathan AU, Sahinidis NV (2022) SDP-quality bounds via convex quadratic relaxations for global optimization of mixed-integer quadratic programs. Math. Programming 196(1):203–233.Crossref, Google Scholar
• Pardalos PM, Vavasis SA (1991) Quadratic programming with one negative eigenvalue is NP-hard. J. Global Optim. 1(1):15–22.Crossref, Google Scholar
• Pedregosa F, Varoquaux G, Gramfort A, Michel V, Thirion B, Grisel O, Blondel M, et al. (2011) Scikit-learn: Machine learning in Python. J. Machine Learn. Res. 12(85):2825–2830.Google Scholar
• Sahinidis NV (1996) BARON: A general purpose global optimization software package. J. Global Optim. 8(2):201–205.Crossref, Google Scholar
• Saif Y, Elkamel A, Pritzker M (2008) Global optimization of reverse osmosis network for wastewater treatment and minimization. Indust. Engrg. Chemistry Res. 47(9):3060–3070.Crossref, Google Scholar
• Sherali HD, Adams WP (2013) A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems, vol. 31 (Springer Science & Business Media, New York).Google Scholar
• Shor NZ (1987) Quadratic optimization problems. Soviet J. Comput. Systems Sci. 25:1–11.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
• Wicaksono DS, Karimi IA (2008) Piecewise MILP under- and overestimators for global optimization of bilinear programs. AIChE J. 54(4):991–1008.Crossref, Google Scholar
• Yang Y, Barton PI (2016) Integrated crude selection and refinery optimization under uncertainty. AIChE J. 62(4):1038–1053.Crossref, Google Scholar