1

i have a pretty basic question regarding column generation. I have the following scheduling problem i would like to solve with column generation: \begin{align} &\min\sum_{t}^{}\sum_{s}^{}slack_{ts}\\ &\sum_{i}^{}x_{its}=Demand_{ts}+slack_{ts}\forall t,s\\ &\sum_{s}^{}x_{its}\le 1\forall i,t\\ &x_{its}\in\left\{ 0,1 \right\}\\ &Demand_{ts},slack_{ts}\ge 0 \forall t,s\\ \end{align}

I would decompose the problem in the following master and subproblem: \begin{align} &MP: \min\sum_{t}^{}\sum_{s}^{}slack_{ts}\\ &\sum_{i}^{}\sum_{r}^{}\lambda_{ir}x^{r}_{its}=Demand_{ts}+slack_{ts}\forall t,s\\ &\sum_{r}^{}\lambda_{ir}=1 \forall i\\ &\lambda_{ir}\in\left\{ 0,1 \right\}\\ \\ &SP: \min 1-\sum_{t}^{}\sum_{s}^{}\pi_{ts}x_{its}-\mu_i\\ &\sum_{s}^{}x_{its}\le 1\forall i,t\\ &x_{its}\in\left\{ 0,1 \right\}\\ \end{align}

My question now is whether I have formulated the subproblem (especially the objective function) correctly? I often read that the reduced costs are calculated with $c-yA$ ($y$=duals and $A$ = constraint matrix), but i dont have any cost vector. Is a $1$ appropriate then?

RobPratt
  • 32,006
  • 1
  • 44
  • 84
nflgreaternba
  • 99
  • 1
  • 8
  • In your original problem, it appears that $\text{Demand}{ts}$ is a variable, but is it instead a given input parameter? Also, should the $+\text{slack}{ts}$ instead be $-\text{slack}{ts}$? Also, $\pi{ds}$ should instead be $\pi_{ts}$. Because $\lambda$ does not appear in the objective, $c=0$. – RobPratt Jan 28 '24 at 15:51
  • @RobPratt I would assume demand is a parameter. If it's a variable, the answer is to set everything to zero (barring additional constraints not stated in the question). Concur on $d\rightarrow t.$ – prubin Jan 28 '24 at 16:18
  • @RobPratt. What do you mean by the latter part? Where is $\lambda_{ir}$ missing? – nflgreaternba Jan 28 '24 at 17:20
  • Because $x$ does not appear in the original objective, $\lambda$ does not appear in the master objective, and so $c=0$ in the reduced cost calculation. Also, you should omit the (redundant) upper bound on $\lambda$. See https://or.stackexchange.com/questions/608/variable-bounds-in-column-generation – RobPratt Jan 28 '24 at 17:35
  • I see, so the updated SP is correct? How would i need to modify my problem to be able to include $\lamba$ in the objective function? I need to introduce costs $c$ right? – nflgreaternba Jan 28 '24 at 17:42

1 Answers1

2

Your original problem is: \begin{align} &\text{minimize} &\sum_t \sum_s \text{slack}_{ts} \\ &\text{subject to} &\sum_i x_{its} + \text{slack}_{ts} & = \text{Demand}_{ts} &&\forall t,s\\ &&\sum_s x_{its} &\le 1 &&\forall i,t\\ &&x_{its} &\in\left\{ 0,1 \right\} &&\forall i,t,s\\ &&\text{slack}_{ts} &\ge 0 &&\forall t,s \end{align}

For the Dantzig-Wolfe reformulation, introduce $\lambda_{ir} \ge 0$ and substitute $x_{its} = \sum_r x_{its}^r \lambda_{ir}$ in the (objective and) complicating constraints to obtain the master problem: \begin{align} &\text{minimize} &\sum_t \sum_s \text{slack}_{ts} \\ &\text{subject to} &\sum_i \sum_r x_{its}^r \lambda_{ir} + \text{slack}_{ts} & = \text{Demand}_{ts} &&\forall t,s &&\text(\text{$\pi_{ts}$ free})\\ &&\sum_r \lambda_{ir} &= 1 &&\forall i &&\text(\text{$\mu_i$ free})\\ &&\lambda_{ir} &\in\mathbb{Z}^+ &&\forall i,r\\ &&\text{slack}_{ts} &\ge 0 &&\forall t,s \end{align} The reduced cost of $\lambda_{ir}$ is $0-\sum_{t,s} \pi_{ts} x_{its}^r - \mu_i$, so the subproblem for block $i$ is: \begin{align} &\text{minimize} &0-\sum_{t,s} \pi_{ts} x_{its} - \mu_i \\ &\text{subject to} &\sum_s x_{its} &\le 1 &&\forall t\\ &&x_{its} &\in\left\{ 0,1 \right\} &&\forall t,s \end{align}

When you solve the LP relaxation of the restricted master problem, be sure to impose $\lambda_{ir} \ge 0$ (instead of $\lambda_{ir} \in [0,1]$), as discussed in Variable bounds in column generation.

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • Thank you. One more question. Suppose I have a new demand constraint and other new constraints (see EDIT). I now want to add the motivation and include it in the demand constraint. The determination of the motivation is introduced below. Can I still only include the demand constraint in the MP and move the other new ones to the SP or is that not possible because they are "linked"? Especially about the initialization of the GC, where the SP has not yet been solved. How do I have to adapt my CG model so that I still only have the demand constraint in the MP and the rest in the SP? – nflgreaternba Jan 28 '24 at 23:00
  • Glad to help. Please mark my answer as accepted, remove your edit, and start a new post for your new question. – RobPratt Jan 28 '24 at 23:22
  • I just did that! – nflgreaternba Jan 29 '24 at 08:49