Relaxations for Binary Polynomial Optimization via Signed Certificates

References

• [1] Atamtürk A, Narayanan V (2022) Submodular function minimization and polarity. Math. Programming 196:57–67.Crossref, Google Scholar
• [2] Bach F (2019) Submodular functions: From discrete to continuous domains. Math. Programming 175:419–459.Crossref, Google Scholar
• [3] Balas E, Ceria S, Cornuéjols G (1993) A lift-and-project cutting plane algorithm for mixed 0–1 programs. Math. Programming 58:295–324.Crossref, Google Scholar
• [4] Bienstock D, Muñoz G (2018) LP formulations for polynomial optimization problems. SIAM J. Optim. 28(2):1121–1150.Crossref, Google Scholar
• [5] Bienstock D, Zuckerberg M (2004) Subset algebra lift operators for 0-1 integer programming. SIAM J. Optim. 15(1):63–95.Crossref, Google Scholar
• [6] Billionnet A, Minoux M (1985) Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions. Discrete Appl. Math. 12(1):1–11.Crossref, Google Scholar
• [7] Boros E, Hammer PL (2002) Pseudo-Boolean optimization. Discrete Appl. Math. 123(1–3):155–225.Crossref, Google Scholar
• [8] Chandrasekaran V, Shah P (2016) Relative entropy relaxations for signomial optimization. SIAM J. Optim. 26(2):1147–1173.Crossref, Google Scholar
• [9] Chlamtac E, Tulsiani M (2012) Convex relaxations and integrality gaps. Anjos M, Lasserre J, eds. Handbook on Semidefinite, Conic and Polynomial Optimization, International Series in Operations Research & Management Science, vol. 166 (Springer, New York), 139–169.Crossref, Google Scholar
• [10] Conforti M, Cornuéjols G, Zambelli G (2014) Integer Programming, Graduate Texts in Mathematics, vol. 271 (Springer, Cham, Switzerland).Crossref, Google Scholar
• [11] Crama Y (1989) Recognition problems for special classes of polynomials in 0–1 variables. Math. Programming 44:139–155.Crossref, Google Scholar
• [12] Crama Y (1993) Concave extensions for nonlinear 0–1 maximization problems. Math. Programming 61:53–60.Crossref, Google Scholar
• [13] Crama Y, Hammer PL (2011) Boolean Functions. Theory, Algorithms, and Applications, Encyclopedia of Mathematics and Its Applications, vol. 142 (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [14] De Loera JA, Hemmecke R, Köppe M (2013) Algebraic and Geometric Ideas in the Theory of Discrete Optimization, MOS/SIAM Series on Optimization, vol. 14 (SIAM, Philadelphia).Google Scholar
• [15] Del Pia A, Di Gregorio S (2023) On the complexity of binary polynomial optimization over acyclic hypergraphs. Algorithmica 85(8):2189–2213.Crossref, Google Scholar
• [16] Del Pia A, Khajavirad A (2017) A polyhedral study of binary polynomial programs. Math. Oper. Res. 42(2):389–410.Link, Google Scholar
• [17] Del Pia A, Khajavirad A (2024) A polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs. Math. Programming 207:269–301.Crossref, Google Scholar
• [18] Deza MM, Laurent M (1997) Geometry of Cuts and Metrics, Algorithms and Combinatorics, vol. 15 (Springer, Berlin, Heidelberg).Crossref, Google Scholar
• [19] Dressler M, Iliman S, De Wolff T (2017) A positivstellensatz for sums of nonnegative circuit polynomials. SIAM J. Appl. Algebra Geometry 1(1):536–555.Crossref, Google Scholar
• [20] Dressler M, Iliman S, De Wolff T (2019) An approach to constrained polynomial optimization via nonnegative circuit polynomials and geometric programming. J. Symbolic Comput. 91:149–172.Crossref, Google Scholar
• [21] Dressler M, Kurpisz A, De Wolff T (2022) Optimization over the boolean hypercube via sums of nonnegative circuit polynomials. Foundations Comput. Math. 22(2):365–387.Crossref, Google Scholar
• [22] Fujishige S (2005) Submodular Functions and Optimization, Annals of Discrete Mathematics, vol. 58 (Elsevier, Amsterdam).Google Scholar
• [23] Gallo G, Simeone B (1989) On the supermodular knapsack problem. Math. Programming 45:295–309.Crossref, Google Scholar
• [24] Gatermann K, Parrilo PA (2004) Symmetry groups, semidefinite programs, and sums of squares. J. Pure Appl. Algebra 192(1):95–128.Crossref, Google Scholar
• [25] Ghasemi M, Marshall M (2012) Lower bounds for polynomials using geometric programming. SIAM J. Optim. 22(2):460–473.Crossref, Google Scholar
• [26] Glover F, Woolsey E (1973) Further reduction of zero-one polynomial programming problems to zero-one linear programming problems. Oper. Res. 21(1):156–161.Link, Google Scholar
• [27] Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6):1115–1145.Crossref, Google Scholar
• [28] Gouveia J, Parrilo PA, Thomas RR (2010) Theta bodies for polynomial ideals. SIAM J. Optim. 20(4):2097–2118.Crossref, Google Scholar
• [29] Grimm D, Netzer T, Schweighofer M (2007) A note on the representation of positive polynomials with structured sparsity. Archiv Math. 89(5):399–403.Crossref, Google Scholar
• [30] Grötschel M, Lovász L, Schrijver A (1981) The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2):169–197.Crossref, Google Scholar
• [31] Handelman D (1988) Representing polynomials by positive linear functions on compact convex polyhedra. Pacific J. Math. 132(1):35–62.Crossref, Google Scholar
• [32] Hansen P (1974) Programmes mathématiques en variables 0-1. PhD thesis, Faculté des Sciences Appliquées, Université Libre de Bruxelles, Brussels.Google Scholar
• [33] Helmberg C, Rendl F (1998) Solving quadratic (0,1)-problems by semidefinite programs and cutting planes. Math. Programming 82:291–315.Crossref, Google Scholar
• [34] Krislock N, Malick J, Roupin F (2014) Improved semidefinite bounding procedure for solving max-cut problems to optimality. Math. Programming 143:61–86.Crossref, Google Scholar
• [35] Krivine JL (1964) Anneaux préordonnés. J. Anal. Math. 12:307–326.Crossref, Google Scholar
• [36] Lasserre JB (2002a) An explicit equivalent positive semidefinite program for nonlinear 0-1 programs. SIAM J. Optim. 12(3):756–769.Crossref, Google Scholar
• [37] Lasserre JB (2002b) Polynomials nonnegative on a grid and discrete optimization. Trans. Amer. Math. Soc. 354(2):631–649.Crossref, Google Scholar
• [38] Lasserre JB (2002c) Semidefinite programming vs. LP relaxations for polynomial programming. Math. Oper. Res. 27(2):347–360.Link, Google Scholar
• [39] Lasserre JB (2006) Convergent SDP-relaxations in polynomial optimization with sparsity. SIAM J. Optim. 17(3):822–843.Crossref, Google Scholar
• [40] Lasserre JB (2015) An Introduction to Polynomial and Semi-Algebraic Optimization, Cambridge Texts in Applied Mathematics (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [41] Laurent M (2003) A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0–1 programming. Math. Oper. Res. 28(3):470–496.Link, Google Scholar
• [42] Laurent M (2009) Sums of squares, moment matrices and optimization over polynomials. Putinar M, Sullivant S, eds. Emerging Applications of Algebraic Geometry, The IMA Volumes in Mathematics and Its Applications, vol. 149 (Springer, New York), 157–270.Crossref, Google Scholar
• [43] Laurent M, Slot L (2023) An effective version of Schmüdgen’s positivstellensatz for the hypercube. Optim. Lett. 17(3):515–530.Crossref, Google Scholar
• [44] Laurent M, Sun Z (2014) Handelman’s hierarchy for the maximum stable set problem. J. Global Optim. 60:393–423.Crossref, Google Scholar
• [45] Lee JR, Raghavendra P, Steurer D (2015) Lower bounds on the size of semidefinite programming relaxations. Proc. STOC 2015 (Association for Computing Machinery, New York), 567–576.Google Scholar
• [46] Liers F, Jünger M, Reinelt G, Rinaldi G (2004) Computing exact ground states of hard Ising spin glass problems by branch-and-cut. Hartmann AK, Riege H, eds. New Optimization Algorithms in Physics (Wiley-VCH, Weinheim, Germany), 47–69.Crossref, Google Scholar
• [47] Lovász L (1983) Submodular functions and convexity. Bachem A, Korte B, Grötschel M, eds. Mathematical Programming the State of the Art: Bonn 1982 (Springer Berlin Heidelberg, Berlin, Heidelberg), 235–257.Crossref, Google Scholar
• [48] 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
• [49] Magron V, Wang J (2023a) SONC optimization and exact nonnegativity certificates via second-order cone programming. J. Symbolic Comput. 115:346–370.Crossref, Google Scholar
• [50] Magron V, Wang J (2023b) Sparse Polynomial Optimization. Theory and Practice, Series on Optimization and its Applications, vol. 5 (World Scientific, Singapore).Crossref, Google Scholar
• [51] Malick J, Roupin F (2013) On the bridge between combinatorial optimization and nonlinear optimization: A family of semidefinite bounds for 0–1 quadratic problems leading to quasi-Newton methods. Math. Programming 140(1):99–124.Crossref, Google Scholar
• [52] Meyer CA, Floudas CA (2005) Convex envelopes for edge-concave functions. Math. Programming 103:207–224.Crossref, Google Scholar
• [53] Murota K (2003) Discrete Convex Analysis, SIAM Monographs on Discrete Mathematics and Applications, vol. 10 (SIAM, Philadelphia).Crossref, Google Scholar
• [54] Murray R, Chandrasekaran V, Wierman A (2021) Newton polytopes and relative entropy optimization. Foundations Comput. Math. 21(6):1703–1737.Crossref, Google Scholar
• [55] Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions—I. Math. Programming 14(1):265–294.Crossref, Google Scholar
• [56] Nguyen TT, Richard JPP, Tawarmalani M (2018) Deriving convex hulls through lifting and projection. Math. Programming 169(2):377–415.Google Scholar
• [57] Orlin JB (2009) A faster strongly polynomial time algorithm for submodular function minimization. Math. Programming 118(2):237–251.Crossref, Google Scholar
• [58] Orlin JB (2013) Max flows in O(nm) time, or better. Proc. STOC 2013 (Association for Computing Machinery, New York), 765–774.Google Scholar
• [59] Papp D (2023) Duality of sum of nonnegative circuit polynomials and optimal SONC bounds. J. Symbolic Comput. 114:246–266.Crossref, Google Scholar
• [60] Parrilo PA (2003) Semidefinite programming relaxations for semialgebraic problems. Math. Programming 96:293–320.Crossref, Google Scholar
• [61] Parrilo PA, Thomas RR, eds. (2020) Sum of Squares: Theory and Applications. AMS Short Course, Baltimore, MD, USA, January 14–15, 2019, Proceedings of Symposia in Applied Mathematics, vol. 77 (AMS, Providence, RI).Google Scholar
• [62] Picard JC, Queyranne M (1982) A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory. Networks 12(2):141–159.Crossref, Google Scholar
• [63] Putinar M (1993) Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. 42(3):969–984.Crossref, Google Scholar
• [64] Rendl F, Rinaldi G, Wiegele A (2010) Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Math. Programming 121:307–335.Crossref, Google Scholar
• [65] Rikun AD (1997) A convex envelope formula for multilinear functions. J. Global Optim. 10(4):425–437.Crossref, Google Scholar
• [66] Rinaldi G (1995) Rudy: A rudimental graph generator. Accessed June 18, 2026, https://github.com/g-rinaldi/rudy.Google Scholar
• [67] Sakaue S, Takeda A, Kim S, Ito N (2017) Exact semidefinite programming relaxations with truncated moment matrix for binary polynomial optimization problems. SIAM J. Optim. 27(1):565–582.Crossref, Google Scholar
• [68] 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
• [69] Sherali HD, Tuncbilek CH (1992) A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique. J. Global Optim. 2(1):101–112.Crossref, Google Scholar
• [70] Sherali HD, Tuncbilek CH (1997) New reformulation linearization/convexification relaxations for univariate and multivariate polynomial programming problems. Oper. Res. Let. 21(1):1–9.Crossref, Google Scholar
• [71] Sherali HD, Dalkiran E, Liberti L (2012) Reduced RLT representations for nonconvex polynomial programming problems. J. Global Optim. 52:447–469.Crossref, Google Scholar
• [72] Slot L, Laurent M (2023) Sum-of-squares hierarchies for binary polynomial optimization. Math. Programming 197(2):621–660.Crossref, Google Scholar
• [73] Tawarmalani M, Richard JPP, Xiong C (2013) Explicit convex and concave envelopes through polyhedral subdivisions. Math. Programming 138(1):531–577.Crossref, Google Scholar
• [74] Waki H, Kim S, Kojima M, Muramatsu M (2006) Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity. SIAM J. Optim. 17(1):218–242.Crossref, Google Scholar
• [75] Wang J, Li H, Xia B (2019) A new sparse SOS decomposition algorithm based on term sparsity. Proc. ISSAC 2019 (Association for Computing Machinery, New York), 347–354.Google Scholar
• [76] Wang J, Magron V, Lasserre JB (2021a) Chordal-TSSOS: A moment-SOS hierarchy that exploits term sparsity with chordal extension. SIAM J. Optim. 31(1):114–141.Crossref, Google Scholar
• [77] Wang J, Magron V, Lasserre JB (2021b) TSSOS: A moment-SOS hierarchy that exploits term sparsity. SIAM J. Optim. 31(1):30–58.Crossref, Google Scholar
• [78] Wiegele A (2007) Biq Mac Library—A collection of Max-Cut and quadratic 0-1 programming instances of medium size. Accessed June 18, 2026, https://biqmac.aau.at/biqmaclib.html.Google Scholar
• [79] Wolsey LA, Nemhauser GL (1999) Integer and Combinatorial Optimization (John Wiley & Sons, Hoboken, NJ).Google Scholar
• [80] Xu L, Liberti L (2025) Submodular maximization and its generalization through an intersection cut lens. Math. Programming 211:341–377.Crossref, Google Scholar