SCIP-SDP  3.0.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Tristan Gally, Marc Pfetsch; Sonja Mars, Lars Schewe

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*}

It combines the branch-and-bound framework of SCIP with interior-point SDP-solvers to solve MISDPs using either a nonlinear branch-and-bound approach or an outer-approximation-based cutting-plane approach. In addition to providing a constraint handler for SDP-constraints and a relaxator to solve continuous SDP-relaxations using interior-point solvers, SCIPSDP adds several heuristics and propagators to SCIP. The MISDPs can be read in using either an extended SDPA-format or the CBF-format. To use the nonlinear branch-and-bound approach one of the following SDP-solvers needs to be installed:

The solution process of interior-point methods for SDPs is highly dependent on the Slater condition. One of the main purposes of the code is handling cases where the Slater condition does not hold using a penalty approach. However, in some cases the SDP-solvers may still fail because of numerical difficulties or even return wrong results, which cannot be compensated. For this purpose there is the possibility to check the Slater condition for the primal and dual problem before the solution of each SDP by setting a SCIP parameter, for details see the parameters tab.