Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.34053

On the Chvátal-Gomory Closure of Integer Quadratic Programs

Linchuan Wei, Tong Xu, Kim Yu

Published Oct 25, 2026• 0 citations
arXivHTMLPDF

Abstract

The integer quadratic moment hull is the closed convex hull of the pairs $(z,zz^{\top})$ with $z\in\mathbb{Z}^n$. We prove that one round of Chvátal-Gomory (CG) cuts applied to its basic semidefinite relaxation recovers this hull exactly if and only if $n\le6$. Our approach identifies its facets with perfect Delaunay polyhedra and characterizes their recovery through depth, the gap between lattice and continuous minima of a defining quadratic after normalization. A facet inequality is valid for the rank-one CG closure exactly when its depth is less than one. We also analyze the complexity of deciding membership in the CG closure and finding violated inequalities. Every rational point outside the CG closure admits a violated CG inequality whose encoding length is polynomial in the input length. Membership is strongly coNP-complete and exact separation is strongly NP-hard. The same reduction proves strong NP-hardness of quadratic split-inequality separation, resolving a conjecture of Burer and Letchford.

DOI
10.48550/arxiv.2610.34053

Related papers

Tight compact extended relaxations for nonconvex quadratic programming problems with box constraints

Sven de Vries, Bernd Perscheid

Abstract Cutting planes from the Boolean Quadric Polytope can be used to reduce the optimality gap of the $$\mathcal {NP}$$ NP -hard nonconvex quadratic program with box constraints (BoxQP). It is known that all cuts of the Chvátal–Gomory closure of the Boolean Quadric Polytope are A-odd cycle inequalities. We obtain a compact extended relaxation of allA-odd cycle inequalities, which allows to optimize over the Chvátal–Gomory closure without repeated calls to separation algorithms and has less inequalities than the formulation provided by Boros et al. (SIAM J Discrete Math 5(2):163–177, 1992) for sparse matrices. In a computational study, we confirm the strength of this relaxation and show that we can provide very strong bounds for the BoxQP, even with a plain linear program. The resulting bounds are significantly stronger than these from Bonami et al. (Math Program Comput 10(3):333–382, 2018), which arise from separating A-odd cycle inequalities heuristically.

Journal of Global Optimization•May 9, 2022•1 citation

Chvátal-Gomory Rounding of Eigenvector Inequalities for QCQPs

Santanu S. Dey, Nan Jiang, Aleksandr M. Kazachkov +2 more

We introduce and analyze a class of valid inequalities for nonconvex quadratically constrained optimization problems (QCQPs) which we call Eigen-CG inequalities. These inequalities are obtained by applying a Chvátal-Gomory (CG) rounding to the well-known eigenvector inequalities for QCQPs, and transferring binary-valid inequalities to the continuous setting via a result of Burer and Letchford (2009). We define three nested subfamilies and prove that they are strictly contained in one another. However, we show that the convex conic closure of two of these subfamilies is equal and, in fact, coincides with the Boros-Hammer inequalities -- a powerful family of inequalities that include, in particular, the triangle and McCormick inequalities. Using this CG perspective, we also prove that dense Eigen-CG inequalities are ineffective when used with the standard SDP+McCormick relaxation. This provides a complementary perspective on what is observed in practice: that sparse inequalities are impactful. Finally, based on these insights, we develop a computational strategy to find sparse Eigen-CG cuts and verify their effectiveness in nonconvex QCQP instances. Our results confirm that density quickly degrades effectiveness, but that including sparse inequalities beyond triangle inequalities can provide significant improvements in dual bounds.

arXiv:2604.00932•Apr 1, 2026•0 citations

Bounded Integer Quadratic Programming through Parallelepiped Covers and Discrete Convic Optimization

Cinar Ari, Robert Hildebrand

