# How to modify master problem and individual sub problems in column generation?

This is a follow-up post regarding this one. I deleted this new post once before, as I was unhappy with the formulation. I have the following basic nurse scheduling MILP, which tries to cover the daily demand $$demand_{ts}$$.

$$\min \sum_t \sum_s slack_{ts}$$ $$\text{subject to} \sum_i x_{its} + slack_{ts} = 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$$ $$slack_{ts} \ge 0 \forall t,s$$

After decomposing according to the Dantzig Decomposition, this yields the following Master problem $$(MP)$$:

$$\text{minimize} \sum_t \sum_s \text{s}_{ts}$$ $$\text{subject to} \sum_i \sum_r x_{its}^r \lambda_{ir} + \text{s}_{ts} = d_{ts} \forall t,s$$ $$\sum_r \lambda_{ir} = 1 \forall i$$ $$\lambda_{ir} \in\mathbb{Z}^+ \forall i,r$$ $$\text{s}_{ts} \ge 0 \forall t,s$$

and sub problem $$(SP(i))$$:

$$\text{minimize } -\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$$

So far so good. Now, I want to incorporate individual motivation ($$motivation_{its}$$), which can be seen as the performance during each shift ($$motivation_{its}$$ is influenced by the daily mood $$mood_{it}$$. If it is smaller than one, there is more $$slack_{ts}$$. This motivation should now be included in the demand constraint (instead of $$x_{its}$$). The new (full) problem looks like this:

$$\text{minimize} \sum_t \sum_s slack_{ts}$$ $$\sum_{i}^{}motivation_{its}+slack_{ts}=demand_{ts}\forall t,s$$ $$mood_{it} + M\cdot (1-x_{its}) \geq motivation_{its} \geq mood_{it} - M\cdot (1-x_{its})\quad \forall i,t,s$$ $$motivation_{its} \leq x_{its}\quad \forall i,t,s$$ $$mood_{it}=1-\alpha_{it}\cdot \sum_s x_{its}\quad \forall i,t\\ \alpha_{it}\sim U(0,1)\quad \forall i,t$$ $$x_{its}\in \{0,1\}$$ $$mood_{it}, motivation_{its}\in[0,1]$$

Now I have the following question. Can I still only include the demand constraint in the MP and move the other new ones to the SP(i) or is that not possible because they are "linked"? Especially about the initialization of the GC, where the SP(i) has not yet been solved and no solutions for $$mood_{it}$$ and therefore also no $$motivation_{its}$$ values are obtained. 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(i)?

SAS Code:

proc optmodel;
/* declare sets and parameters */
set ISET, TSET, SSET;
num demand {TSET, SSET};

/* read input data here */
set ISET = {1, 2, 3};
set SSET = {1, 2, 3};
set TSET = {1, 2, 3, 4, 5, 6, 7};
num demand{TSET, SSET} = {(1, 1): 2, (1, 2): 1, (1, 3): 0, (2, 1): 1, (2, 2): 2, (2, 3): 0, (3, 1): 1, (3, 2): 1, (3, 3): 1,
(4, 1): 1, (4, 2): 2, (4, 3): 0, (5, 1): 2, (5, 2): 0, (5, 3): 1, (6, 1): 1, (6, 2): 1, (6, 3): 1,
(7, 1): 0, (7, 2): 3, (7, 3): 0};
/* Generate random values for alpha */
execute INIT_RANDOM(123); /* Set a seed for reproducibility */
alpha{i in ISET, t in TSET} = rand("Uniform", 0, 1);

/* declare decision variables */
var motivation {ISET, TSET, SSET} >= 0 <= 1;
var slack {TSET, SSET} >= 0;
var mood {ISET, TSET} >= 0 <= 1;
var x {ISET, TSET, SSET} binary;

/* declare objective */
minimize z = sum {t in TSET, s in SSET} slack[t,s];

/* declare constraints */
con SatisfyDemand {t in TSET, s in SSET}:
sum {i in ISET} motivation[i,t,s] + slack[t,s] = demand[t,s];

con Indicator {i in ISET, t in TSET, s in SSET}:
x[i,t,s] = 1 implies motivation[i,t,s] = mood[i,t]
suffixes=(block=i);

con MotivationImpliesX {i in ISET, t in TSET, s in SSET}:
motivation[i,t,s] <= x[i,t,s]
suffixes=(block=i);

con AlphaMood {i in ISET, t in TSET}:
alpha * sum {s in SSET} x[i,t,s] + mood[i,t] = 1
suffixes=(block=i);

/* call MILP solver with Dantzig-Wolfe decomposition algorithm */
solve with milp / decomp;

/* write output data here */
quit;

• Please clarify whether $\text{mood}_{it}$ is an input parameter or a decision variable. Does $U(0,1)$ mean a standard uniform random variable? Commented Feb 2 at 20:53
• I just updated my post, as I forget to add something. Yes, $U(0,1)$ is standard uniform random variable Commented Feb 2 at 21:07
• Thank you for the update, but I still don't understand whether mood is an input parameter or a decision variable. And is motivation a nonnegative decision variable? And is $x$ still a binary decision variable? The full problem needs to be completely specified before attempting column generation. Commented Feb 2 at 21:16
• $x$ is still binary and $mood$ is a decision variable Commented Feb 2 at 21:53

Your problem is: \begin{align} &\text{minimize} &\sum_t \sum_s \text{slack}_{ts} \\ &\text{subject to} &\sum_i \text{motivation}_{its} + \text{slack}_{ts} &= \text{demand}_{ts} &&\forall t,s \\ &&-M(1-x_{its}) \le \text{motivation}_{its} - \text{mood}_{it} &\le M(1-x_{its}) &&\forall i,t,s \\ &&\text{motivation}_{its} &\le x_{its} && \forall i,t,s \\ &&\alpha_{it} \sum_s x_{its} + \text{mood}_{it} &= 1 &&\forall i,t\\ &&\text{motivation}_{its} &\in[0,1] &&\forall i,t,s \\ &&\text{slack}_{ts} &\ge 0 &&\forall t,s \\ &&\text{mood}_{it} &\in[0,1] &&\forall i,t \\ &&x_{its}&\in \{0,1\} &&\forall i,t,s\\ \end{align}

For the Dantzig-Wolfe reformulation, introduce $$\lambda_{ir} \ge 0$$ and substitute $$\text{motivation}_{its} = \sum_r \text{motivation}_{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 \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} The reduced cost of $$\lambda_{ir}$$ is $$0-\sum_{t,s} \pi_{ts} \text{motivation}_{its}^r - \mu_i$$, so the subproblem for block $$i$$ is: \begin{align} &\text{minimize} &0-\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}

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.

