SCIP-SDP
a mixed integer semidefinite programming plugin for SCIP
a mixed integer semidefinite programming plugin for SCIP
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} \] 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.
| June 2023 | SCIP-SDP 4.2.0 is released for SCIP 8.0.3 and DSDP 5.8 or SDPA 7.3.8 or MOSEK 9.x or 10.x |
| December 2022 | SCIP-SDP 4.1.0 is released for SCIP 8.0.2 and DSDP 5.8 or SDPA 7.3.8 or MOSEK 9.x or 10.x |
| October 2021 | New paper "Presolving for Mixed-Integer Semidefinite Optimization": paper and data. |
| September 2021 | SCIP-SDP 4.0.0 is released for SCIP 8.0.0 and DSDP 5.8 or SDPA 7.3.8 or MOSEK 9.x |
| March 2021 | Updated interface to Matlab/Octave at GitHub based on the OPTI Toolbox. |
| March 2020 | SCIP-SDP 3.2.0 is released for SCIP 7.0.0 and DSDP 5.8 or SDPA 7.3.8 or MOSEK 9.x |
| June 2019 | SCIP-SDP 3.1.2 is released for SCIP 6.0.2 and DSDP 5.8 or SDPA 7.3.8 or MOSEK 9.x |
| June 2018 | SCIP-SDP 3.1.1 is released for SCIP 6.0.0 and DSDP 5.8 or SDPA 7.3.8 or MOSEK 8.1.x |
| December 2017 | SCIP-SDP 3.1.0 is released for SCIP 5.0.0 and DSDP 5.8 or SDPA 7.3.8 or MOSEK 8.1.x |
| September 2017 | SCIP-SDP 3.0.1 is released for SCIP 4.0.1 and DSDP 5.8 or SDPA 7.3.8 or MOSEK 8.1.x |
| 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 |
This program is licensed under the Apache License, Version 2.0.
| Copyright (C) | 2011-2013 | Discrete Optimization, TU Darmstadt |
| EDOM, FAU Erlangen-Nürnberg | ||
| 2014-2023 | Discrete Optimization, TU Darmstadt |
It is based on SCIP - Solving Constraint Integer Programs, Copyright (C) 2002-2023 Zuse Institute Berlin.
Any publication using SCIP-SDP should include an acknowledgment and a reference to the following article:
If you find any bugs, it would be nice if you send a description together with a data file that shows the problem to Marc Pfetsch.
| Marc Pfetsch |
| Frederic Matter | (developer from version 3.2.0 to 4.0.0) |
| Tristan Gally | (main development from version 2.0.0 to 3.1.1) |
| Sonja Mars | (original program creator, version 1.0) |
| Lars Schewe | (support for version 1.0) |
| Christopher Hojny |
| Henrik Alsing Friberg |
| Ambros Gleixner |
| Jakob Schelbert |
| Tim Schmidt (reader_sdpa) |
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:
Parts of SCIP-SDP were developed in Subproject A4 of the Collaborative Research Centre 805 – Control of Uncertainty in Load-Carrying Structures in Mechanical Engineering and in the EXPRESS project within the priority program 1798 CoSIP, both funded by the German Research Foundation.