Chvátal Rank in Binary Polynomial Optimization

References

• Balas E (1998) Disjunctive programming: Properties of the convex hull of feasible points. Discrete Appl. Math. 89(1–3):3–44.Google Scholar
• Barahona F, Mahjoub A (1986) On the cut polytope. Math. Programming 36:157–173.Google Scholar
• Beeri C, Fagin R, Maier D, Yannakakis M (1983) On the desirability of acyclic database schemes. J. ACM 30:479–513.Google Scholar
• Bernasconi J (1987) Low autocorrelation binary sequences: Statistical mechanics and configuration space analysis. J. Phys. (Paris) 141(48):559–567.Google Scholar
• Bienstock D, Muñoz G (2018) Lp formulations for polynomial optimization problems. SIAM J. Optim. 28(2):1121–1150.Google Scholar
• 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(3):333–382.Google Scholar
• Boros E, Gruber A (2012) On quadratization of pseudo-boolean functions. Internat. Sympos. Artificial Intelligence Math. (Fort Lauderdale, FL).Google Scholar
• Boros E, Hammer P (2002) Pseudo-boolean optimization. Discrete Appl. Math. 123:155–225.Google Scholar
• Boros E, Crama Y, Hammer P (1992) Chvátal cuts and odd cycle inequalities in quadratic 0 − 1 optimization. SIAM J. Discrete Math. 5(2):163–177.Google Scholar
• Boros E, Crama Y, Rodríguez-Heck E (2020) Compact quadratizations for pseudo-boolean functions. J. Combinatorial Optim. 39:687–707.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.Google Scholar
• Buchheim C, Crama Y, Rodríguez-Heck E (2018) Berge-acyclic multilinear 0 − 1 optimization problems. Eur. J. Oper. Res.Google Scholar
• Conforti M, Cornuéjols G, Zambelli G (2014) Integer Programming (Springer, Berlin).Google Scholar
• Cornuéjols G (2001) Combinatorial optimization: Packing and covering. CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 74 (SIAM, Philadelphia).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.Google Scholar
• Crama Y, Hansen P, Jaumard B (1990) The basic algorithm for pseudo-boolean programming revisited. Discrete Appl. Math. 29:171–185.Google Scholar
• Del Pia A, Khajavirad A (2017) A polyhedral study of binary polynomial programs. Math. Oper. Res. 42(2):389–410.Link, Google Scholar
• Del Pia A, Khajavirad A (2018a) The multilinear polytope for acyclic hypergraphs. SIAM J. Optim. 28(2):1049–1076.Google Scholar
• Del Pia A, Khajavirad A (2018b) On decomposability of multilinear sets. Math. Programming Ser. A 170(2):387–415.Google Scholar
• Del Pia A, Khajavirad A (2018c) On decomposability of the multilinear polytope and its implications in mixed-integer nonlinear optimization. INFORMS OS Today. 8(1):3–10.Google Scholar
• Del Pia A, Khajavirad A (2020) The running intersection relaxation of the multilinear polytope. Math. Oper. Res., Forthcoming.Google Scholar
• 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.Google Scholar
• Elloumi S, Lambert A, Lazare A (2019) Solving unconstrained 0-1 polynomial programs through quadratic convex reformulation. Preprint, submitted XXX, https://arxiv.org/abs/1901.07904.Google Scholar
• Fagin R (1983) Degrees of acyclicity for hypergraphs and relational database schemes. J. ACM 30(3):514–550.Google Scholar
• Fischetti M, Lodi A (2007) Optimizing over the first chvátal closure. Math. Programming 110:3–20.Google Scholar
• Fortet R (1960) Applications de l’algèbre de boole en recherche opérationnelle. Revue Française. Recherche Opérationnelle. 4:17–26.Google Scholar
• Freedman D, Drineas P (2005) Energy minimization via graph cuts: Settling what is possible. 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05, San Diego, CA), 939–946.Google Scholar
• Garey M, Johnson D (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (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 (2019) Gurobi 8.1.0 reference manual. Accessed June 1, 2020, https://www.gurobi.com/documentation/8.1/refman/index.html.Google Scholar
• Hammer P, Rudeanu S (1968) Boolean Methods in Operations Research and Related Areas (Springer, Berlin).Google Scholar
• Hammer P, Rosenberg I, Rudeanu S (1963) On the determination of the minima of pseudo-boolean functions (in Romanian). Studii Cercetari Matematice 14:359–364.Google Scholar
• Hartmann M, Queyranne M, Wang Y (1999) On the chvátal rank of certain inequalities. 7th Internat. IPCO Conf. (Springer, Berlin, Heidelberg), 218–233.Google Scholar
• Hojny C, Pfetsch M, Walter M (2019) Integrality of linearizations of polynomials over binary variables using additional monomials. Preprint, submitted November 15, 2019, https://arxiv.org/pdf/1911.06894.pdf.Google Scholar
• Ishikawa H (2009) Higher-order gradient descent by fusion-move graph cut. 2009 IEEE 12th Internat. Conf. Comput. Vision (Kyoto), pp. 568–574.Google Scholar
• Ishikawa H (2011) Transformation of general binary mrf minimization to the first-order case. IEEE Trans. Pattern Anal. Machine Intelligence 33(6):1234–1249.Google Scholar
• Lauritzen SL (1996) Graphical Models (Oxford University Press, New York).Google Scholar
• Lodi A (2010) Mixed integer programming computation. Jünger M, Liebling T, Naddef D, Nemhauser G, Pulleyblank W, Reinelt G, Rinaldi G, Wolsey L, eds. 50 Years of Integer Programming 1958–2008: From the Early Years to the State-of-the-Art (Springer, Berlin), 619–645.Google Scholar
• Mertens S, Bessenrodt C (1998) On the ground states of the bernasconi model. J. Phys. Math. General 31(16):3731–3749.Google Scholar
• MINLPLib (2020) A library of mixed-integer and continuous nonlinear programming instances. Accessed June 1, 2020, http://www.minlplib.org.Google Scholar
• Padberg M (1989) The Boolean quadric polytope: Some characteristics, facets and relatives. Math. Programming 45(1–3):139–172.Google Scholar
• POLIP (2014) Library for polynomially constrained mixed-integer programming. Accessed June 1, 2020, http://polip.zib.de.Google Scholar
• PORTA (2015) Polyhedron representation transformation algorithm. Accessed September 1, 2018, http://porta.zib.de.Google Scholar
• Rosenberg I (1975) Reduction of bivalent maximization to the quadratic case. Cahiers Center Études Recherche Opér. 17:71–74.Google Scholar
• Schrijver A (1986) Theory of Linear and Integer Programming (Wiley, Chichester, UK).Google Scholar