Article ID: | iaor20119270 |
Volume: | 39 |
Issue: | 5 |
Start Page Number: | 297 |
End Page Number: | 300 |
Publication Date: | Sep 2011 |
Journal: | Operations Research Letters |
Authors: | Letchford Adam N, Kaparis Konstantinos, Galli Laura |
Keywords: | programming: integer, programming: convex |
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.