Face Identification via Polyhedral Relaxations for Binary Programs: A Comparison with Factor-Width Partial Facial Reduction

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. Factor-width-$k$ partial FR restricts the class of exposing matrices. Increasing $k$ enlarges this class, but, for $k\ge 3$, the auxiliary problem remains an SDP involving positive semidefinite blocks of order $k$. For SDP relaxations of binary programs, we replace this auxiliary SDP by an LP-based face-identification method. We construct a polyhedron in subset-indexed moment variables that has polynomial size for fixed $k$. The resulting face contains every feasible binary lift and is contained in every face exposed by a factor-width-$k$ exposing matrix from the same auxiliary system. Thus, linear programming identifies a face no larger than those obtained from the factor-width-$k$ auxiliary SDP while preserving all feasible binary points. To iterate the construction, we represent each identified face by linear equations in the original matrix variable, thereby retaining the moment-matrix indexing and the factor-width comparison at every iteration.