THE TIGHTNESS OF STRENGTHENED SEMIDEFINITE RELAXATIONS FOR THE BOOLEAN QUADRATIC PROGRAMMING PROBLEM WITH GENERALIZED UPPER BOUND CONSTRAINTS
Hitarth Sharma, Rupaj Kumar Nayak
ABSTRACT This paper studies semidefinite programming (SDP) relaxations for the Boolean Quadratic Programming problem with Generalized Upper Bound constraints (BQP-GUB), which arises in several application domains. We show that conventional semidefinite relaxation (SDR) does not yield tight bounds for this problem. We then analyze strengthened SDP relaxations and identify formulations that produce tight or near-tight bounds, particularly those based on reduced reformulation-linearization techniques (SDR+RRLT and SSDR+RRLT. Numerical experiments demonstrate that these approaches significantly reduce the relaxation gap compared to SDR, while highlighting the trade-off between bound quality and computational scalability.
Pesquisa Operacional•Jan 1, 2026•0 citations