{"id":"arxiv/2608.29945","url":"https://arxiv.org/abs/2608.29945","tags":["math.OC"],"score":0,"title":"Sharp Singularity-Degree Bounds for Equality-Generated SDP-RLT Relaxations of Binary Programs","domain":"math.OC","source":"arxiv","authors":["Hao Hu"],"reviews":0,"subject":"math.OC","summary":"Singularity degree is an important measure of semidefinite programming (SDP) degeneracy, but it is generally unavailable a priori from the problem data. We augment the Shor relaxation of nonempty binary sets $\\{x\\in\\{0,1\\}^n:Ax=b\\}$ with the first-level Reformulation-Linearization Technique (RLT) equations generated by the defining linear equalities. For the resulting equality-generated SDP-RLT relaxation, we determine the exact worst-case singularity degree. If $\\operatorname{rank}(A)=m$ and $0<m<n$, then the associated relaxation has singularity degree at most $\\min\\{m,n-m\\}$, and this…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-30","reactions":{}}