Johanna Skåntorp: Cutting Planes for Outer Approximation in Mixed-Integer Semidefinite Programming

In this work we consider different methods for cut-generation in order to solve mixed-integer semidefinite programs (MISDPs) within the outer approximation (OA) framework. Utilizing duality in semidefinite programming (SDP) the main components of classical outer approximation can easily be adapted for MISDPs; By fixing the integer variables and solving an SDP at each iteration, the resulting algorithm exhibit similar behaviour and convergence properties.

Another approach for cut-generation comes from the cutting-plane algorithm for SDPs, where valid cuts are derived from eigenvectors corresponding to the (most) negative eigenvalues of the relaxed solution. By sidestepping solving an SDP at each iteration, the cost of cut-generation is significantly lower. On the other hand, since no feasible solution are produced, the resulting algorithm differs significantly from classic OA.

In addition to contrasting the two algorithms we propose new methods for generating cuts – with desirable theoretical and computational properties – and present numerical comparisons.