0
$\begingroup$

As suggested by @RobPratt, here is the new opened question. I have these decomposed master and subproblems:

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

One approach would be to add a new single problem that includes all $i$ and impose the new constraint there. How would that look like?

$\endgroup$

1 Answer 1

0
$\begingroup$

Your original compact 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\\ &&\sum_i x_{its} &\ge 1 &&\forall t,s\\ &&\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_r \ge 0$ and substitute $\text{motivation}_{its} = \sum_r \text{motivation}_{its}^r \lambda_r$ 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_r + \text{slack}_{ts} & = \text{demand}_{ts} &&\forall t,s &&\text(\text{$\pi_{ts}$ free})\\ &&\sum_r \lambda_r &= 1 &&&&\text{($\mu$ free)}\\ &&\lambda_r &\in\mathbb{Z}^+ &&\forall r\\ &&\text{slack}_{ts} &\ge 0 &&\forall t,s \end{align} The reduced cost of $\lambda_r$ is $0-\sum_{i,t,s} \pi_{ts} \text{motivation}_{its}^r - \mu$, so the subproblem is: \begin{align} &\text{minimize} &0-\sum_{i,t,s} \pi_{ts} \text{motivation}_{its} - \mu \\ &\text{subject to} &-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\\ &&\sum_i x_{its} &\ge 1 &&\forall t,s\\ &&\text{motivation}_{its} &\in[0,1] &&\forall i,t,s \\ &&\text{mood}_{it} &\in[0,1] &&\forall i,t \\ &&x_{its}&\in \{0,1\} &&\forall i,t,s\\ \end{align}

$\endgroup$
4
  • $\begingroup$ Isn't there a separate subproblem for each $i$? If so, how can you sum over $i$ in a subproblem? $\endgroup$
    – prubin
    Commented May 28 at 18:13
  • $\begingroup$ @prubin Yes, decomposing by $i$ is the more natural approach. But in another comment the OP asked for details about instead putting the new constraints in a single subproblem that includes all $i$: or.stackexchange.com/questions/11608/… $\endgroup$
    – RobPratt
    Commented May 28 at 18:30
  • $\begingroup$ So is your answer above replacing the various subproblems by a single one? This version of the question still mentions "subproblems($i$)". $\endgroup$
    – prubin
    Commented May 28 at 18:33
  • 1
    $\begingroup$ Yes, after imposing the new constraints, the subproblems are no longer independent and instead form a single block. $\endgroup$
    – RobPratt
    Commented May 28 at 18:35

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.