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

Question

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;

Answer 1

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;