0
$\begingroup$

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?

$\endgroup$

2 Answers 2

0
$\begingroup$

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} $$

$\endgroup$
0
$\begingroup$

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}

$\endgroup$
4
  • $\begingroup$ Note that the symbol $\alpha$ is already used in OP's subproblem $\endgroup$
    – Kuifje
    May 11 at 16:53
  • $\begingroup$ @Kuifje Yes, corrected. $\endgroup$
    – RobPratt
    May 11 at 16:55
  • $\begingroup$ @RobPratt Thanks. Assuming now instead of $\sum_i x_{its}\geq 1~ \forall t, s$, i now want to enforce $\sum_i motivation_{its}\geq 0.5\cdot demand_{ts} \quad \forall t, s$. Do i again need to modify it to $\sum_i \sum_r \lambda_r motivation_{its}^r \geq 0.5\cdot Demand_{ts} \quad \forall t, s$ and add the new duals $\gamma$ or is it sufficient to just add the constraint without $\lambda$? $\endgroup$ 2 hours ago
  • $\begingroup$ Yes, you need to do the substitution in terms of $\lambda$, just like in the first equality constraint. $\endgroup$
    – RobPratt
    2 hours ago

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.