  


Quadratic combinatorial 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 binary 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 adapt an algorithm of Dong (2014) in order to obtain 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 as well as the SDPbased software BiqCrunch on instances of the quadratic shortest path problem and the quadratic assignment problem. 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  