Convex reformulation for binary quadratic programming problems via average objective value maximization

详细信息    查看全文

• 作者：Cheng Lu (1)
  Xiaoling Guo (2)
  
  1. Department of Electronic Engineering ; Tsinghua University ; 100084聽 ; Beijing ; China
  2. College of Engineering and Information Technology ; University of Chinese Academy of Sciences ; 100049聽 ; Beijing ; China
  
• 关键词：Binary quadratic programming ; Lower bounds ; Branch ; and ; bound ; Convex reformulation
• 刊名：Optimization Letters
• 出版年：2015
• 出版时间：March 2015
• 年：2015
• 卷：9
• 期：3
• 页码：523-535
• 全文大小：186 KB
• 参考文献：1. Anjos, M.F., Chang, X.-W., Ku, W.-Y.: Lattice preconditioning for the real relaxation branch-and-bound approach for integer least squares problems. J. Global Optim. (2014)
  2. Anstreicher, KM (2009) Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming. J. Global Optim. 43: pp. 471-484 CrossRef
  3. Billionnet, A, Elloumi, S (2007) Using a mixed integer quadratic programming solver for the unconstrained quadratic 0鈥? Problem. Math. Program. 109: pp. 55-68 CrossRef
  4. Burer, S (2009) On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120: pp. 479-495 CrossRef
  5. Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completeness. Freeman W.H., Madison (1979)
  6. Goemans, MX, Williamson, DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42: pp. 1115-1145 CrossRef
  7. Halikias, GD, Jaimoukha, IM, Malik, U, Gungah, SK (2007) New bounds on the unconstrained quadratic integer problem. J. Global Optim. 39: pp. 543-554 CrossRef
  8. Lemarechal, C, Oustry, F.: SDP relaxations in combinatorial optimization from a Lagrangian point of view. In: Hadjisavvas, N., Pardalos, P. (eds) Proceedings of Advances in Convex Analysis and Global Optimization, pp. 119鈥?34. Kluwer Academic Press, New York (2001)
  9. Lu, C, Wang, Z, Xing, W (2010) An improved lower bound and approximation algorithm for binary constrained quadratic programming problem. J. Global Optim. 48: pp. 497-508 CrossRef
  10. Malik, U, Jaimoukha, IM, Halikias, GD, Gungah, SK (2006) On the gap between the quadratic integer programming problem and its semidefinite relaxation. Math. Program. 107: pp. 505-515 CrossRef
  11. Ma, W-K, Davidson, TN, Wong, KM, Luo, Z-Q, Cing, P-C (2002) Quasi-maximum-likelihood multiuser detection using semi-definite relaxation with application to synchronous CDMA. IEEE Trans. Signal Process. 50: pp. 912-922 CrossRef
  12. Ma, W-K, Su, C-C, Jald茅n, J, Chang, T-H, Chi, C-Y (2009) The equivalence of semidefinite relaxation MIMO detectors for higher-order QAM. IEEE J. Sel. Topics Signal Process. 3: pp. 1038-1052 CrossRef
  13. Pardalos, PM, Rodgers, GP (1990) Computational aspects of a branch and bound algorithm for quadratic zero-one programming. Computing 45: pp. 131-144 CrossRef
  14. Poljak, S, Wolkowicz, H (1995) Convex relaxations of (01)-quadratic programming. Math. Oper. Res. 20: pp. 550-561 CrossRef
  15. Sidiropoulos, ND, Luo, Z-Q (2006) A semidefinite relaxation approach to MIMO detection for higher-order QAM constellations. IEEE Signal Process. Lett. 13: pp. 525-528 CrossRef
  16. Sun, XL, Liu, CL, Li, D, Gao, JJ (2012) On duality gap in binary quadratic programming. J. Global Optim. 53: pp. 255-269 CrossRef
  17. Tan, P, Rasmussen, L (2001) The application of semidefinite programming for detection in CDMA. IEEE J. Sel. Areas Commun. 19: pp. 1142-1449
  18. Vandenberghe, L, Boyd, S (1996) Semidefinite programming. SIAM Rev. 38: pp. 49-95 CrossRef
  19. Wolsey, LA (1998) Integer programming. Wiley, New York
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Optimization
  Operation Research and Decision Theory
  Numerical and Computational Methods in Engineering
  Numerical and Computational Methods
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1862-4480

文摘

Quadratic convex reformulation is an important method for improving the performance of a branch-and-bound based binary quadratic programming solver. In this paper, we study a new convex reformulation method. By this reformulation, the efficiency of a branch-and-bound algorithm can be improved significantly. We also compare this new reformulation method with other proposed methods, whose effectiveness has been proven. Numerical experimental results show that our reformulation method performs better than the compared methods for certain types of binary quadratic programming problems.