Affine Facial Reduction for Semidefinite Relaxations of Binary and Mixed-Binary Optimization Problems

Abstract

Semidefinite programming (SDP) relaxations can provide strong bounds for binary and mixed-binary optimization problems, but their practical use is often limited by matrix variables of large order and by failures of Slater's condition, which can contribute to numerical difficulties for interior-point solvers. We propose \emph{affine facial reduction (affine FR)}, an automatic, LP-based preprocessing method for SDP relaxations of such problems. The method uses the affine hull of the linear programming relaxation to construct a positive semidefinite face containing the lifted feasible set and an associated facial range vector, thereby replacing the original positive semidefinite matrix variable by one of lower order. The required affine-hull information is obtained by solving a single linear programming problem, followed by linear-algebraic computations. We analyze the relation between affine FR, analytical facial reduction, the Permenter--Parrilo partial FR method, and Sieve-SDP, and establish explicit comparisons among the resulting matrix orders for the Shor relaxation. On MIPLIB 2017 mixed-binary instances, affine FR reduces matrix order more often and by a larger amount than the partial-FR variants considered, with comparable preprocessing times. On selected SAT relaxations with substantial reductions, affine FR can shorten SDP solution times and yield more reliable solver outcomes when the unreduced formulations encounter numerical difficulties.