4 papers · 1 filter
Face Identification via Polyhedral Relaxations for Binary Programs: A Comparison with Factor-Width Partial Facial Reduction
Hao Hu, Blake Smith, Mingming Xu
Facial reduction (FR) is a preprocessing technique used to restore Slater's condition in semidefinite programming (SDP), but each step generally requires solving an auxiliary SDP.…
A Primal Approach to Facial Reduction for SDP Relaxations of Combinatorial Optimization Problems
Hao Hu, Mingming Xu
We propose a novel facial reduction algorithm tailored to semidefinite programming relaxations of combinatorial optimization problems with quadratic objective functions. Our method…
Face Structure in Partial Facial Reduction of Semidefinite Relaxations of Binary Programs
Hao Hu, Mingming Xu
Semidefinite relaxations of binary optimization problems often fail Slater's condition. Full facial reduction restores strict feasibility but may require auxiliary problems as cost…
SDP Approach to Quadratic Vertex-Disjoint Paths Problem
Mingming Xu, Hao Hu
We study the quadratic -vertex-disjoint paths problem (Q--VDP), which seeks vertex-disjoint paths in a directed graph that minimize a nonconvex quadratic objective functi…