Presolving for Mixed-Integer Semidefinite Optimization

This paper provides a discussion and evaluation of presolving methods for mixed-integer semidefinite programs. We generalize methods from the mixed-integer linear case and introduce new methods that depend on the semidefinite condition. The methods considered include adding linear constraints, deriving bounds relying on 2 × 2 minors of the semidefinite constraints, tightening of variable bounds based on solving a semidefinite program with one variable, and scaling of the matrices in the semidefinite constraints. Tightening the bounds of variables can also be used in a node presolving step. Along the way, we discuss how to solve semidefinite programs with one variable using a semismooth Newton method and the convergence of iteratively applying bound tightening. We then provide an extensive computational comparison of the different presolving methods, demonstrating their effectiveness with an improvement in running time of about 22% on average. The impact depends on the instance type and varies across the methods.

Funding: This work was supported by the EXPRESS II project within the German Research Foundation (Deutsche Forschungsgemeinschaft, DFG) priority program CoSIP (DFG-SPP 1798). It was also partly supported by the DFG within Project A4 in the SFB 805.