The Running Intersection Relaxation of the Multilinear Polytope

References

• [1] Balas E (1998) Disjunctive programming: Properties of the convex hull of feasible points. Discrete Appl. Math. 89(1–3):3–44.Crossref, Google Scholar
• [2] Bao X , Sahinidis NV , Tawarmalani M (2009) Multiterm polyhedral relaxations for nonconvex, quadratically-constrained quadratic programs. Optim. Methods Software 24:485–504.Crossref, Google Scholar
• [3] Barahona F , Junger M , Reinelt G (1989) Experiments in quadratic 0-1 programming. Math. Programming 44:127–137.Crossref, Google Scholar
• [4] Beeri C , Fagin R , Maier D , Yannakakis M (1983) On the desirability of acyclic database schemes. J. ACM 30:479–513.Crossref, Google Scholar
• [5] Berge C (1973) Graphs and Hypergraphs (North-Holland, Amsterdam).Google Scholar
• [6] Bienstock D , Munoz G (2018) LP furmulations for polynomial optimization problems. SIAM J. Optim. 28(2):1121–1150.Crossref, Google Scholar
• [7] Bonami P , Günlük O , Linderoth J (2018) Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods. Math. Programming Comput. 10:333–382.Crossref, Google Scholar
• [8] Buchheim C , Crama Y , Rodríguez-Heck E (2019) Berge-acyclic multilinear 0-1 optimization problems. Eur. J. Oper. Res. 273(1):102–107.Crossref, Google Scholar
• [9] Conforti M , Cornuéjols G (1995) A class of logic problems solvable by linear programming. J. Assoc. Comput. Machinery 42:1107–1113.Crossref, Google Scholar
• [10] Crama Y (1993) Concave extensions for non-linear 0-1 maximization problems. Math. Programming 61:53–60.Crossref, Google Scholar
• [11] 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
• [12] Del Pia A , Khajavirad A (2017) A polyhedral study of binary polynomial programs. Math. Oper. Res. 42(2):389–410.Link, Google Scholar
• [13] Del Pia A , Khajavirad A (2018) The multilinear polytope for acyclic hypergraphs. SIAM J. Optim. 28:1049–1076.Crossref, Google Scholar
• [14] Del Pia A , Khajavirad A (2018) On decomposability of multilinear sets. Math. Programming Ser. A 170(2):387–415.Crossref, Google Scholar
• [15] Del Pia A , Khajavirad A , Sahinidis N (2020) On the impact of running intersection inequalities for globally solving polynomial optimization problems. Math. Programming Comput. 12:165–191.Crossref, Google Scholar
• [16] Deza MM , Laurent M (1997) Geometry of Cuts and Metrics, Algorithms and Combinatorics , vol. 15 (Springer-Verlag, Berlin).Crossref, Google Scholar
• [17] Dukes PJ (2015) Generalized laminar families and certain forbidden matrices. Order 32(3):401–408.Crossref, Google Scholar
• [18] Fagin R (1983) Degrees of acyclicity for hypergraphs and relational database schemes. J. ACM 30(3):514–550.Crossref, Google Scholar
• [19] Heggernes P (2005) Treewidth, partial k-trees, and chordal graphs. Working paper, University of Bergen, Bergen, Norway.Google Scholar
• [20] Khajavirad A , Sahinidis NV (2018) A hybrid LP/NLP paradigm for global optimization relaxations. Math. Programming Comput. 10(3):383–421.Crossref, Google Scholar
• [21] Kolman P , Koutecký M (2015) Extended formulation for CSP that is compact for instances of bounded treewidth. Electronic J. Combinatorics 22(4):P4.30.Crossref, Google Scholar
• [22] Laurent M (2009) Sums of squares, moment matrices and optimization over polynomials. Emerging Applications of Algebraic Geometry , The IMA Volumes in Mathematics and Its Applications, vol. 149 (Springer, Berlin), 157–270.Crossref, Google Scholar
• [23] Lauritzen SL (1996) Graphical Models (Oxford University Press, New York).Crossref, Google Scholar
• [24] 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
• [25] Padberg M (1989) The boolean quadric polytope: Some characteristics, facets and relatives. Math. Programming 45:139–172.Crossref, Google Scholar
• [26] Sahinidis NV (2017) BARON 17.8.9: Global Optimization of Mixed-Integer Nonlinear Programs (The Optimization Firm LLC, Pittsburgh).Google Scholar
• [27] Wainwright MJ , Jordan MI (2004) Treewidth-based conditions for exactness of the Sherali-Adams and Lasserre relaxations. Technical Report 671, University of California, Berkeley, Berkeley.Google Scholar