Optimization Online


On the Separation of Split Inequalities for Non-Convex Quadratic Integer Programming

Christoph Buchheim(christoph.buchheim***at***tu-dortmund.de)
Emiliano Traversi(emiliano.traversi***at***gmail.com)

Abstract: 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.


Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Integer Programming (Cutting Plane Approaches )

Category 3: Nonlinear Optimization (Quadratic Programming )


Download: [PDF]

Entry Submitted: 07/12/2013
Entry Accepted: 07/12/2013
Entry Last Modified: 07/12/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society