Scippy

GCG

Branch-and-Price & Column Generation for Everyone

Type Classifier (SCIP Variable Type)

This classifier adds variables to classes according to their domain given by SCIP. There are four different variable types supported:

  • Binary (bin)
  • Integer (int)
  • Implicit Integer (impl)
  • Continuous (cont)

Classification

Dantzig-Wolfe Decomposition

The handling for Dantzig-Wolfe decomposition mode is as follows:

  • A new class is generated for each of the aforementioned types.
  • By default, the class with name newVartype is generated

Benders' Decomposition

The handling for Benders' decomposition is as follows:

  • If detection/benders/onlycontsubpr is set:
    • Integer variables will be added to the linking variables
    • Continuous variables will be added to the block variables
  • If detection/benders/onlybinmaster is set:
    • Binary variables will be added to the linking variables
    • Integer Variables, Implicit Integer Variables and Continuous Variables will be added to the block variables

Example

Different domains of variables usually hint to a different purpose of those. Thus, we find an example for a problem that one usually models using different variable types.
We look at a "text-book" mixed-integer program for the Lot-Sizing problem.

Given: single product, \(T\) periods, holding cost \(l\) per unit, setup cost \(r\) per lot, demand \(b_t\) in period \(t\)
Problem: how much to produce in each period in order to satisfy demands at minimum setup and holding cost
Variables: \(x_t\) how much to store in time \(t\), \(y_t\) how much to produce in time \(t\), \(z_t\) produce in \(t\)

\begin{align} & \text{min} & & \sum_{t=0}^T(l y_t+r z_t) \\ & \text{s.t.} & & y_{t-1}+x_t = b_t+y_t && t=0,\cdots,T-1 \\ & & & x_t\leq z_t\cdot M && t=0,\cdots,T \\ & & & \mathbf{x_t, y_t \in \mathbb{Z}_{+}} && t=0,\cdots,T \\ & & & \mathbf{z_t\in\{0,1\}} && t=0,\cdots,T \end{align}

We see that there are two different types of variables, which is detected by GCG:

Varclassifier "vartypes" yields a classification with 2 different variable classes