This page documents some of the statistics shown on the single instance pages in more detail.

# Trivial Presolving

By trivial presolving we denote a set of simple presolving rules used to preprocess the instances for computing instance features and decompositions. Many of the more elaborate presolving techniques incorporated in modern solvers have been disabled.

Trivial presolving iteratively

• removes fixed variables from the problem
• turns integer variables with bounds $$\{0,1\}$$ into binary variables
• tightens variable bounds by singleton constraints
• tightens variable bounds based on constraint activity
• removes redundant constraints

until no further reductions can be found. A few submissions could even be solved completely with this method.

Instance features for the selection process have been collected after trivial presolving, and structure information including decomposition is available both for the original, unpresolved instance and its trivially presolved counterpart.

# Constraint Classes

In order to give an insight into the composition of a particular instance, MIPLIB distinguishes between the following 17 special classes of linear constraints. It should be noted that in rare cases, a single matrix row with different left and right hand sides can be part of two different classes at the same time. It is then counted twice. The table represents an inclusion hierarchy from more specific to more general. For example, every Set Packing constraint is also a Knapsack constraint. Only the first, most specific applicable type is counted.

Note: While checking whether a constraint fits into a class, we allow for negation of binary variables, i.e., a binary variable $$x$$ may be replaced by $$1 - \bar{x}$$. In particular, this is performed for classes that require positive coefficients for a match. The constraint $$x_1 + x_2 - x_3 - x_4 = 0$$ will be transformed to $$x_1 + x_2 + \bar{x}_3 + \bar{x}_4 = 2$$ and classified as a cardinality constraint.

Type Linear constraints ...
Empty ... with no variables
Free ... with no finite side
Singleton ... with a single variable
Aggregation ... of the type $$ax + by = c$$
Precedence ... of the type $$a x - a y \leq b$$ where $$x$$ and $$y$$ must have the same type
Variable Bound ... of the form $$ax + by \leq c, \, x \in \{0,1\}$$
Set Partitioning ... of the form $$\sum x_i = 1,\, x_i \in \{0,1\}\,\forall i$$
Set Packing ... of the form $$\sum x_i \leq 1,\, x_i \in \{0,1\}\, \forall i$$
Set Covering ... of the form $$\sum x_i \geq 1,\, x_i \in \{0,1\}\, \forall i$$
Cardinality ... of the form $$\sum x_i = k, \, x_i \in \{0,1\} \, \forall i, \, k\geq 2$$
Invariant Knapsack ... of the form $$\sum x_i \leq b, \, x_i \in \{0,1\} \forall i, \, b\in \mathbb{N} \geq 2$$
Equation Knapsack ... of the form $$\sum a_i x_i = b,\, x_i \in \{0,1\}\, \forall i, \, b\in \mathbb{N} \geq 2$$
Binpacking ... of the form $$\sum a_i x_i + a x \leq a,\, x, x_i \in \{0,1\}\, \forall i, \, a\in \mathbb{N} \geq 2$$
Knapsack ... of the form $$\sum a_k x_k \leq b,\, x_i \in \{0,1\}\, \forall i, \, b\in \mathbb{N} \geq 2$$
Integer Knapsack ... of the form $$\sum a_k x_k \leq b,\, x_i \in \mathbb{Z}\, \forall i, \, b\in \mathbb{N}$$
Mixed Binary ... of the form $$\sum a_k x_k + \sum p_j s_j \,\{\leq,=\}\, b,\, x_i \in \{0,1\}\, \forall i, s_j \text{ cont. } \forall j$$
General Linear ... with no special structure

# Instance Structure

The numbers in the table refer to the best (according to the maxwhite score, see below) decomposition that is found by GCG for minimal detection settings (only constraint classification). A decomposition can be seen as a partition of the constraints in $$nb+1$$ (nb = "decomp_ncomponents") many subsets (first subset is called border, last $$nb$$ subsets are called blocks or components) such that each variable must not have a nonzero entry in two constraints that are part of different blocks. Thus, each variable is assigned to the corresponding block or part of no block (then all its non-zero entries are in constraints of the border). Besides the features for minimum, maximum, median, and mean of the numbers of constraints/variables in the components, the so-called maxwhite score (mw) is the following: $$mw = 1 - (s+t)/(nvars*nconss)$$ with $$t = nvars * nconss_1$$, $$s = \sum_{i=2}^{nb+1} s_i$$ where $$s_i = nvars_i * nconss_i$$. Note that $$mw$$ might be greater 0 even if "decomp_ncomponents" == 1, since there might be variables without non-zero entries in constraints of the (single) block.

Last Update Aug 03, 2023 by Jan Krüger
generated with R Markdown