An efficient combined DCA and B\&B using DC/SDP relaxation for globally solving binary quadratic programs

DOI10.1007/s10898-009-9507-yzbMath1226.90060MaRDI QIDQ604951

Nam Nguyen Canh, Hoai An Le Thi, Tao Pham Dinh

Publication date: 12 November 2010

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10898-009-9507-y

zbMATH Keywords

nonconvex quadratic programming; DC programming; DC relaxation; semidefinite programming (SDP); exact penalty; binary quadratic programming (BQP); branch-and-bound (B\&B); DC algorithms (DCA)

Mathematics Subject Classification ID

90C20: Quadratic programming

90C09: Boolean programming

Related Items

DC Programming and DCA for Challenging Problems in Bioinformatics and Computational Biology, Solving the Production and Maintenance Optimization Problem by a Global Approach, DC programming approaches for discrete portfolio optimization under concave transaction costs, DC approximation approaches for sparse optimization, The unconstrained binary quadratic programming problem: a survey, An efficient DC programming approach for portfolio decision with higher moments, Exact penalty and error bounds in DC programming, New formulations of the multiple sequence alignment problem, Properties of two DC algorithms in quadratic programming, A continuous DC programming approach for resource allocation in OFDMA/TDD wireless networks, DC programming and DCA: thirty years of developments, Solving the degree-concentrated fault-tolerant spanning subgraph problem by DC programming, Efficient semidefinite branch-and-cut for MAP-MRF inference, A branch-and-bound algorithm embedded with DCA for DC programming, Closed-form formulas for evaluating \(r\)-flip moves to the unconstrained binary quadratic programming problem, Variations and extension of the convex-concave procedure, Solving partitioning-hub location-routing problem using DCA, Building an iterative heuristic solver for a quantum annealer, On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study, DC Programming and DCA for General DC Programs

Uses Software

• SDPA
• CPLEX
• OR-Library
• SDP_S

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On solving linear complementarity problems by DC programming and DCA
• Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
• Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
• On the equivalence between roof duality and Lagrangian duality for unconstrained \(0\)-\(1\) quadratic programming problems
• Solving a class of linearly constrained indefinite quadratic problems by DC algorithms
• A combined d.c. optimization--ellipsoidal branch-and-bound algorithm for solving nonconvex quadratic programming problems
• Simplicially-constrained DC optimization over efficient and weakly efficient sets
• Exact penalty in d. c. programming
• The DC (Difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems
• A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
• Obtaining test problems via Internet
• Decomposition branch and bound method for globally solving linearly constrained indefinite quadratic minimization problems
• Graph separation techniques for quadratic zero-one programming
• Computational aspects of a branch and bound algorithm for quadratic zero- one programming
• Adaptive Memory Tabu Search for Binary Quadratic Programs
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• A D.C. Optimization Algorithm for Solving the Trust-Region Subproblem
• Large-Scale Molecular Optimization from Distance Matrices by a D.C. Optimization Approach
• A Spectral Bundle Method for Semidefinite Programming
• On globally solving linearly constrained indefinite quadratic minimization problems by decomposition branch and bound method
• Combining DCA (DC Algorithms) and interior point techniques for large-scale nonconvex quadratic programming
• Quadratic Binary Programming with Application to Capital-Budgeting Problems
• Handbook of semidefinite programming. Theory, algorithms, and applications
• Introduction to global optimization.