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?

Improve this question
$\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
    Commented 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 ♦
    Commented Jan 28 at 16:18
  • $\begingroup$ @RobPratt. What do you mean by the latter part? Where is $\lambda_{ir}$ missing? $\endgroup$
    – nflgreaternba
    Commented 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
    Commented 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$
    – nflgreaternba
    Commented Jan 28 at 17:42

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
7
  • $\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$
    – nflgreaternba
    Commented 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
    Commented Jan 28 at 23:22
  • $\begingroup$ I just did that! $\endgroup$
    – nflgreaternba
    Commented Jan 29 at 8:49
  • $\begingroup$ Dear @RobPratt, would you please, 1) why we should choose only the first part of the first constraint to convexfy? (I mean, it seems the only part that was convexified is $\sum_i \sum_r x_{its}^r \lambda_{ir}$), and is there any specific reason for disincorporating $slack_{ts}$? 2) Is the variable $x_{its}^r$, in the master problem, the relaxed form? (e.g. $0 \leq x_{its}^r \leq 1$) 3) Would you elaborate more on how we can deal with index $i$ in the sub-problem? $\endgroup$
    – A.Omidi
    Commented May 20 at 10:57
  • $\begingroup$ @A.Omidi 1) That choice of convexification was requested by the OP, and it enables decomposition of the subproblem by $i$. 2) In the master problem, $x_{its}^r$ is a constant obtained by solving the subproblem, and it is binary-valued. 3) The subproblem decomposes by $i$, so you can solve for each $i$ separately. The constraints are identical, and only the objective depends on $i$, through the constant offset $\mu_i$. $\endgroup$
    – RobPratt
    Commented May 20 at 14:15

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.