Modification of subproblem objective function

Question

I have the following decomposed compact model with the following 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 &&\\ &&\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} and subproblems($i$): \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}

Now i want to additionally impose the constraint: $$\sum_i x_{its} \geq 1 \quad \forall t, s$$ My idea would be to add this constraint to the masterproblem, which yields the following constraint: $$\sum_i \sum_r \lambda_r x_{its}^r \geq 1 \quad \forall t, s$$ How would i need to modify my subproblem objective function to additionally cope for this?

Answer 1

If $\gamma_{ts}$ is the dual variable associated with the new constraint, then the objective function of the subproblem $i$ becomes: $$ \text{minimize} \quad -\sum_{t,s} \pi_{ts} \text{motivation}_{its} - \mu_i - \sum_{t,s} \gamma_{ts} x_{its} $$

Answer 2

Your original 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 \\ &&\sum_i x_{its} &\ge 1 &&\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}$ and $x_{its} = \sum_r x_{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_i \sum_r x_{its}^r \lambda_{ir} &\ge 1 &&\forall t,s &&\text(\text{$\gamma_{ts} \ge 0$})\\ &&\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 + \gamma_{ts} x_{its}^r) - \mu_i$, so the subproblem for block $i$ is: \begin{align} &\text{minimize} &0-\sum_{t,s} (\pi_{ts} \text{motivation}_{its} + \gamma_{ts} x_{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}