Semidefinite Relaxations for Non-Convex Quadratic Mixed-Integer Programming
Christoph Buchheim (christoph.buchheimtu-dortmund.de)
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.
Entry Submitted: 09/14/2010
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|