Home > Research > Publications & Outputs > Gap inequalities for non-convex mixed-integer q...
View graph of relations

Gap inequalities for non-convex mixed-integer quadratic programs

Research output: Contribution to journalJournal article


<mark>Journal publication date</mark>2011
<mark>Journal</mark>Operations Research Letters
Issue number5
Number of pages4
Pages (from-to)297-300
<mark>Original language</mark>English


Laurent and Poljak introduced a very general class of valid linear inequalities, called gap inequalities, for the max-cut problem. We show that an analogous class of inequalities can be defined for general non-convex mixed-integer quadratic programs. These inequalities dominate some inequalities arising from a natural semidefinite relaxation.