|
SCIP-SDP
4.2.0
|
SCIP-SDP is a plugin for SCIP to solve mixed integer semidefinite programs (MISDPs) of the form
\begin{equation*} \begin{aligned} \inf \quad & b^T y && \\ \mbox{s.t.} \quad & \sum_{i = 1}^m A_i y_i - A_0 \succeq 0,&& \\ & y_i \in \mathbb{Z} && \forall \ i \in \mathcal{I}. \end{aligned} \end{equation*}
SCIP-SDP allows to solve MISDPs using a nonlinear branch-and-bound approach or a linear programming cutting-plane approach. In the first case (the default), the semidefinite programming (SDP) relaxations are solve using interior-point SDP-solvers. In the second case, cutting planes based on eigenvector are generated. SCIP-SDP is based on the branch-and-cut framework SCIP. In addition to providing a constraint handler for SDP-constraints and a relaxator to solve continuous SDP-relaxations using interior-point solvers, SCIP-SDP adds several heuristics and propagators to SCIP.
The MISDPs can be read in using either an extended SDPA-format or the CBF-format. There is also an interface for Matlab/Octave on GitHub.
To use the nonlinear branch-and-bound approach one of the following SDP-solvers needs to be installed:
Mixed-integer semidefinite programs are sometimes numerically challenging to solve. One reason is that the Slater condition may not hold for the SDP-relaxations of some of the nodes. SCIP-SDP implements several methods that try to recover from a failure to accurately solve the relaxation.
1.8.17