# Exploiting identical subproblems in column generation

As suggested, this is a new post. I have the following column generation model. The notation is as follows: $$i\in I$$ refers to the nurses, $$t\in T$$ to the days and $$s\in S$$ for the shifts. With the following master problem $$MP$$ and the index $$r\in R$$ which refers to the roster to be worked:

Concerning the variables, $$motivation_{its}$$ is the (continuous) shift specific motivation which, together with the slack $$slack_{ts}$$ must fulfill the $$demand_{ts}$$.

In the subproblem, the shift assignment $$x_{its}$$ and the random (with $$\alpha_{it}$$) daily mood $$mood_{it}$$, are used to determine the shift specific motivation $$motivation_{its}$$. \begin{align} &\text{minimize} &\sum_t \sum_s \text{slack}_{ts} \\ &\text{subject to} &\sum_i \sum_r \text{motivation}_{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} And the individual subproblems $$SP(i)$$: \begin{align} &\text{minimize} &-\sum_{t,s} \pi_{ts} \text{motivation}_{its} - \mu_i \\ &\text{subject to} &-M(1-x_{its}) \le \text{motivation}_{its} - \text{mood}_{it} &\le M(1-x_{its}) &&\forall t,s \\ &&\text{motivation}_{its} &\le x_{its} && \forall t,s \\\ &&\alpha_{it} \sum_s x_{its} + \text{mood}_{it} &= 1 &&\forall t\\ &&\text{motivation}_{its} &\in[0,1] &&\forall t,s \\ &&\text{mood}_{it} &\in[0,1] &&\forall t \\ &&x_{its}&\in \{0,1\} &&\forall t,s\\ \end{align}

This assumes individual nurses, with different regulatory requirements or preferences f.e. However, if this assumption is relaxed, that every nurse is the same, how would this change the model formulation and why should the model be changed? For example, as done by Purnomo and Bard (2007), they translated the decision variable to be an integer, rather than being binary. Is the necessary as $$motivation^r_{its}$$ is continuous

EDIT: The new objective function looks like this. $$-\sum_{t,s}^{}\pi_{ts}motivation_{ts}-\min \mu_i$$

EDIT 2: \begin{align} &\text{minimize} &\sum_t \sum_s \text{slack}_{ts} \\ &\text{subject to} &\sum_r \text{motivation}_{ts}^r \lambda_{r} + \text{slack}_{ts} & = \text{demand}_{ts} &&\forall t,s &&\\ &&\sum_r \lambda_{r} &= \mid I \mid && &&\\ &&\lambda_{r} &\in\mathbb{Z}^+ &&\forall r\\ &&\text{slack}_{ts} &\ge 0 &&\forall t,s \end{align} And the generic subproblems $$SP$$: \begin{align} &\text{minimize} &-\sum_{t,s} \pi_{ts} \text{motivation}_{ts} - \mu \\ &\text{subject to} &-M(1-x_{ts}) \le \text{motivation}_{ts} - \text{mood}_{t} &\le M(1-x_{ts}) &&\forall t,s \\ &&\text{motivation}_{ts} &\le x_{ts} && \forall t,s \\\ &&\alpha_{t} \sum_s x_{ts} + \text{mood}_{t} &= 1 &&\forall t\\ &&\text{motivation}_{ts} &\in[0,1] &&\forall t,s \\ &&\text{mood}_{t} &\in[0,1] &&\forall t \\ &&x_{ts}&\in \{0,1\} &&\forall t,s\\ \end{align}

With individual nurses, you generate columns specific to each nurse, use binary variables to indicate which column is used for each nurse, and constraints on the binary variables saying that exactly (or at most, depending on your problem) one column is selected for each nurse.

With generic nurses, you generate columns usable by any nurse (so likely fewer columns) and replace the binary variables with nonnegative integer variables indicating how many nurses match to each column. The constraint that exactly/at most one column is used for each individual nurse changes to a single constraint saying that the number of times each column is used totals to exactly/at most the number of nurses available.

This is irrespective of whether subproblem variables are binary, general integer or continuous.

• Thanks. And why is it necessary to modify the SP objective function (see edit)? Commented Feb 12 at 1:24
• @nflgreaternba If you use the suggested approach, the (single) subproblem objective function becomes $-\sum_{t,s} \pi_{ts} \text{motivation}_{ts}-\mu$, where $\mu$ is the dual variable for the convexity/cardinality constraint. You can think of the new $\lambda_r$ variable as the aggregation $\sum_i \lambda_{ir}$. Commented Feb 12 at 4:56
• So the new objective function is not $-\sum_{t,s}^{}\pi_{ts}motivations_{ts}-\min\mu_i$ but rather $\min−\sum_{t,s}^{}\pi_{ts}motivation_{ts}-\mu$ (which is the same objective function as in the case of individual subproblems but dropping the index on \mu). Correct? Commented Feb 13 at 10:05
• @prubin How would i need to modify my MP and SP, in mathematical notation, in order to aggregate the columns? Commented Mar 28 at 16:08
• @nflgreaternba Beats me, since you have not indicated what each variable or each subscript represents in your post.
– prubin
Commented Mar 28 at 16:23