SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
As a stand-alone solver, SCIP can solve mixed-integer nonlinear programs (MINLPs), to which it applies an LP based spatial branch-and-cut algorithm. This method is guaranteed to solve bounded MINLPs within a given numerical tolerance in a finite amount of time. In particular, SCIP is a stand-alone solver for mixed-integer linear programs (MIPs).
As a framework, SCIP also provides the tools to solve constraint optimization problems defined over integer and continuous variables. Therefore, the design of SCIP supports the easy integration of constraints of arbitrary type into the solver. More precisely, SCIP can handle the class of constraint integer programs (CIPs), which are constraint optimization problems that become linear programs (LPs) after the integer variables are fixed.
The following table gives a non-exhaustive list of common types of mathematical optimization problems that can be solved through SCIP itself or one of its extensions. Some recommendations are given on how to compile SCIP for a certain problem class and how make best use of SCIP. The file format column gives some common file formats for every class. Note that since some of the mentioned problem classes are more general than others (like every LP is a MIP is an MINLP), the formats for the superclass should always work just as fine, although they may be less common for the class at hand.
Please see also the pages on SCIP Examples and SCIP Applications to learn more on how to extend SCIP for a particular MIP, MINLP, or CIP application. All examples and applications use the C or C++ APIs of SCIP. Please have a look at SCIP interfaces to see how to use SCIP from within other programming languages.
| Problem class | Mathematical problem description | Supported file formats | Recommendations | |
|---|---|---|---|---|
| Mixed-integer linear program (MIP) | \begin{align*} \text{min} \quad& c^T x \\ \text{s.t.} \quad& Ax \geq b \\ &l_{j} \leq x_{j} \leq u_{j} && \forall j \in \mathcal{N} \\ &x_{j} \in \mathbb{Z} && \forall j \in \mathcal{I} \end{align*} |
| ||
| Mixed-integer nonlinear program (MINLP) | \begin{align*} \text{min} \quad& f(x) \\ \text{s.t.} \quad& g_{i}(x) \leq 0 && \forall i \in \mathcal{M} \\ &l_{j} \leq x_{j} \leq u_{j} && \forall j \in \mathcal{N} \\ &x_{j} \in \mathbb{Z} && \forall j \in \mathcal{I} \end{align*} |
| ||
| Constraint Integer Program (CIP) | \begin{align*} \text{min} \quad& c^T x + d^T y \\ \text{s.t.} \quad& C_i(x,y) = \text{true} && \forall i \in \mathcal{M} \\ & x \in \mathbb{Z}^{p}, y \in \mathbb{R}^{n - p} \end{align*} where \(\forall i \in\mathcal{M}, \forall x^* \in \mathbb{Z}^{p},\) \( \{ y : C_i(x^*, y) = \text{true} \} \) is a polyhedron. |
| ||
| Convex MINLP | Like MINLP, \(f\) and all \(g_i\) are convex. | see MINLP formats |
| |
| Linear program (LP) | \begin{align*} \text{min} \quad& c^T x \\ \text{s.t.} \quad& Ax \geq b \\ & x_{j} \geq 0 && \forall j \in \mathcal{N} \end{align*} | see MIP formats | See Can I use SCIP as a pure LP solver in the FAQ. | |
| Pseudoboolean optimization | \begin{align*} \text{min} \quad& c^T x \\ \text{s.t.} \quad& \sum_{k=0}^p a_{ik} \cdot \prod_{j \in \mathcal{N}_{ik}} x_j \leq b_i && \forall i \in \mathcal{M} \\ &x_{j} \in \{0,1\} && \forall j \in \mathcal{N} \end{align*} |
| ||
| Satisfiability (SAT) and variants | \begin{align*} \text{min} \quad& 0 \\ \text{s.t.} \quad&\bigvee\limits_{j \in B_i} x_j \vee \bigvee\limits_{j \in \bar{B}_i} \neg x_j = \text{true} && \forall i \in \mathcal{M}\\ &x_{j} \in \{\text{false},\text{true}\} && \forall j \in \mathcal{N} \end{align*} |
| ||
| Multicriteria optimization | \begin{align*} \text{min} \quad &(c_1^T x,\ldots,c_k^T x) \\ \text{s.t. } \quad& Ax \geq b \\ &x \in \mathbb{K}^n \end{align*} where \(\mathbb{K}\) is either \(\mathbb{Z}\) or \(\mathbb{R}\). | see the PolySCIP web page | ||