On the Singularity Degree of Shor Relaxations for 0-1 Programs
Shor relaxations are standard tools for nonconvex quadratic optimization, but they may fail Slater's condition. The singularity degree quantifies this degeneracy by the number of facial-reduction steps needed to reach the minimal face. We determine how the constraints defining a binary feasible set affect this quantity. For every nonempty binary set defined by linear equations and inequalities, the Shor relaxation has singularity degree at most one. It is zero precisely when the linear programming (LP) relaxation contains a point in the open cube that strictly satisfies every inequality, and…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.12476
curl -X POST /api/v1/records/arxiv/2607.12476/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.12476/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'