Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142615 | Operations Research Letters | 2011 | 4 Pages |
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.
► The gap inequalities form a very general class of cutting planes for the max-cut problem. ► We extend them to the case of non-convex mixed-integer quadratic programs. ► Our inequalities dominate some inequalities arising from a natural semidefinite relaxation.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Laura Galli, Konstantinos Kaparis, Adam N. Letchford,