Scippy

SCIP-SDP

a mixed integer semidefinite programming plugin for SCIP

About

SCIP-SDP is a plugin for SCIP to solve mixed integer semidefinite programs (MISDPs) of the form \[ \begin{aligned} \inf \quad \thinspace & b^\top y \\ \text{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} \] 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 documentation.

News

March 2017 SCIP-SDP 3.0.0 is released for SCIP 4.0.0 and DSDP 5.8 or SDPA 7.3.8 or MOSEK 8.0.0.x
May 2016 SCIP-SDP 2.1.0 is released for SCIP 3.2.1 and DSDP 5.8 or SDPA 7.3.8
June 2015 SCIP-SDP 2.0.0 is released for SCIP 3.2.0 and DSDP 5.8 or SDPA 7.3.8
July 2012 SCIP-SDP 1.0 is released for SCIP 3.0.0 and DSDP 5.8


License

This program is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

Copyright (C) 2011-2013 Discrete Optimization, TU Darmstadt
EDOM, FAU Erlangen-Nürnberg
2014-2017 Discrete Optimization, TU Darmstadt


It is based on SCIP - Solving Constraint Integer Programs. SCIP is distributed under the terms of the SCIP Academic Licence, see file COPYING in the SCIP distribution.

Copyright (C) 2002-2017 Zuse Institute Berlin


Any publication for which SCIP-SDP is used should include an acknowledgment and a reference to the following article:

A preprint, an online supplement with detailed results and the corresponding instances (CBF / SDPA-format) are also available.

Bugs

If you find any bugs, it would be nice if you send a description together with a data file that shows the problem to Tristan Gally.

Developers

Main developers

Tristan Gally
Marc Pfetsch

Former main developers

Sonja Mars
Lars Schewe

Contributors

Henrik Alsing Friberg
Ambros Gleixner
Jakob Schelbert

Download

The files you can download here come without any warranty. Use at your own risk! Please refer to the provided INSTALL file for help on installing the software.


You can download the source code here:

Old versions from the following list can also be downloaded:

Cooperation

SCIP-SDP is developed in subproject A4 of the Collaborative Research Centre 805 – Control of Uncertainty in Load-Carrying Structures in Mechanical Engineering funded by the German Research Foundation.

SFB 805
DFG