Gap inequalities for non-convex mixed-integer quadratic programs |
| |
Authors: | Laura Galli Konstantinos Kaparis Adam N Letchford |
| |
Institution: | aDEIS, University of Bologna, Viale Risorgimento 2, 40136 Bologna, Italy;bDepartment of Management Science, Lancaster University, Lancaster LA1 4YW, United Kingdom |
| |
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. |
| |
Keywords: | Max-cut problem Mixed-integer nonlinear programming Polyhedral combinatorics |
本文献已被 ScienceDirect 等数据库收录! |
|