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

Valid inequalities for QCQPs

Amélie Lambert

Published Jul 3, 2018• 0 citations
OpenAlex

Related papers

MPGP for Separable QCQP

Zdeněk Dostál

Advances in mechanics and mathematics•Jan 1, 2016•0 citations

MPGP for Separable QCQP

Zdeněk Dostál

Advances in mechanics and mathematics•Jan 1, 2023•0 citations

On the implementation and strengthening of intersection cuts for QCQPs

Antonia Chmiela, Gonzalo Muñoz, Felipe Serrano

Mathematical Programming•Apr 18, 2022•6 citations

On the Implementation and Strengthening of Intersection Cuts for QCQPs

Antonia Chmiela, Gonzalo Muñoz, Felipe Serrano

Lecture notes in computer science•Jan 1, 2021•2 citations

QCL-C: Formulations and Projection Inequalities

Kluwer Academic Publishers eBooks•May 31, 2006•0 citations

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
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.