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} \] 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:

• DSDP
• SDPA
• MOSEK

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.

News

Literature

The following articles cover many ideas implemented in SCIP-SDP:

• A Framework for Solving Mixed-Integer Semidefinite Programs
  Tristan Gally, Marc E. Pfetsch, and Stefan Ulbrich
  Optimization Methods and Software, 33(3):594-632, 2018.
  DOI: 10.1080/10556788.2017.1322081, Preprint: Optimization Online
  An online supplement with detailed results and the corresponding instances (CBF / SDPA-format) are also available.
• Presolving for Mixed-Integer Semidefinite Optimization
  Frederic Matter and Marc E. Pfetsch
  INFORMS Journal on Optimization 5, No. 2, 131-154 (2022)
  DOI:10.1287/ijoo.2022.0079, Preprint: Optimization Online
  Detailed results and problem data.
• Handling Symmetries in Mixed-Integer Semidefinite Programs
  Christopher Hojny, Marc E. Pfetsch Proc. of CPAIOR 2023, 69-78
  DOI:10.1007/978-3-031-33271-5_5, Preprint: Optimization Online.

License

This program is licensed under the Apache License, Version 2.0.

It is based on SCIP - Solving Constraint Integer Programs, Copyright (C) 2002-2024 Zuse Institute Berlin.

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 Marc Pfetsch.

Developers

Main developers

Former main developers

Contributors

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:

• scipsdp-4.3.0.tgz

Old versions from the following list can also be downloaded:

• scipsdp-4.2.0.tgz
• scipsdp-4.1.0.tgz
• scipsdp-4.0.0.tgz
• scipsdp-3.2.0.tgz
• scipsdp-3.1.2.tgz
• scipsdp-3.1.1.tgz
• scipsdp-3.1.0.tgz
• scipsdp-3.0.1.tgz
• scipsdp-3.0.0.tgz
• scipsdp-2.1.0.tgz
• scipsdp-2.0.0.tgz
• scipsdp-1.0.zip

Cooperation

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.