Volume Formulae for the Convex Hull of the Graph of a Trilinear Monomial: A Complete Characterization for General Box Domains

References

• 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.Google Scholar
• Avis D, Devroye L (2026) On the volume of the elliptope and related metric polytopes. Preprint, submitted April 17, https://arxiv.org/abs/2604.16735.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 Software 24(4–5):597–634.Google Scholar
• Bestuzheva K, Chmiela A, Müller B, Serrano F, Vigerske S, Wegscheider F (2025) Global optimization of mixed-integer nonlinear programs with SCIP 8. J. Global Optim. 91(2):287–310.Google Scholar
• Burer S, Letchford AN (2012) Non-convex mixed-integer nonlinear programming: A survey. Surveys Oper. Res. Management Sci. 17(2):97–106.Google Scholar
• Cafieri S, Lee J, Liberti L (2010) On convex relaxations of quadrilinear terms. J. Global Optim. 47(4):661–685.Google Scholar
• Cafieri S, Hansen P, Létocart L, Liberti L, Messine F (2012) Compact relaxations for polynomial programming problems. Klasing R, ed. Experimental Algorithms. SEA 2012, Lecture Notes in Computer Science, vol. 7276 (Springer, Berlin), 75–86.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
• Jach M, Michaels D, Weismantel R (2008) The convex envelope of-convex functions. SIAM J. Optim. 19(3):1451–1466.Google Scholar
• Khajavirad A (2023) On the strength of recursive McCormick relaxations for binary polynomial optimization. Oper. Res. Lett. 51(2):146–152.Google Scholar
• Ko CW, Lee J, Steingrímsson E (1997) The volume of relaxed Boolean-quadric and cut polytopes. Discrete Math. 163(1):293–298.Google Scholar
• Kronqvist J, Bernal Neira DE, Grossmann IE (2026) 50 years of mixed-integer nonlinear and disjunctive programming. Eur. J. Oper. Res. 331(3):687–705.Google Scholar
• Lasserre JB, Zeron ES (2001) A new algorithm for the volume of a convex polytope. J. ACM 48(6):1126–1140.Google Scholar
• Lawrence J (1991) Polytope volume computation. Math. Comput. 57(195):259–271.Google Scholar
• Lee J, Morris WD (1994) Geometric comparison of combinatorial polytopes. Discrete Appl. Math. 55(2):163–182.Google Scholar
• Lee J, Skipper D, Speakman E (2018) Algorithmic and modeling insights via volumetric comparison of polyhedral relaxations. Math. Programming 170(1):121–140.Google Scholar
• Lee J, Skipper D, Speakman E (2022) Gaining or losing perspective. J. Global Optim. 82(4):835–862.Google Scholar
• Lee J, Skipper D, Speakman E, Xu L (2023) Gaining or losing perspective for piecewise-linear under-estimators of convex univariate functions. J. Optim. Theory Appl. 196(1):1–35.Google Scholar
• Luedtke J, Namazifar M, Linderoth J (2012) Some results on the strength of relaxations of multilinear functions. Math. Programming 136(2):325–351.Google Scholar
• McCormick GP (1976) Computability of global solutions to factorable nonconvex programs: Part I—Convex underestimating problems. Math. Programming 10(1):147–175.Google Scholar
• Meyer CA, Floudas CA (2004a) Trilinear monomials with mixed sign domains: Facets of the convex and concave envelopes. J. Global Optim. 29(2):125–155.Google Scholar
• Meyer CA, Floudas CA (2004b) Trilinear monomials with positive or negative domains: Facets of the convex and concave envelopes. Floudas CA, Pardalos P, eds. Frontiers in Global Optimization, Nonconvex Optimization and Its Applications, vol. 74 (Springer, Boston), 327–352.Google Scholar
• Meyer CA, Floudas CA (2005) Convex envelopes for edge-concave functions. Math. Programming 103(2):207–224.Google Scholar
• Misener R, Floudas CA (2014) ANTIGONE: Algorithms for continuous/integer global optimization of nonlinear equations. J. Global Optim. 59(2):503–526.Google Scholar
• Rikun AD (1997) A convex envelope formula for multilinear functions. J. Global Optim. 10(4):425–437.Google Scholar
• Ryoo HS, Sahinidis NV (1995) Global optimization of nonconvex NLPs and MINLPs with applications in process design. Comput. Chemical Engrg. 19(5):551–566.Google Scholar
• Ryoo HS, Sahinidis NV (1996) A branch-and-reduce approach to global optimization. J. Global Optim. 8(2):107–138.Google Scholar
• Ryoo HS, Sahinidis NV (2001) Analysis of bounds for multilinear functions. J. Global Optim. 19(4):403–424.Google Scholar
• Sahinidis NV (1996) BARON: A general purpose global optimization software package. J. Global Optim. 8(2):201–205.Google Scholar
• Schneider R (2013) Convex Bodies: The Brunn–Minkowski Theory, 2nd ed. (Cambridge University Press, Cambridge, UK).Google Scholar
• Schutte E, Walter M (2024) Relaxation strength for multilinear optimization: McCormick strikes back. Vygen J, Byrka J, eds. Integer Programming and Combinatorial Optimization. IPCO 2024, Lecture Notes in Computer Science, vol. 14679 (Springer, Cham, Switzerland), 393–406.Google Scholar
• Smith E, Pantelides C (1999) A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex MINLPs. Comput. Chemical Engrg. 23(4–5):457–478.Google Scholar
• Speakman E, Averkov G (2022) Computing the volume of the convex hull of the graph of a trilinear monomial using mixed volumes. Discrete Appl. Math. 308(c):36–45.Google Scholar
• Speakman E, Lee J (2017) Quantifying double McCormick. Math. Oper. Res. 42(4):1230–1253.Link, Google Scholar
• Speakman E, Lee J (2018) On branching-point selection for trilinear monomials in spatial branch-and-bound: The hull relaxation. J. Global Optim. 72(2):129–153.Google Scholar
• Speakman E, Yu H, Lee J (2017) Experimental validation of volume-based comparison for double-McCormick relaxations. Salvagnin D, Lombardi M, eds. Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2017, Lecture Notes in Computer Science, vol. 10335 (Springer, Cham, Switzerland), 229–243.Google Scholar
• Steingrímsson E (1994) A decomposition of 2-weak vertex-packing polytopes. Discrete Comput. Geometry 12(4):465–479.Google Scholar
• Tawarmalani M, Sahinidis NV (2002) Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications, Nonconvex Optimization and Its Applications, vol. 65 (Kluwer Academic Publishers, Dordrecht, Netherlands).Google Scholar
• Virtanen P, Gommers R, Oliphant TE, Haberland M, Reddy T, Cournapeau D, Burovski E, et al. (2020) SciPy 1.0: Fundamental algorithms for scientific computing in Python. Nature Methods 17(3):261–272.Google Scholar