On the Chvátal-Gomory Closure of Integer Quadratic Programs
Abstract
The integer quadratic moment hull is the closed convex hull of the pairs (z,zz⊤) with 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≤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.
Related
- 0/1 integer programming over polytopes of Chvátal rank one is as hard as lattice problems
- A quadratic upper bound on the Chvátal rank of polytopes in the 0/1-cube
- Infinite families of pairs of real quadratic fields whose class numbers are divisible by a given integer
- Asynchronous Parallel Computation of Lagrangian Bounds for Mixed-Integer Stochastic Programs by Frank-Wolfe Methods within Projective Hedging
- Satisfiability and freezing in random integer programs
BibTeX
@misc{wei2026chvátalgomory,
title = {{On the Chvátal-Gomory Closure of Integer Quadratic Programs}},
author = {Linchuan Wei and Tong Xu and Kim Yu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.34053},
eprint = {2610.34053},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.34053},
}
RIS
TY - UNPB
TI - On the Chvátal-Gomory Closure of Integer Quadratic Programs
AU - Linchuan Wei
AU - Tong Xu
AU - Kim Yu
PY - 2026
DA - 2026/10/25
PB - arXiv
DO - 10.48550/arxiv.2610.34053
UR - https://arxiv.org/abs/2610.34053
AB - The integer quadratic moment hull is the closed convex hull of the pairs (z,zz^⊤) with 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≤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.
ER -