Improved SDP Bounds for Binary Quadratic Programming
Downloads
As a classical combinatorial problem, the binary quadratic programming problem has many applications in finance, statistics, production management, etc. The state-of-the-art solution for solving this problem accurately is based on branch-and-bound frameworks, with the low bound support of a semi-definite programming (SDP) relaxation. This paper generalizes the spectral bounds in the literature and proposes a sequence of improved SDP bounds for the binary quadratic programming problem. Our method relies on the closest binary points to an affine space, which can be found by reverse enumeration technique.
D. Avis and K. Fukuda. Reverse search for enumeration. Discrete Applied Mathematics, 65(1-3): 21–46, 1996.
W. Ben-Ameur and J. Neto. Spectral bounds for the maximum cut problem. Networks, 52(1):8–13, 2008.
W. Ben-Ameur and J. Neto. Spectral bounds for unconstrained (-1,1)- quadratic optimization problems. European Journal of Operational Research, 207(1):15–24, 2010.
A. Billionnet and S. Elloumi. Using a mixed integer quadratic programming solver for the unconstrained quadratic 0-1 problem. Mathematical programming, 109(1):55–68, 2007.
H. Edelsbrunner. Algorithms in combinatorial geometry, volume 10. Springer Verlag, 1987.
T. Gerstner and M. Holtz. Algorithms for the cell enumeration and orthant decomposition of hyperplane arrangements. Technical report, Citeseer, 2006.
M.X. Goemans and D.P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semi definite programming. Jour-nal of the ACM (JACM), 42(6):1115–1145, 1995.
C. Helmberg and F. Rendl. Solving quadratic (0, 1)-problems by semi definite programs and cutting planes. Mathematical Programming, 82(3):291–315, 1998.
U. Malik, IM Jaimoukha, GD Halikias, and SK Gungah. On the gap between the quadratic integer programming problem and its semi definite relaxation. Mathematical programming, 107(3):505–515, 2006.
F. Rendl, G. Rinaldi, and A. Wiegele. Solving max-cut to optimality by in-tersecting semidefinite and polyhedral relaxations. Mathematical Programming, 121(2):307–335, 2010.
N.H. Sleumer. Output-sensitive cell enumeration in hyperplane arrangements. Nordic Journal of Computing, 6(2):137–147, 1999.
XL Sun, CL Liu, D. Li, and JJ Gao. On duality gap in binary quadratic pro-gramming. Journal of Global Optimization, (online):1–15, 2011.
X.L. Sun Y. Xia, R.L. Sheu and D. Li. Improved estimation of duality gap in binary quadratic programming using a weghted distance measure. Submitted for publication, 2011.
T. Zaslavsky. Facing up to arrangements: face-count formulas for partitions of space by hyperplanes. American Mathematical Society, Providence, 1975.
X. Zheng, X. Sun, D. Li, and Y. Xia. Duality gap estimation of linear equality constrained binary quadratic programming. Mathematics of Operations Re-search, 35(4):864–880, 2010.
All Content should be original and unpublished.
