Azarbaijan Shahid Madani University Communications in Combinatorics and Optimization 2538-2128 Articles in Press 2026 02 08 Efficient semidefinite relaxation for Boolean quadratic programming problems with generalized upper bound constraints via row-by-row method 15101 10.22049/cco.2026.30575.2540 EN Hitarth Sharma Department of Mathematics, IIIT Bhubaneswar, Odisha, India Rupaj K. Nayak Department of Mathematics, IIIT Bhubaneswar, Odisha, India Journal Article 2025 04 30 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]. https://comb-opt.azaruniv.ac.ir/article_15101_f3e0ec64e7d4a94e6c608ad549a28c2e.pdf