Solving Constraint Integer Programs

What types of optimization problems does SCIP solve?

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.

Some important subclasses of CIP and MINLP

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.

Some problem classes that can be solved by SCIP
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*}

  • SCIP requires an external LP solver to solve LP relaxations, which needs to be specified at compilation time. By default, it uses SoPlex (LPS=spx). See Makefiles / Installation information for a list of available LP solver interfaces and how to use them inside SCIP.
  • Compile with Zimpl support (ZIMPL=true) to read in Zimpl models directly.
  • SCIP comes with many different parameters. Use the provided emphasis settings (see this tutorial) to change many parameters at once and boost the performance.
  • Test instances are available at check/instances/MIP/.
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*}

  • Compile with IPOPT=true for better performance.
  • Compile with GAMS=true to read gms-files.
  • See Which kind of MINLPs are supported by SCIP? in the FAQ.
  • There is an interface for the modelling language AMPL, see Interfaces.
  • Mixed-integer quadratically constrained programs (MIQCP) can also be formulated in the file formats
  • Test instances are available at check/instances/MINLP/.
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.
  • SCIP supports a limited number of general constraints; see How to add constraint handlers to learn how to extend the SCIP framework to a given CIP.
  • Use the emphasis setting set emphasis cpsolver to completely disable LP solves and use depth-first search with periodic restarts, see also Can I use SCIP as a pure CP solver? in the FAQ.
  • Test instances are available at check/instances/CP.
Convex MINLP Like MINLP, \(f\) and all \(g_i\) are convex. see MINLP formats
  • See the comments for MINLP.
  • In addition, use constraints/nonlinear/assumeconvex = TRUE to inform SCIP about a convex problem in cases where the automated detection is not strong enough.
  • Test instances are available at check/instances/MINLP/circle.cip.
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*}

  • Test instances are available at check/instances/PseudoBoolean/.
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*}

  • Use the emphasis setting set emphasis cpsolver to completely disable LP solves and use depth-first search with periodic restarts, see also Can I use SCIP as a pure CP/SAT solver? in the FAQ.
  • Test instances are available at check/instances/SAT/.
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