Efficient semidefinite relaxation for Boolean quadratic programming problems with generalized upper bound constraints via row-by-row method

Articles in Press

Document Type : Original paper

Authors

Department of Mathematics, IIIT Bhubaneswar, Odisha, India

Abstract

This study focuses on the low-complexity implementation of semidefinite relaxation (SDR) to generate bounds for the Boolean Quadratic Programming Problem with Generalized Upper Bound Constraints (BQP-GUB). Most current SDR approaches rely on interior-point methods (IPM), which, despite having worst-case polynomial complexity, can be computationally expensive in practice. We depart from the IPM framework and investigate the use of other low per-iteration-complexity techniques for the solution of BQP-GUB. Specifically, we apply the row-by-row (RBR) method, called NuclearRBR, to solve the semidefinite programs that emerge from reformulating the BQP-GUB as an unconstrained Boolean Quadratic Programming Problem (UBQP). In this formulation, a nonconvex rank-one constraint is relaxed by a convex nuclear norm constraint. The RBR method only requires matrix-vector multiplications in each iteration, making it highly efficient. Numerical results demonstrate that NuclearRBR outperforms the semidefinite dual (SDD) method and other similar existing methods like SDcutRBR method [R.K. Nayak and N.K. Mohanty, Improved row-by-row method for binary quadratic optimization problems, Ann. Oper. Res. 275 (2019), 2, 587–605].

Keywords

Main Subjects

References

