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 considered methods include adding linear constraints, bounds relying on 2 × 2 minors of the semidefinite constraints, bound tightening based on solving a semidefinite program with one variable, and scaling of the matrices in the semidefinite constraints. Tightening variable bounds can also be used in a node presolving step. Along the way, we discuss the solution of 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.

Article

Download

View PDF