Optimization Online


Semidefinite Relaxations for Non-Convex Quadratic Mixed-Integer Programming

Christoph Buchheim (christoph.buchheim***at***tu-dortmund.de)
Angelika Wiegele (angelika.wiegele***at***uni-klu.ac.at)

Abstract: We present semidefinite relaxations for unconstrained non-convex quadratic mixed-integer optimization problems. These relaxations yield tight bounds and are computationally easy to solve for medium-sized instances, even if some of the variables are integer and unbounded. In this case, the problem contains an infinite number of linear constraints; these constraints are separated dynamically. We use this approach as the bounding routine in an SDP-based branch-and-bound framework. In case of a convex objective function, the new SDP bound improves the bound given by the continuous relaxation of the problem. Numerical experiments show that our algorithm performs well on various types of non-convex instances.

Keywords: Semidefinite Programming, Mixed-Integer Quadratic Programming, Integer Programming

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

Category 2: Linear, Cone and Semidefinite Programming

Category 3: Nonlinear Optimization (Quadratic Programming )

Citation: Technical Report, Alpen-Adria-Universitaet Klagenfurt.

Download: [PDF]

Entry Submitted: 09/14/2010
Entry Accepted: 09/14/2010
Entry Last Modified: 11/08/2011

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