Understanding convexifing a variable based on Dantzig-Wolfe reformulation

[abb-omidi]

Dear support team,

I have some issues distinguishing how to select the variables and also convexifing those in the context of D-W reformulation. Let me explain more:

In a one-dimensional cutting stock problem, the variable $x{i,k}$, in the Kantrovich model, is declared of the number of items final of width $w{i}$ is cut in roll $k$. For that, we need to introduce the variable $\lambda{k}^p$, where the set $p$ defines the extreme points of the original solution space. Now, by substituting the variable $x{i,k}$ by whose reformulated parameter, $a_{i,k}^p$, to capture the added columns coefficients, we can rewrite the demand constraint as, ($\sum_k \sump a{i,k}^p \lambda_{k}^p \geq r_i \ , \forall i$).

A trick that was used here is to transform the variable $y{k}$ based on the variable $\lambda{k}^p$. As far as I know, when the width of master rolls, $W$, are the same we can aggregate ($\sum{p} \sum{k} \lambda{k}^p = \sum{p} \lambda{}^p$). Also, as long as we minimize the original and already the master problems we can ommit the convexity constraint. Now, my questions are_:

• Why do we select the variable $x{i,k}$ and why not go ahead with the variable $y{k}$?

• How actually may the variable $y{k}$ be interpreted by the variable $\lambda{k}^p$? ($y{k}$ is a binary while $\lambda{k}^p$ is a general integer. Also, $\lambda_{k}^p$ is used to select the number of a specific feasible pattern that came from the sub-problem. I am a bit confused to understand the idea!).

• In defining the convexifing variable $\lambda{k}^p$ , why do we select index $k$ instead of index $i$? Is it correct to select an index we ask to decompose the problem based on it? (e.g. if we have a variable $s{i,j,k}$ in the constraint of the form ($\sum{j,k} s{i,j,k} \leq c{i}, \ \forall i$), and would like to decompose the problem w.r.t the index $i$, should we declare the convexifing variable as $a{i,j,k}^p \lambda{i}^p$ and rewrite the constraint as $\sum{p} \sum{j,k} a{i,j,k}^p \lambda{i}^p \leq c{i}, \ \forall i$?)

• Can the mentioned trick for aggregating the variable be applied in all the cases as long as we have the same resources like identical machines, stations, vehicles, etc.?

• How can GCG perform to select the variables for transforming it in whose convexifing form?

• Is it possible to write the master and sub-problems, in an LP format, in a specific iteration of the column generation algorithm by GCG?

I am looking forward to hearing from you All the best Abbas

[abb-omidi]

Dear support team,

May I have your insight regarding the above questions? If it needs more information please, let me know to provide that.

Best regards

[jurgen-lentz]

Not a pygcgopt issue! Please use forums or other resources for that.

[abb-omidi]

@jurgen-lentz,

What about my last two questions? (I think they would be related to the GCG)

Thanks