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

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.

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 |

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 Dec 06, 2022 by Jan Krüger

generated with R Markdown

© 2022 by Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)

Imprint