  


Quadratic 01 optimization using separable underestimators
Christoph Buchheim (christoph.buchheimtudortmund.de) Abstract: Binary programs with a quadratic objective function are NPhard in general, even if the linear optimization problem over the same feasible set is tractable. In this paper, we address such problems by computing quadratic global underestimators of the objective function that are separable but not necessarily convex. Exploiting the binarity constraint on the variables, a minimizer of the separable underestimator over the feasible set can be computed by solving an appropriate linear minimization problem over the same feasible set. Embedding the resulting lower bounds into a branchandbound framework, we obtain an exact algorithm for the original quadratic binary program. The main practical challenge is the fast computation of an appropriate underestimator, which in our approach reduces to solving a series of semidefinite programs. We exploit the special structure of the resulting problems and propose a tailored coordinatedescent method for their solution. Our extensive experimental results on various quadratic combinatorial optimization problems show that our approach outperforms both Cplex and the related QCR method. For the quadratic shortest path problem, we thus provide the fastest exact approach currently available. Keywords: Binary Quadratic Optimization, Separable Underestimators, Quadratic Shortest Path Problem Category 1: Integer Programming (01 Programming ) Category 2: Nonlinear Optimization (Quadratic Programming ) Category 3: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Citation: Download: [PDF] Entry Submitted: 10/24/2012 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  