1
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ 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$. $\endgroup$
    – RobPratt
    Jan 28 at 15:51
  • $\begingroup$ @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.$ $\endgroup$
    – prubin
    Jan 28 at 16:18
  • $\begingroup$ @RobPratt. What do you mean by the latter part? Where is $\lambda_{ir}$ missing? $\endgroup$ Jan 28 at 17:20
  • $\begingroup$ 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 or.stackexchange.com/questions/608/… $\endgroup$
    – RobPratt
    Jan 28 at 17:35
  • $\begingroup$ 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? $\endgroup$ Jan 28 at 17:42

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ Jan 28 at 23:00
  • $\begingroup$ Glad to help. Please mark my answer as accepted, remove your edit, and start a new post for your new question. $\endgroup$
    – RobPratt
    Jan 28 at 23:22
  • $\begingroup$ I just did that! $\endgroup$ Jan 29 at 8:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.