How can I add columns from the subproblem to the master problem in my column generation model?

Question

I have one last question about my column generation model. I am currently trying to implement it in code, and I am successfully solving the subproblem. So I can solve the dual values of the master problem, then pass them to the individual SP and these then minimize the SP target functions. Unfortunately, I fail when adding the columns to my master problem, which is probably also due to the fact that I don't quite understand what exactly should be passed from the individual subproblems to the master problem and how the assignment to the $\lambda$ variable is done. And what exactly is a roster in this context? Do I simply have to pass the optimal values of $motivation$ from the super problem to the master problem? When I try this in Gurobi for example, there is an error that the array length does not match. For $I=3$, $S=3$ and $T=7$ I have $21$ values of $motivation$ for each doctor, but there are $24$ constraints in the MP (21 for the Demand Constraint and 3 of the Integrality constraint). So what exactly do I add from the SPs to the MP? This is the model:

Master Problem: $$ \begin{align} &(MP)\quad \min &\sum_t \sum_s \text{slack}_{ts} \\ \end{align}$$ subject to: \begin{align} &&\sum_i \sum_r \text{motivation}_{its}^r \lambda_{ir} + \text{slack}_{ts} & \ge \text{demand}_{ts} &&\forall t,s &&\label{eins}\\ &&\sum_r \lambda_{ir} &= 1 &&\forall i &&\\ &&\lambda_{ir} &\in\mathbb{Z}^+ &&\forall i,r\\ &&\text{slack}_{ts} &\ge 0 &&\forall t,s \end{align}

Subproblems (i)

$$\begin{align} &SP(i)\quad \min -\sum_{t,s} \pi_{ts} \text{motivation}_{ts} - \mu_i\\ \end{align}$$ subject to: $$\begin{align} &mood_{it} + M\cdot (1-x_{its}) \geq motivation_{its}&\forall i,t,s \\ &motivation_{its} \geq mood_{it} - M\cdot (1-x_{its}) &\forall i,t,s \\ &motivation_{its} \le x_{its} & \forall t,s \\ &\sum_{s}^{}x_{its}\le 1& \forall i,t \\ &\alpha \sum_s x_{its} + \text{mood}_{it} = 1 &\forall i,t\\ &motivation_{its} \in[0,1] &\forall t,s \\ &mood_{it} \in[0,1] &\forall t \\ &x_{its}\in \{0,1\} &\forall t,s\\ \end{align}$$

Gere is my Gurobi implementation, in case anyone here is familiar with it: GitHub

Answer 1

The values of the variables in your subproblem solution become the constraint coefficients in the new column in your master problem. Lets say that, prior to solving the subproblem, your master columns are numbered $r=1,\dots, R.$ Your new subproblem solution will be used to create master problem column $R+1.$ The coefficient $$\text{motivation}_{its}^{R+1}$$ in the master problem will be the value of $$motivation_{its}$$ in the subproblem solution. For each $i,$ in the master problem row $\sum_r \lambda_{i,r} = 1$ the coefficient in the new column will be 1.