12,000

We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK

93%

93% of Lancaster students go into work or further study within six months of graduating

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

« Back

Gap inequalities for non-convex mixed-integer quadratic programs

Research output: Contribution to journalJournal article

Published

Journal publication date2011
JournalOperations Research Letters
Journal number5
Volume39
Number of pages4
Pages297-300
Original languageEnglish

Abstract

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.