Recursive McCormick Linearization of Multilinear Programs

References

• Achterberg T, Towle E (2020) Non-convex quadratic optimization webinar. Accessed November 15, 2024, https://www.gurobi.com/events/non-convex-quadratic-optimization/.Google Scholar
• Anthony M, Boros E, Crama Y, Gruber A (2016) Quadratization of symmetric pseudo-Boolean functions. Discrete Appl. Math. 203:1–12.Crossref, Google Scholar
• Anthony M, Boros E, Crama Y, Gruber A (2017) Quadratic reformulations of nonlinear binary optimization problems. Math. Programming 162:115–144.Crossref, Google Scholar
• Bao X, Sahinidis NV, Tawarmalani M (2009) Multiterm polyhedral relaxations for nonconvex, quadratically constrained quadratic programs. Optim. Methods Software 24(4–5):485–504.Crossref, Google Scholar
• Bao X, Khajavirad A, Sahinidis NV, Tawarmalani M (2015) Global optimization of nonconvex problems with multilinear intermediates. Math. Programming Comput. 7(1):1–37.Crossref, Google Scholar
• Bernasconi J (1987) Low autocorrelation binary sequences: Statistical mechanics and configuration space analysis. J. Physique France 48(4):559–567.Crossref, Google Scholar
• Boros E, Hammer PL (2002) Pseudo-Boolean optimization. Discrete Appl. Math. 123(1–3):155–225.Crossref, Google Scholar
• Boros E, Crama Y, Rodríguez-Heck E (2020) Compact quadratizations for pseudo-Boolean functions. J. Combin. Optim. 39:687–707.Crossref, Google Scholar
• Boros E, Hammer PL, Minoux M, Rader Jr DJ (1999) Optimal cell flipping to minimize channel density in VLSI design and pseudo-Boolean optimization. Discrete Appl. Math. 90(1–3):69–88.Crossref, Google Scholar
• Buchheim C, Rinaldi G (2008) Efficient reduction of polynomial zero-one optimization to the quadratic case. SIAM J. Optim. 18(4):1398–1413.Crossref, Google Scholar
• Buss JF, Goldsmith J (1993) Nondeterminism within P*. SIAM J. Comput. 22(3):560–572.Crossref, Google Scholar
• Cardonha C, Raghunathan AU, Bergman D, Nohra CJ (2024) Recursive McCormick linearization of multilinear programs. http://dx.doi.org/10.1287/ijoc.2023.0390.cd, https://github.com/INFORMSJoC/2023.0390.Google Scholar
• Crama Y, Rodríguez-Heck E (2017) A class of valid inequalities for multilinear 0–1 optimization problems. Discrete Optim. 25:28–47.Crossref, Google Scholar
• Crama Y, Elloumi S, Lambert A, Rodriguez-Heck E (2022) Quadratization and convexification in polynomial binary optimization. HAL Open Science. Accessed November 15, 2024, https://hal.science/hal-03795395.Google Scholar
• Dalkiran E, Ghalami L (2018) On linear programming relaxations for solving polynomial programming problems. Comput. Oper. Res. 99:67–77.Crossref, Google Scholar
• Dalkiran E, Sherali HD (2016) RLT-POS: Reformulation-linearization technique-based optimization software for solving polynomial programming problems. Math. Programming Comput. 8(3):337–375.Crossref, Google Scholar
• Del Pia A, Khajavirad A (2021) The running intersection relaxation of the multilinear polytope. Math. Oper. Res. 46(3):1008–1037.Link, Google Scholar
• Del Pia A, Khajavirad A, Sahinidis NV (2020) On the impact of running intersection inequalities for globally solving polynomial optimization problems. Math. Programming Comput. 12(2):165–191.Crossref, Google Scholar
• Elloumi S, Verchère Z (2023) Efficient linear reformulations for binary polynomial optimization problems. Comput. Oper. Res. 155:106240.Crossref, Google Scholar
• Elloumi S, Lambert A, Lazare A (2021) Solving unconstrained 0-1 polynomial programs through quadratic convex reformulation. J. Global Optim. 80(2):231–248.Crossref, Google Scholar
• Garey MR, Johnson DS (1979) Computers and Intractability, vol. 174 (Freeman, San Francisco).Google Scholar
• Glover F, Woolsey E (1974) Converting the 0-1 polynomial programming problem to a 0-1 linear program. Oper. Res. 22(1):180–182.Link, Google Scholar
• Gurobi Optimization, LLC (2022) Gurobi optimizer reference manual. Accessed November 15, 2024, https://www.gurobi.com.Google Scholar
• Hart WE, Laird CD, Watson JP, Woodruff DL, Hackebeil GA, Nicholson BL, Siirola JD (2017) Pyomo-Optimization Modeling in Python, vol. 67 (Springer, Berlin), 277.Crossref, Google Scholar
• IBM (2022) IBM ILOG CPLEX 22.1.1 user’s manual. Accessed November 15, 2024, https://www.ibm.com/docs/en/icos/22.1.1?topic=optimizers-users-manual-cplex.Google Scholar
• Jakob K, Pruzan PM (1983) The simple plant location problem: Survey and synthesis. Eur. J. Oper. Res. 12(1):36–81.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
• Khajavirad A (2023) On the strength of recursive McCormick relaxations for binary polynomial optimization. Oper. Res. Lett. 51(2):146–152.Crossref, Google Scholar
• Khajavirad A, Sahinidis NV (2018) A hybrid LP/NLP paradigm for global optimization relaxations. Math. Programming Comput. 10(3):383–421.Crossref, Google Scholar
• Kılınç MR, Sahinidis NV (2018) Exploiting integrality in the global optimization of mixed-integer nonlinear programming problems with BARON. Optim. Methods Software 33(3):540–562.Crossref, Google Scholar
• Kim J, Richard JPP, Tawarmalani M (2024) Piecewise polyhedral relaxations of multilinear optimization. SIAM J. Optim. 34(4):3167–3193.Google Scholar
• Lasserre JB (2001) Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3):796–817.Crossref, 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, 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
• Padberg M (1989) The Boolean quadric polytope: Some characteristics, facets and relatives. Math. Programming 45:139–172.Crossref, Google Scholar
• Rodríguez-Heck E (2019) Linear and quadratic reformulations of nonlinear optimization problems in binary variables. 4OR-Q J. Oper. Res. 17:221–222.Google Scholar
• Ryoo HS, Sahinidis NV (2001) Analysis of bounds for multilinear functions. J. Global Optim. 19:403–424.Crossref, Google Scholar
• Sherali HD, Alameddine A (1992) A new reformulation-linearization technique for bilinear programming problems. J. Global Optim. 2:379–410.Crossref, Google Scholar
• Sherali HD, Fraticelli BM (2002) Enhancing RLT relaxations via a new class of semidefinite cuts. J. Global Optim. 22:233–261. Crossref, Google Scholar
• Sherali HD, Wang H (2001) Global optimization of nonconvex factorable programming problems. Math. Programming 89:459–478.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
• 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
• Verma A, Lewis M (2020) Optimal quadratic reformulations of fourth degree pseudo-Boolean functions. Optim. Lett. 14:1557–1569.Crossref, Google Scholar
• Zorn K, Sahinidis NV (2014) Global optimization of general nonconvex problems with intermediate polynomial substructures. J. Global Optim. 59:673–693.Crossref, Google Scholar