Comparing between Kantorovich and Gilmore-Gomory formulations to solve Cutting stock problem by column generation

Question

The well-known approach to solving the cutting stock problem is the Gilmore-Gomory (GG) formulation in a column generation procedure. The master and subproblems of GG formulation are: (for simplicity I dropped the indices and parameters definition)

\begin{align*} \text{Min}_{(MP)} \quad & \sum_{p \in P} x_p \\ \text{subject to} \quad & \sum_{p \in P} a_{i,p} x_p \geq r_i \ , \forall i \in I\\ & x_p \geq 0. \end{align*}

$$-----------------$$

\begin{align*} \text{Min}_{(SP)} \quad & 1- \sum_{i \in I} \pi_i y_i \\ \text{subject to} \quad & \sum_{i \in I} w_i y_i \leq W\\ & y_i \in \mathbb{Z}^+. \end{align*}

Indeed, Kantorovich also proposed a MIP formulation to solve the CSP.

\begin{align*} \text{Min} \quad & \sum_k y_k \\ \text{subject to} \quad & \sum_k x_{i,k} \geq r_i \ , \forall i \\ \quad & \sum_i w_i x_{i,k} \leq W y_k \ , \forall k \\ & y_k \in \{0,1\}, x_{i,k} \in \mathbb{Z}^+. \end{align*}

As far as I know, the GG formulation came from the Kantorovich formulation in the Dantzig-Wolfe reformulation context. The DW reformulation of the Kantorovich model is as follows:

\begin{align*} \text{Min}_{(MP)} \quad & \sum_k \sum_p \lambda_{k}^p \\ \text{subject to} \quad & \sum_k \sum_p a_{i,k}^p \lambda_{k}^p \geq r_i \ , \forall i \\ \quad & \sum_p \lambda_{k}^p \leq 1 \ , \forall k \\ & \lambda_{k}^p \geq 0. \end{align*}

Now, my questions are:

• How can the GG model be derived from the Kantorovich model?
• How the variables $y_k$ can be interpreted as $\lambda_{k}^p$?
• Based on the Kantorovich model, what would the subproblem objective function be?

Answer 1

The trick is that since the big rolls are identical, you can aggregate the $\lambda$ variables: $$ \sum_k \lambda_k^p = \lambda^p = x_p $$

Also, since you are minimizing the number of big rolls, you can ommit the convexity constraints, which yields the CG model.

The interpretation of the $y_k$ variables is: $y_k$ takes value $1$ if and only if roll $k$ is selected. The difference with $\lambda_p$ is that although $p$ also represents a roll, its structure is already entirely defined (via $a_i^p$). On the contrary, roll $k$ is not defined; it is defined via constraints $\sum_i w_i x_{i,k} \le W y_k$.