We give an exact algorithm for minimizing an arbitrary rational quadratic polynomial $x^T Q x + c^T x + γ$ over the integer points of a bounded rational polyhedron $\{x : Ax \le b\}$. For $n$ variables and $m$ inequalities, the running time is $$2^{O(n \log(n+1))} (m+1)^{O(n)} β^{O(n)} (1+L)^{O(1)},$$ where $β$ is one plus the maximum binary encoding length of an entry of $A$ or $Q$, and $L$ is the full input encoding length. The polynomial degree in $L$ is absolute; in particular, the encoding of $b$, $c$, and $γ$ enters only this fixed-degree factor. Our algorithm refines the integral parallelepiped cover of Goemans and Rothvoss into cells with controlled displacement sets. On each cell, either an integer displacement of negative quadratic value rules out every point as a global minimizer, or the quadratic identity supplies a separation oracle for the convex hull of each integer objective sublevel set. The integer-query feasibility theorem of Hildebrand and Goess then finds the cell minimum. A refinement through scaled lattices solves the displacement search, and a localization argument separates the encoding dependence of the constraint matrix and quadratic part from that of the remaining data. Combining the bounded algorithm with the unboundedness test of Ari and Hildebrand extends the method to arbitrary rational polyhedra.

arXiv:2609.17889•Sep 15, 2026•0 citations

High Degree Sum of Squares Proofs, Bienstock--Zuckerberg Hierarchy, and Chvátal--Gomory Cuts

Monaldo Mastrolilli

Chvátal--Gomory cuts (CG-cuts) and the Bienstock--Zuckerberg hierarchy capture useful linear programs that the standard bounded degree sum-of-squares (SoS) hierarchy fails to capture. In this paper we present a novel polynomial time SoS hierarchy for 0/1 problems with a custom subspace of high degree polynomials (not the standard subspace of low degree polynomials). We show that the new SoS hierarchy recovers the Bienstock--Zuckerberg hierarchy. Our result implies a linear program that reproduces the Bienstock--Zuckerberg hierarchy as a polynomial-sized, efficiently constructible extended formulation that satisfies all constant pitch inequalities. The construction is also very simple, and it is fully defined by giving the supporting polynomials. Moreover, for a class of polytopes (e.g., set cover and packing problems), the resulting SoS hierarchy optimizes in polynomial time over the polytope resulting from any constant rounds of CG-cuts, up to an arbitrarily small error in the solution value. Arguably, this is the first example where different basis functions can be useful in asymmetric situations to obtain a hierarchy of relaxations.

arXiv:1709.07966•SIAM Journal on Optimization•Jan 1, 2020•1 citation

Cutting Planes for Mixed Integer Programming

Andrea Qualizza

My work focuses on cutting planes technology in Mixed Integer Programming. I explore novel classes of valid linear inequalities to strengthen linear relaxations of both Linear and Nonlinear Mixed Integer problems. My dissertation consists of three chapters that investigate theoretically and computationally the families of cuts considered. The first chapter is based on joint work with Prof. Pietro Belotti and Prof. Francois Margot. We study linear relaxations of Quadratically Constrained Quadratic Programs. The proposed relaxations are models with both semi-definite constraints (PSD) and linear constraints given by the Reformulation Linearization Technique (RLT). It is known from the literature (Anstreicher, 2007) that PSD and RLT used together yield better bounds than each technique used separately. We adopt a linear outer-approximation of the PSD cone, and we use exclusively linear programming tools to enforce the PSD condition via a cutting plane approach in the lifted space containing the Yij = xixj variables. We study new classes of valid linear inequalities and we test their effectiveness empirically. These include sparse PSD cuts and cuts derived from principal minors. Computational results based on instances from the GLOBALLib and Boxed Constrained Quadratic Programs show that this approach yields better bounds than using solely the standard PSD cuts on top of the RLT inequalities. The C++ code developed for this study has been included in Coin-OR as part of the Couenne project (exact solver for MINLPs). In the second chapter I present a work closely related to the recent developments in the area of \cuts from multiple rows of the simplex tableau" (Andersen et al., 2007). This chapter is based on joint work with Prof. Egon Balas. We generate intersection cuts from lattice-free convex sets as lift-and-project cuts from multiple-term disjunctions. We use the concept of \Disjunctive Hull" defined for a Mixed Integer Program at a fractional vertex v of its linear relaxation P as the convex hull of points in P satisfying all basic disjunctions that cut o v but no integer point. We examine the relationship between the Disjunctive Hull and the Integer Hull and we give procedures to generate inequalities for the Integer Hull derived from the Cut Generating Linear Program associated to the Disjunctive Hull. Strengthening techniques based on coefficient modularization and monoidal strengthening are also discussed. In this chapter we also analyze the case of 0-1 programming which has not been covered in the literature. Our framework applies to this setting with minor changes and produces valid families of cuts for the 0-1 case but invalid for general integer programs. These cuts include the triangle, quadrilateral, split cuts for the MIP case, and cuts from cones and truncated cones for the 0-1 setting. Moreover we run an experiment in which we separate two families of non facet defining cuts: we consider cuts from fixed shape triangles of type 1 and conic disjunctions having the apex at one vertex of the unit cube and two extreme rays, each containing an additional vertex of the cube. In practice, in order to match the strength of the non facet defining inequalities, a large number of facet defining inequalities is typically needed. Triangles of type 1 produce a consistent improvement over the Gomory cuts, as shown in experiments on the MIPLIB 3 0-1 instances. In the third chapter I present a theoretical result on strengthening valid inequalities for Mixed Integer Linear Programs. This chapter is also based on joint work with Prof. Egon Balas. There are two distinct strengthening methods for disjunctive cuts; they differ in the way they modularize the coefficients associated to integer constrained variables. We introduce a new variant of one of these methods, the monoidal cut strengthening procedure (Balas and Jeroslow, 1980), based on the paradox that sometimes weakening a disjunction helps the strengthening procedure and results in sharper cuts. We first derive a general result that applies to cuts from disjunctions with any number of terms. It defines the coefficients of the cut in a way that takes advantage of the option of adding new terms to the disjunction. We then specialize this result to the case of split cuts, in particular Gomory Mixed Integer cuts, and to intersection cuts from multiple rows of a simplex tableau. In both instances we give conditions for the new cuts to have stronger coefficients than the cuts obtained by either of the two currently known strengthening procedures.

