We investigate the computational potential of split inequalities for non-convex quadratic integer programming, first introduced by Letchford and further examined by Burer and Letchford. These inequalities can be separated by solving convex quadratic integer minimization problems. For small instances with box-constraints, we show that the resulting dual bounds are very tight; they can close a large percentage of the gap left open by both the RLT- and the SDP-relaxations of the problem. The gap can be further decreased by separating so-called non-standard split inequalities, which we examine in the case of ternary variables.
Article
View On the Separation of Split Inequalities for Non-Convex Quadratic Integer Programming