0
$\begingroup$

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

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thank you for your anwser Mr. Rubin. If I understand it correctly, then the master problem consists of $T\times S$ demand constraints and $I$ integrailty constraints, right? and for each of the $i$ nurses there are also $T\times S$ values of $motivation$ which are then summed up there. Then I pass the respective (individual) $motivation$ values to all demand constraints and when a new roster comes for doctor 1, the previous lambdas are set to 0 and the new one to 1, right? So this is dynamic programming right? And why is the constraint then $\lambda\ge0$ and not $\in\{0,1\}$, if 1 is assigned? $\endgroup$ Feb 19 at 14:40
  • $\begingroup$ First, your "sum of lambda = 1" constraints are not "integrality" constraints. The integrality constraints are the ones that say lambdas must be integers. You have $T\times S$ demand constraints and $I$ constraints saying that each $i$ (doctor?) gets assigned to a single column (schedule?). I don't know what you mean by "previous lambdas". You retain every column previously generated and add one new column, then let the solver decide whether the new column is used (and by which doctor or doctors). No, this is not dynamic programming. $\endgroup$
    – prubin
    Feb 19 at 16:19
  • 1
    $\begingroup$ As for $\lambda \ge 0,$ this probably relates to an answer to a previous question. To get dual values for the master, you solve a relaxed master, the relaxation being that you drop integrality constraints (allowing fractional assignments). $\endgroup$
    – prubin
    Feb 19 at 16:20
  • $\begingroup$ Thank you for your answer. I have understood the fractional allocation, but in this context I do not fully understand the last sentence of your answer. You mention there that the coefficient in the new column must be 1. How should I understand this? $\endgroup$ Feb 26 at 10:09
  • 1
    $\begingroup$ The constraint $\sum_r \lambda_{i,r} = 1$ is, more explicitly, $\sum_{r=1}^R \lambda_{i,r}=1.$ When you add the new column, the upper limit of summation becomes $R+1$ and the coefficient of $\lambda_{i,R+1}$ is, as with every other term in the summation, 1. $\endgroup$
    – prubin
    Feb 26 at 16:24

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.