Hao Hu

Sharp Singularity-Degree Bounds for Equality-Generated SDP–RLT Relaxations of Binary Programs

Categories Convex Optimization, Semi-definite Programming

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 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 … Read more

A Primal Approach to Facial Reduction for SDP Relaxations of Combinatorial Optimization Problems

Categories (Mixed) Integer Linear Programming, Convex Optimization

We propose a novel facial reduction algorithm tailored to semidefinite programming relaxations of combinatorial optimization problems with quadratic objective functions. Our method leverages the specific structure of these relaxations, particularly the availability of feasible solutions that can often be generated efficiently in practice. By incorporating such solutions into the facial reduction process, we substantially simplify … Read more