Most mixed-integer programs have sparse constraint matrices in the sense that most columns and rows have only very few nonzero entries, maybe except for a few outlier columns/rows with many nonzeros. A decomposition identifies subproblems (subsets of rows and columns) that are only linked to each other via a set of linking rows and/or linking columns, but are otherwise independent. The special case of completely independent subproblems (with no linking rows and columns), for example, can be solved by solving the much smaller subproblems and concatenating their optimal solutions. This case has already been integrated into SCIP as a successful presolving technique (see cons_components.c). Another use of decomposition within SCIP is the Benders Decomposition framework.

Since SCIP 7.0, it is easier to pass user decompositions to SCIP that can be used within Benders decomposition or by user algorithms. This page introduces the struct SCIP_DECOMP and gives examples how to create and use it.

Overview

In the following, we present decompositions of mixed-integer programs. However, the generalization to Constraint Integer Programs is straightforward.

Concretely, for \(k \geq 0\) we call a partition \(\mathcal{D}=(D^{\text{row}},D^{\text{col}})\) of the rows and columns of the constraint matrix \(A\) into \(k + 1\) pieces each,

\[ D^{\text{row}} = (D^{\text{row}}_{1},\dots,D^{\text{row}}_{k},L^{\text{row}}), \quad D^{\text{col}} = (D^{\text{col}}_{1},\dots,D^{\text{col}}_{k},L^{\text{col}}) \]

a decomposition of \(A\) if \(D^{\text{row}}_{q} \neq \emptyset\), \(D^{\text{col}}_{q} \neq \emptyset\) for \(q \in \{1,\dots,k\}\) and if it holds for all \(i\in D^{\text{row}}_{q_{1}}, j\in D^{\text{col}}_{q_{2}}\) that \(a_{i,j} \neq 0 \Rightarrow q_{1} = q_{2}\). The special rows \(L^{\text{row}}\) and columns \(L^{\text{col}}\), which may be empty, are called linking rows and linking columns, respectively. In other words, the inequality system \(A x \geq b\) can be rewritten with respect to a decomposition \(\mathcal{D}\) by a suitable permutation of the rows and columns of \(A\) as equivalent system

\[ \left( \begin{matrix} A_{[D^{\text{row}}_{1},D^{\text{col}}_{1}]} & 0 & \cdots & 0 & A_{[D^{\text{row}}_{1},L^{\text{col}}]}\\ 0 & A_{[D^{\text{row}}_{2},D^{\text{col}}_{2}]} & 0 & 0 & A_{[D^{\text{row}}_{2},L^{\text{col}}]}\\ \vdots & 0 & \ddots & 0 & \vdots\\ 0 & \cdots & 0 & A_{[D^{\text{row}}_{k},D^{\text{col}}_{k}]} & A_{[D^{\text{row}}_{k},L^{\text{col}}]}\\ A_{[L^{\text{row}},D^{\text{col}}_{1}]} & A_{[L^{\text{row}},D^{\text{col}}_{2}]} & \cdots & A_{[L^{\text{row}},D^{\text{col}}_{k}]} & A_{[L^{\text{row}},L^{\text{col}}]} \end{matrix} \right) \left( \begin{matrix} x_{[D^{\text{col}}_{1}]}\\ x_{[D^{\text{col}}_{2}]}\\ \vdots\\ x_{[D^{\text{col}}_{k}]}\\ x_{[L^{\text{col}}]} \end{matrix} \right) \geq \left( \begin{matrix} b_{[D^{\text{row}}_{1}]}\\ b_{[D^{\text{row}}_{2}]}\\ \vdots\\ b_{[D^{\text{row}}_{k}]}\\ b_{[L^{\text{row}}]} \end{matrix} \right) % A= \left(\begin{matrix}4&8&\frac{1}{2}\\\frac{3}{2}&4&1\\1&3&7\end{matrix}\right) \]

where we use the short hand syntax \(A_{[I,J]}\) to denote the \(|I|\)-by- \(|J|\) submatrix that arises from the deletion of all entries from \(A\) except for rows \(I\) and columns \(J\), for nonempty row and column subsets \(I\subseteq\{1,\dots,m\}\) and \(J\subseteq\{1,\dots,n\}\).

Using a decomposition

After passing one or more decompositions, see below, one can access all available decompositions with SCIPgetDecomps(). The labels can be obtained by calling SCIPdecompGetVarsLabels() and SCIPdecompGetConsLabels(). If some variables/constraints are not labeled, these methods will mark them as linking variables/constraints. There are several methods to get more information about one decomposition, see Decomposition data structure.

A decomposition can be used to split the problem into several subproblems which, in general, are easier to solve. For \(q \in \{1,\dots,k\}\) the system

\[ A_{[D^{\text{row}}_{q},D^{\text{col}}_{q}]}\; x_{[D^{\text{col}}_{q}]} \geq b_{[D^{\text{row}}_{q}]} \]

