# Help with formulating the objective function of my subproblem

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?

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

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.
• 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? May 20 at 10:57
• @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$. May 20 at 14:15