[1] E.A. Anacleto, C.N. Meneses, and R.N. Liang, Fast r-flip move evaluations via closed-form formulae for boolean quadratic programming problems with generalized upper bound constraints, Comput. Oper. Res. 132 (2021), 105297.
https://doi.org/10.1016/j.cor.2021.105297
[2] M. ApS, Mosek optimization toolbox for matlab, User’s Guide and Reference Manual, Version 4 (2019), no. 1, p.116.
[3] J.E. Beasley, Heuristic algorithms for the unconstrained binary quadratic programming problem, Tech. report, Working Paper, The Management School, Imperial College, London, England, 1998.
[4] P. Chr´etienne, A polynomial algorithm to optimally schedule tasks on a virtual distributed system under tree-like precedence constraints, European J. Ope. Res. 43 (1989), no. 2, 225–230. https://doi.org/10.1016/0377-2217(89)90216-6
[5] E.D. Demaine, D. Emanuel, A. Fiat, and N. Immorlica, Correlation clustering in general weighted graphs, Theoretical Computer Science 361 (2006), no. 2-3, 172–187. https://doi.org/10.1016/j.tcs.2006.05.008
[6] S. Dhouib, A new column-row method for traveling salesman problem: the dhouib-
matrix-TSP1, International Journal of Recent Engineering Science 8 (2021),
no. 1, 6–10.
https://doi.org/10.14445/23497157/IJRES-V8I1P102.
[7] E. Gelenbe, S. Timotheou, and D. Nicholson, Fast distributed near-optimum assignment of assets to tasks, Comput. J. 53 (2010), no. 9, 1360–1369. https://doi.org/10.1093/comjnl/bxq010
[8] F. Glover, Z. Lū, and J.K. Hao, Diversification-driven tabu search for unconstrained binary quadratic problems, 4OR 8 (2010), no. 3, 239–253. https://doi.org/10.1007/s10288-009-0115-y
[9] M. Grant and S. Boyd, Cvx: Matlab software for disciplined convex programming, version 2.1, 2014.
[10] M. Grant, S. Boyd, and Y. Ye, Cvx: Matlab software for disciplined convex programming, 2008.
[11] S. Guattery and G.L. Miller, On the quality of spectral separators, SIAM J. Matrix Anal. Appl. 19 (1998), no. 3, 701–719.
https://doi.org/10.1137/S0895479896312262
[12] M. Heiler, J. Keuchel, and C. Schn¨orr, Semidefinite clustering for image segmentation with a-priori knowledge, Joint Pattern Recognition Symposium, Springer, 2005, pp. 309–317.
[13] A. Joulin, F. Bach, and J. Ponce, Discriminative clustering for image cosegmentation, 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, IEEE, 2010, pp. 1943–1950. https://doi.ieeecomputersociety.org/10.1109/CVPR.2010.5539868
[14] R. Kannan, S. Vempala, and A. Vetta, On clusterings: Good, bad and spectral, Journal of the ACM (JACM) 51 (2004), no. 3, 497–515. https://doi.org/10.1145/990308.990313
[15] J. Kleinberg and E. Tardos, Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields, Journal of the ACM (JACM) 49 (2002), no. 5, 616–639. https://doi.org/10.1145/585265.585268
[16] K. Lang, Fixing two weaknesses of the spectral method, Advances in Neural Information Processing Systems (Vancouver, British Columbia, Canada).
[17] F. Lauer and C. Schn¨orr, Spectral clustering of linear subspaces for motion segmentation, 2009 IEEE 12th International Conference on Computer Vision, IEEE, 2009, pp. 678–685. https://doi.org/10.1109/ICCV.2009.5459173
[18] Z. L¨u, F. Glover, and J.K. Hao, A hybrid metaheuristic approach to solving the UBQP problem, European J. Oper. Res. 207 (2010), no. 3, 1254–1262. https://doi.org/10.1016/j.ejor.2010.06.039
[19] Z. L¨u, J.K. Hao, and F. Glover, A study of memetic search with multi-parent combination for UBQP, Evolutionary Computation in Combinatorial Optimization: 10th European Conference, EvoCOP 2010, Istanbul, Turkey, April 7-9,
2010. Proceedings 10 (Istanbul, Turkey).
[20] V.S. Mai, D. Maity, B. Ramasubramanian, and M.C. Rotkowitz, Convex methods for rank-constrained optimization problems, 2015 Proceedings of the Conference on Control and its Applications, SIAM, 2015, pp. 123–130. https://doi.org/10.1137/1.9781611974072.18
[21] R.K. Nayak and M.P. Biswal, A low complexity semidefinite relaxation for largescale MIMO detection, J. Comb. Optim. 35 (2018), no. 2, 473–492. https://doi.org/10.1007/s10878–017–0186–1
[22] R.K. Nayak and N.K. Mohanty, Improved row-by-row method for binary quadratic optimization problems, Ann. Oper. Res. 275 (2019), no. 2, 587–605. https://doi.org/10.1007/s10479-018-2978-9
[23] C. Schellewald and C. Schn¨orr, Probabilistic subgraph matching based on convex relaxation, International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition (Mannheim, Germany).
[24] Z. Shang, J.K. Hao, S. Zhao, Y. Wang, and F. Ma, Multi-wave tabu search for the boolean quadratic programming problem with generalized upper bound constraints, Comput. Oper. Res. 150 (2023), 106077. https://doi.org/10.1016/j.cor.2022.106077
[25] J. Shi and J. Malik, Normalized cuts and image segmentation, IEEE Transactions on pattern analysis and machine intelligence 22 (2000), no. 8, 888–905. https://doi.org/10.1109/34.868688
[26] S.N. Vitaladevuni and R. Basri, Co-clustering of image segments using convex optimization applied to EM neuronal reconstruction, 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, IEEE, 2010, pp. 2203–2210. https://doi.org/10.1109/CVPR.2010.5539901
[27] H.T. Wai, W.K. Ma, and A.M.C. So, Cheap semidefinite relaxation MIMO detection using row-by-row block coordinate descent, 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (Prague, Czech
Republic).
[28] Y. Wang, Z. Lū, F. Glover, and J.K. Hao, Path relinking for unconstrained binary quadratic programming, European J. Oper. Res. 223 (2012), no. 3, 595–604. https://doi.org/10.1016/j.ejor.2012.07.012
[29] Y. Wang, Z. Lū, F. Glover, and J.K. Hao, Backbone guided tabu search for solving the UBQP problem, J. Heuristics 19 (2013), no. 4, 679–695. https://doi.org/10.1007/s10732-011-9164-4
[30] Y. Wang and A.P. Punnen, The boolean quadratic programming problem with generalized upper bound constraints, Comput. Oper. Res. 77 (2017), 1–10. https://doi.org/10.1016/j.cor.2016.07.005
[31] Z. Wen, D. Goldfarb, S. Ma, and K. Scheinberg, Row by row methods for semidefinite programming, Industrial Engineering (2009), 1–21.
[32] S.X. Yu and J. Shi, Segmentation given partial grouping constraints, IEEE Transactions on Pattern Analysis and Machine Intelligence 26 (2004), no. 2, 173–183. https://doi.org/10.1109/TPAMI.2004.1262179
[33] F. Zhang, The schur complement and its applications, vol. 4, Springer Science and Business Media, 2006.
[34] Y. Zhou, J. Wang, Z. Wu, and K. Wu, A multi-objective tabu search algorithm based on decomposition for multi-objective unconstrained binary quadratic programming problem, Knowledge-Based Systems 141 (2018), 18–30.
https://doi.org/10.1016/j.knosys.2017.11.009
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 08 February 2026

Files

Share

How to cite

Statistics