is part of subproblem \(q\), the handling of the linking variables/constraints depends on the chosen application context. For example, in the heuristic heur_padm.c several smaller subproblems are solved multiple times to get a feasible solution. Also the Benders' decomposition framework was extended with release 7.0 to use user decompositions.

Creation via SCIP-API

There are two different ways to provide a decomposition in SCIP. It can be created with the SCIP-API or it can be read from a file.

To create it with the API, the user must first create a decomposition with SCIPcreateDecomp() specifying whether the decomposition belongs to the original or transformed problem and the number of blocks. Then the variables and constraints can be assigned to one block or to the linking rows/columns by calling SCIPdecompSetVarsLabels() and SCIPdecompSetConsLabels(), respectively. To complete the decomposition or to ensure that it is internally consistent, SCIPcomputeDecompVarsLabels() or SCIPcomputeDecompConsLabels() can be called. Note that SCIPcomputeDecompVarsLabels() will ignore the existing variable labels and computes again the labels based on the constraint labels only; SCIPcomputeDecompConsLabels() works in the same way and ignores the existing constraint labels.

After the decomposition has been successfully created, it can be saved for later use in the DecompStore using SCIPaddDecomp(). Access to all decompositions in the DecompStore is possible with SCIPgetDecomps().

Reading a decomposition from a file

Alternatively, after a problem has been read, a related decomposition can be read from a dec-file. Please refer to the DEC file reader for further information about the required file format. Upon reading a valid dec-file, a decomposition structure is created, where the corresponding variable labels are inferred from the constraint labels, giving precedence to block over linking constraints.

Use for Benders

If the variables should be labeled for the application of Benders' decomposition, the decomposition must be explicitly flagged by setting the parameter decomposition/benderslabels to TRUE. With this setting, the variable's labeling takes place giving precedence to its presence in linking constraints over its presence in named blocks.

Decomposition after problem transformation

As the problem's constraints are constantly changing, or possibly deleted, during presolving, the constraints' labeling must be triggered again. Therefore, SCIP automatically transforms all user decompositions at the beginning of the root node based on the variables' labels.

Decomposition statistics

Further useful measures and statistics about the decomposition are computed within SCIPcomputeDecompStats(). When the labeling process is concluded, the following measures are computed and printed:

the number of blocks;
the number of linking variables and linking constraints;
the size of the largest as well as the smallest block;
the area score: This score is also used by GCG to rank decompositions during the automatic detection procedure. For a decomposition \(\mathcal{D}=(D^{\text{row}},D^{\text{col}})\), the area score is defined as
\[ \text{areascore}(\mathcal{D}) = 1 - \frac{ \sum_{q=1}^k \lvert D^{\text{row}}_{q} \rvert \lvert D^{\text{col}}_{q} \rvert + n\lvert L^{\text{row}} \rvert + m\lvert L^{\text{col}} \rvert - \lvert L^{\text{row}} \rvert \lvert L^{\text{col}} \rvert }{mn} \enspace. \]
In the case of a mixed-integer program, the area score intuitively measures the coverage of the rearranged matrix by 0's. Decompositions with few linking variables and/or constraints and many small blocks \(A_{[D^{\text{row}}_{q},D^{\text{col}}_{q}]}\) will have an area score close to \(1\), whereas coarse decompositions of a matrix have smaller area scores. The trivial decomposition with a single block has the worst possible area score of 0.
the modularity: This measure is used to assess the quality of the community structure within a decomposition. The modularity of the decomposition is computed as follows:
\[ \begin{aligned} \sum_{q=1}^{k} \dfrac{e_{q}}{m} \left(1-\dfrac{e_{q}}{m}\right), \end{aligned} \]
where \(e_{q}\) is the number of inner edges within block \(q\) and \(m\) is the total number of edges. The presence of an inner edge is identified through the presence of a variable in a constraint, both—the variable and the constraint—belonging to the same block.
the block graph statistics: A block graph is constructed with the aim of depicting the connection between the different blocks in a decomposition through the existing linking variables in the constraints. Note that the linking constraints are intentionally skipped in this computation. \( G = (V,E) \) denotes a block graph, with vertex set \(V\) and edge set \(E\). Each vertex in the graph represents a block in the decomposition; \(V = \{v_{1},\dots,v_{k}\}\). An edge \(e = \{ v_{s},v_{t} \}\) is added to \(G\), if and only if there exists a column \(\ell \in L^{\text{col}}\), a row \(i \in D^{\text{row}}_{s}\) and a row \(j \in D^{\text{row}}_{t}\), such that \(a_{i,\ell} \neq 0\) and \(a_{j,\ell} \neq 0\). From the constructed graph, the number of edges, articulation points and connected components are computed, together with the maximum and minimum degree. Note that building the block graph can become computationally expensive with large and dense decompositions. Thus, it is possible through a user parameter decomposition/maxgraphedge to define a maximum edge limit. The construction process will be interrupted once this limit is reached, in which case only approximate estimations of the block graph statistics will be displayed and accompanied with a warning message.