A Polyhedral Study of Binary Polynomial Programs

References

• Al-Khayyal FA, Falk JE (1983) Jointly constrained biconvex programming. Math. Oper. Res. 8(2):273–286.Link, Google Scholar
• Balas E (1998) Disjunctive programming: Properties of the convex hull of feasible points. Discrete Appl. Math. 89(1–3):3–44.Crossref, Google Scholar
• Balas E, Ceria S, Cornuéjols G (1993) A lift-and-project cutting plane algorithm for mixed 0–1 programs. Math. Programming 58(1):295–324.Crossref, Google Scholar
• Bao X, Khajavirad A, Sahinidis NV, Tawarmalani M (2014) Global optimization of nonconvex problems with multilinear intermediates. Math. Programming Comput. 7(1):1–37.Crossref, Google Scholar
• Barahona F (1983) The max-cut problem on graphs not contractible to K5. Oper. Res. Lett. 2(3):107–111.Crossref, Google Scholar
• Barahona F (1986) A solvable case of quadratic 0 − 1 programming. Discrete Appl. Math. 13(1):23–26.Crossref, Google Scholar
• Barahona F, Mahjoub AR (1986) On the cut polytope. Math. Programming 36(2):157–173.Crossref, Google Scholar
• Barahona F, Junger M, Reinelt G (1989) Experiments in quadratic 0–1 programming. Math. Programming 44(1):127–137.Crossref, Google Scholar
• Berge C (1984) Hypergraphs: Combinatorics of Finite Sets (North-Holland, Amsterdam).Google Scholar
• Boros E, Gruber A (2014) On quadratization of pseudo-Boolean functions. Preprint, arXiv:1404.6538.Google Scholar
• Boros E, Hammer PL (1991) The max-cut problem and quadratic 0–1 optimization; polyhedral aspects, relaxations and bounds. Ann. Oper. Res. 33(3):151–180.Crossref, Google Scholar
• Boros E, Hammer PL (1993) Cut-polytopes, Boolean quadric polytopes and nonnegative quadratic pseudo-Boolean functions. Math. Oper. Res. 18(1):245–253.Link, Google Scholar
• Boros E, Hammer PL (2002) Pseudo-Boolean optimization. Discrete Appl. Math. 123(1):155–225.Crossref, Google Scholar
• Buchheim C, Rinaldi G (2007) Efficient reduction of polynomial zero-one optimization to the quadratic case. SIAM J. Optim. 18(4):1398–1413.Crossref, Google Scholar
• Cafieri S, Lee J, Liberti L (2010) On convex relaxations of quadrilinear terms. J. Global Optim. 47(4):661–685.Crossref, Google Scholar
• Crama Y (1993) Concave extensions for non-linear 0–1 maximization problems. Math. Programming 61(1):53–60.Crossref, Google Scholar
• De Simone C (1990) The cut polytope and the Boolean quadric polytope. Discrete Math. 79(1):71–75.Crossref, Google Scholar
• De Simone C, Rinaldi G (1994) A cutting plane algorithm for the max-cut problem. Optim. Methods and Software 3(1–3):195–214.Crossref, Google Scholar
• Deza MM, Laurent M (1997) Geometry of Cuts and Metrics, Algorithms and Combinatorics, Vol. 15 (Springer, Berlin).Crossref, Google Scholar
• Glover F, Woolsey E (1974) Converting a 0–1 polynomial programming problem to a 0–1 linear program. Oper. Res. 22(1):180–182.Link, Google Scholar
• Hammer PL, Rudeanu S (1968) Boolean Methods in Operations Research and Related Areas (Springer, Berlin).Crossref, Google Scholar
• Hammer PL, Hansen P, Simeone B (1984) Roof duality, complementation and persistency in quadratic 0–1 optimization. Math. Programming 28(2):121–155.Crossref, Google Scholar
• Helmberg C, Rendl F (1998) Solving quadratic 0–1 problems by semidefinite programs and cutting planes. Math. Programming 82(3):291–315.Crossref, Google Scholar
• Lasserre JB (2003) Global optimization with polynomials and the problem of moments. SIAM J. Optim. 96(3):796–817.Crossref, Google Scholar
• Letchford AN, Sørensen MM (2014) A new separation algorithm for the Boolean quadric and cut polytopes. Discrete Optim. 14:61–71.Crossref, Google Scholar
• Lovász L, Schrijver A (1991) Cones of matrices and set-functions and 0–1 optimization. SIAM J. Optim. 1(2):166–190.Crossref, Google Scholar
• Luedtke J, Namazifar M, Linderoth JT (2012) Some results on the strength of relaxations of multilinear functions. Math. Programming 136(2):325–351.Crossref, Google Scholar
• Meyer CA, Floudas CA (2005) Convex envelopes for edge-concave functions. Math. Programming 103(2):207–224.Crossref, Google Scholar
• Padberg M (1989) The Boolean quadric polytope: Some characteristics, facets and relatives. Math. Programming 45(1–3):139–172.Crossref, Google Scholar
• Padberg M, Wilczak MJ (1993) Boolean polynomials and set functions. Math. Comput. Model. 17(9):3–6.Crossref, Google Scholar
• Parillo PA (2003) Semidefinite programming relaxations for semialgebraic problems. Math. Programming 96(2):307–321.Google Scholar
• Rikun AD (1997) A convex envelope formula for multilinear functions. J. Global Optim. 10(4):425–437.Crossref, Google Scholar
• Ryoo HS, Sahinidis NV (2001) Analysis of bounds for multilinear functions. J. Global Optim. 19(4):403–424.Crossref, Google Scholar
• Sherali HD (1997) Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets. Acta Mathematica Vietnamica 22(1):245–270.Google Scholar
• Sherali HD, Adams WP (1990) A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3(3):411–430.Crossref, Google Scholar
• Tawarmalani M (2010) Inclusion certificates and simultaneous convexification of functions. Working paper, Krannert School of Management, Purdue University, West Lafayette, IN.Google Scholar
• Tawarmalani M, Sahinidis NV (2002) Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications (Kluwer Academic Publishers, Dordrecht, Netherlands).Crossref, Google Scholar
• Tawarmalani M, Richard J-P, Xiong C (2013) Explicit convex and concave envelopes through polyhedral subdivisions. Math. Programming 138(1–2):531–577.Crossref, Google Scholar
• Ursic S (1983) A linear characterization of NP-complete problems. Proc. Twenty-First Annual Allerton Conf. Comm., Control, and Comput. 100–109.Google Scholar
• Yajima Y, Fujie T (1998) A polyhedral approach for nonconvex quadratic programming problems with box constraints. J. Global Optim. 13(2):151–170.Crossref, Google Scholar