•Jan 1, 2011•2 citations

The equivalence between doubly nonnegative relaxation and semidefinite relaxation for binary quadratic programming problems

Chuan-Hao Guo, Yanqin Bai, Tang, Li-Ping

It has recently been shown (Burer, Math. Program Ser. A 120:479-495, 2009) that a large class of NP-hard nonconvex quadratic programming problems can be modeled as so called completely positive programming problems, which are convex but still NP-hard in general. A basic tractable relaxation is gotten by doubly nonnegative relaxation, resulting in a doubly nonnegative programming. In this paper, we prove that doubly nonnegative relaxation for binary quadratic programming (BQP) problem is equivalent to a tighter semidifinite relaxation for it. When problem (BQP) reduces to max-cut (MC) problem, doubly nonnegative relaxation for it is equivalent to the standard semidifinite relaxation. Furthermore, some compared numerical results are reported.

arXiv:1211.5406•Nov 23, 2012•0 citations
The integer quadratic moment hull is the closed convex hull of the pairs (z,zz⊤)(z,zz^{\top})(z,zz⊤) with z∈Znz\in\mathbb{Z}^nz∈Zn. We prove that one round of Chvátal-Gomory (CG) cuts applied to its basic semidefinite relaxation recovers this hull exactly if and only if n≤6n\le6n≤6. Our approach identifies its facets with perfect Delaunay polyhedra and characterizes their recovery through depth, the gap between lattice and continuous minima of a defining quadratic after normalization. A facet inequality is valid for the rank-one CG closure exactly when its depth is less than one. We also analyze the complexity of deciding membership in the CG closure and finding violated inequalities. Every rational point outside the CG closure admits a violated CG inequality whose encoding length is polynomial in the input length. Membership is strongly coNP-complete and exact separation is strongly NP-hard. The same reduction proves strong NP-hardness of quadratic split-inequality separation, resolving a conjecture of Burer and Letchford.
Abstract Cutting planes from the Boolean Quadric Polytope can be used to reduce the optimality gap of the NP\mathcal {NP}NP NP -hard nonconvex quadratic program with box constraints (BoxQP). It is known that all cuts of the Chvátal–Gomory closure of the Boolean Quadric Polytope are A-odd cycle inequalities. We obtain a compact extended relaxation of allA-odd cycle inequalities, which allows to optimize over the Chvátal–Gomory closure without repeated calls to separation algorithms and has less inequalities than the formulation provided by Boros et al. (SIAM J Discrete Math 5(2):163–177, 1992) for sparse matrices. In a computational study, we confirm the strength of this relaxation and show that we can provide very strong bounds for the BoxQP, even with a plain linear program. The resulting bounds are significantly stronger than these from Bonami et al. (Math Program Comput 10(3):333–382, 2018), which arise from separating A-odd cycle inequalities heuristically.
We introduce and analyze a class of valid inequalities for nonconvex quadratically constrained optimization problems (QCQPs) which we call Eigen-CG inequalities. These inequalities are obtained by applying a Chvátal-Gomory (CG) rounding to the well-known eigenvector inequalities for QCQPs, and transferring binary-valid inequalities to the continuous setting via a result of Burer and Letchford (2009). We define three nested subfamilies and prove that they are strictly contained in one another. However, we show that the convex conic closure of two of these subfamilies is equal and, in fact, coincides with the Boros-Hammer inequalities -- a powerful family of inequalities that include, in particular, the triangle and McCormick inequalities. Using this CG perspective, we also prove that dense Eigen-CG inequalities are ineffective when used with the standard SDP+McCormick relaxation. This provides a complementary perspective on what is observed in practice: that sparse inequalities are impactful. Finally, based on these insights, we develop a computational strategy to find sparse Eigen-CG cuts and verify their effectiveness in nonconvex QCQP instances. Our results confirm that density quickly degrades effectiveness, but that including sparse inequalities beyond triangle inequalities can provide significant improvements in dual bounds.
We give an exact algorithm for minimizing an arbitrary rational quadratic polynomial xTQx+cTx+γx^T Q x + c^T x + γxTQx+cTx+γ over the integer points of a bounded rational polyhedron {x:Ax≤b}\{x : Ax \le b\}{x:Ax≤b}. For nnn variables and mmm inequalities, the running time is 2O(nlog⁡(n+1))(m+1)O(n)βO(n)(1+L)O(1),2^{O(n \log(n+1))} (m+1)^{O(n)} β^{O(n)} (1+L)^{O(1)},2O(nlog(n+1))(m+1)O(n)βO(n)(1+L)O(1), where βββ is one plus the maximum binary encoding length of an entry of AAA or QQQ, and LLL is the full input encoding length. The polynomial degree in LLL is absolute; in particular, the encoding of bbb, ccc, and γγγ enters only this fixed-degree factor. Our algorithm refines the integral parallelepiped cover of Goemans and Rothvoss into cells with controlled displacement sets. On each cell, either an integer displacement of negative quadratic value rules out every point as a global minimizer, or the quadratic identity supplies a separation oracle for the convex hull of each integer objective sublevel set. The integer-query feasibility theorem of Hildebrand and Goess then finds the cell minimum. A refinement through scaled lattices solves the displacement search, and a localization argument separates the encoding dependence of the constraint matrix and quadratic part from that of the remaining data. Combining the bounded algorithm with the unboundedness test of Ari and Hildebrand extends the method to arbitrary rational polyhedra.
Chvátal--Gomory cuts (CG-cuts) and the Bienstock--Zuckerberg hierarchy capture useful linear programs that the standard bounded degree sum-of-squares (SoS) hierarchy fails to capture. In this paper we present a novel polynomial time SoS hierarchy for 0/1 problems with a custom subspace of high degree polynomials (not the standard subspace of low degree polynomials). We show that the new SoS hierarchy recovers the Bienstock--Zuckerberg hierarchy. Our result implies a linear program that reproduces the Bienstock--Zuckerberg hierarchy as a polynomial-sized, efficiently constructible extended formulation that satisfies all constant pitch inequalities. The construction is also very simple, and it is fully defined by giving the supporting polynomials. Moreover, for a class of polytopes (e.g., set cover and packing problems), the resulting SoS hierarchy optimizes in polynomial time over the polytope resulting from any constant rounds of CG-cuts, up to an arbitrarily small error in the solution value. Arguably, this is the first example where different basis functions can be useful in asymmetric situations to obtain a hierarchy of relaxations.
My work focuses on cutting planes technology in Mixed Integer Programming. I explore novel classes of valid linear inequalities to strengthen linear relaxations of both Linear and Nonlinear Mixed Integer problems. My dissertation consists of three chapters that investigate theoretically and computationally the families of cuts considered. The first chapter is based on joint work with Prof. Pietro Belotti and Prof. Francois Margot. We study linear relaxations of Quadratically Constrained Quadratic Programs. The proposed relaxations are models with both semi-definite constraints (PSD) and linear constraints given by the Reformulation Linearization Technique (RLT). It is known from the literature (Anstreicher, 2007) that PSD and RLT used together yield better bounds than each technique used separately. We adopt a linear outer-approximation of the PSD cone, and we use exclusively linear programming tools to enforce the PSD condition via a cutting plane approach in the lifted space containing the Yij = xixj variables. We study new classes of valid linear inequalities and we test their effectiveness empirically. These include sparse PSD cuts and cuts derived from principal minors. Computational results based on instances from the GLOBALLib and Boxed Constrained Quadratic Programs show that this approach yields better bounds than using solely the standard PSD cuts on top of the RLT inequalities. The C++ code developed for this study has been included in Coin-OR as part of the Couenne project (exact solver for MINLPs). In the second chapter I present a work closely related to the recent developments in the area of \cuts from multiple rows of the simplex tableau" (Andersen et al., 2007). This chapter is based on joint work with Prof. Egon Balas. We generate intersection cuts from lattice-free convex sets as lift-and-project cuts from multiple-term disjunctions. We use the concept of \Disjunctive Hull" defined for a Mixed Integer Program at a fractional vertex v of its linear relaxation P as the convex hull of points in P satisfying all basic disjunctions that cut o v but no integer point. We examine the relationship between the Disjunctive Hull and the Integer Hull and we give procedures to generate inequalities for the Integer Hull derived from the Cut Generating Linear Program associated to the Disjunctive Hull. Strengthening techniques based on coefficient modularization and monoidal strengthening are also discussed. In this chapter we also analyze the case of 0-1 programming which has not been covered in the literature. Our framework applies to this setting with minor changes and produces valid families of cuts for the 0-1 case but invalid for general integer programs. These cuts include the triangle, quadrilateral, split cuts for the MIP case, and cuts from cones and truncated cones for the 0-1 setting. Moreover we run an experiment in which we separate two families of non facet defining cuts: we consider cuts from fixed shape triangles of type 1 and conic disjunctions having the apex at one vertex of the unit cube and two extreme rays, each containing an additional vertex of the cube. In practice, in order to match the strength of the non facet defining inequalities, a large number of facet defining inequalities is typically needed. Triangles of type 1 produce a consistent improvement over the Gomory cuts, as shown in experiments on the MIPLIB 3 0-1 instances. In the third chapter I present a theoretical result on strengthening valid inequalities for Mixed Integer Linear Programs. This chapter is also based on joint work with Prof. Egon Balas. There are two distinct strengthening methods for disjunctive cuts; they differ in the way they modularize the coefficients associated to integer constrained variables. We introduce a new variant of one of these methods, the monoidal cut strengthening procedure (Balas and Jeroslow, 1980), based on the paradox that sometimes weakening a disjunction helps the strengthening procedure and results in sharper cuts. We first derive a general result that applies to cuts from disjunctions with any number of terms. It defines the coefficients of the cut in a way that takes advantage of the option of adding new terms to the disjunction. We then specialize this result to the case of split cuts, in particular Gomory Mixed Integer cuts, and to intersection cuts from multiple rows of a simplex tableau. In both instances we give conditions for the new cuts to have stronger coefficients than the cuts obtained by either of the two currently known strengthening procedures.
It has recently been shown (Burer, Math. Program Ser. A 120:479-495, 2009) that a large class of NP-hard nonconvex quadratic programming problems can be modeled as so called completely positive programming problems, which are convex but still NP-hard in general. A basic tractable relaxation is gotten by doubly nonnegative relaxation, resulting in a doubly nonnegative programming. In this paper, we prove that doubly nonnegative relaxation for binary quadratic programming (BQP) problem is equivalent to a tighter semidifinite relaxation for it. When problem (BQP) reduces to max-cut (MC) problem, doubly nonnegative relaxation for it is equivalent to the standard semidifinite relaxation. Furthermore, some compared numerical results are reported.