Volume Formulae for the Convex Hull of the Graph of a Trilinear Monomial: A Complete Characterization for General Box Domains
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917148359655424 |
|---|---|
| author | Makhoul, Lillian Speakman, Emily |
| author_facet | Makhoul, Lillian Speakman, Emily |
| contents | Solving difficult mixed-integer nonlinear programs via spatial branch-and-bound requires effective convex outer-approximations of nonconvex sets. In this framework, complex problem formulations are decomposed into simpler library functions, whose relaxations are then composed to build relaxations of the overall problem. The trilinear monomial serves as one such fundamental library function, appearing frequently as a building block across diverse applications. By definition, its convex hull provides the tightest possible relaxation and thus serves as a benchmark for evaluating alternatives. Mixed volume techniques have yielded a parameterized volume formula for the convex hull of the graph of a trilinear monomial; however, existing results only address the case where all six bounds of the box domain are nonnegative. This restriction represents a notable gap in the literature, as variables with mixed-sign domains arise naturally in practice. In this work, we close the gap by extending to the general case via an exhaustive case analysis. We demonstrate that removing the nonnegative domain assumption alters the underlying structure of the convex hull polytope, leading to six distinct volume formulae that together characterize all possible parameter configurations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_13964 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Volume Formulae for the Convex Hull of the Graph of a Trilinear Monomial: A Complete Characterization for General Box Domains Makhoul, Lillian Speakman, Emily Optimization and Control Solving difficult mixed-integer nonlinear programs via spatial branch-and-bound requires effective convex outer-approximations of nonconvex sets. In this framework, complex problem formulations are decomposed into simpler library functions, whose relaxations are then composed to build relaxations of the overall problem. The trilinear monomial serves as one such fundamental library function, appearing frequently as a building block across diverse applications. By definition, its convex hull provides the tightest possible relaxation and thus serves as a benchmark for evaluating alternatives. Mixed volume techniques have yielded a parameterized volume formula for the convex hull of the graph of a trilinear monomial; however, existing results only address the case where all six bounds of the box domain are nonnegative. This restriction represents a notable gap in the literature, as variables with mixed-sign domains arise naturally in practice. In this work, we close the gap by extending to the general case via an exhaustive case analysis. We demonstrate that removing the nonnegative domain assumption alters the underlying structure of the convex hull polytope, leading to six distinct volume formulae that together characterize all possible parameter configurations. |
| title | Volume Formulae for the Convex Hull of the Graph of a Trilinear Monomial: A Complete Characterization for General Box Domains |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2512.13964 |