You can initialize with trivial columns (one per block $$i$$) that correspond to $$\text{motivation}_{its}=x_{its}=0$$ and $$\text{mood}_{it}=1$$. The first master solve will thus yield $$\text{slack}_{ts}=\text{demand}_{ts}$$ and $$\lambda_{ir}=1$$.

By request, here is SAS code that uses automated Dantzig-Wolfe decomposition:

proc optmodel;
/* declare sets and parameters */
set ISET, TSET, SSET;
num alpha {ISET, TSET};
num demand {TSET, SSET};

/* read input data here */

/* declare decision variables */
var motivation {ISET, TSET, SSET} >= 0 <= 1;
var slack {TSET, SSET} >= 0;
var mood {ISET, TSET} >= 0 <= 1;
var x {ISET, TSET, SSET} binary;

/* declare objective */
minimize z = sum {t in TSET, s in SSET} slack[t,s];

/* declare constraints */
con SatisfyDemand {t in TSET, s in SSET}:
sum {i in ISET} motivation[i,t,s] + slack[t,s] = demand[t,s];

con Indicator {i in ISET, t in TSET, s in SSET}:
x[i,t,s] = 1 implies motivation[i,t,s] = mood[i,t]
suffixes=(block=i);

con MotivationImpliesX {i in ISET, t in TSET, s in SSET}:
motivation[i,t,s] <= x[i,t,s]
suffixes=(block=i);

con AlphaMood {i in ISET, t in TSET}:
alpha[i,t] * sum {s in SSET} x[i,t,s] + mood[i,t] = 1
suffixes=(block=i);

/* call MILP solver with Dantzig-Wolfe decomposition algorithm */
solve with milp / decomp;

/* write output data here */
quit;

• Thank you so much. One last question. What do you mean with $\mu,\pi$-free? Commented Feb 4 at 10:12
• Like in the previous post, those are dual variables associated with equality constraints, so they are free/unbounded/unrestricted in sign. Commented Feb 4 at 14:49
• Thanks. As there are $\mid I\mid$ subproblems and they are individual, can I drop the $i$ in every constraint? Commented Feb 5 at 16:17
• Yes, for subproblem $i$ I have dropped the $i$ in the constraint index. You can also drop the $i$ from the subproblem variable indices if you want. But you must keep the $i$ in the parameters $\mu_i$ and $\alpha_{it}$. Commented Feb 5 at 17:11
• And why is that. Why can I drop $i$ everywhere apart from $\alpha_{it}$ and $\mu_i$. Would that mean, that when i implement the problem in a commercial solver, i create a subproblem for every $i\in I$ using a for loop. Would that mean that my SP objective after the for loop would be $\min -\sum_{t,s}\pi_{ts}motivation^r_{ts}-\mu_i$ (the i would still be there?). Commented Feb 5 at 17:58