1
$\begingroup$

Suppose there is a specific constraint as follows to impose the precedence relation between the tasks:

$$ \sum_{m \in M} m.x_{j,m} \leq \sum_{m \in M} m.x_{k,m} \quad \forall (j,k) \in T $$

I want to decompose this specific constraint based on each $m \in M$ and would like to know how can I bring this out in the sub-problem? I have tried the following, but I am unsure if it really imposes what the relation would be.

$$ x_{j} \leq x_{k} \quad \forall (i,j) \in T $$

Improve this question
$\endgroup$
15
  • $\begingroup$ Is $x$ binary? Do you also have $\sum_m x_{jm}=1$ for all $j$? $\endgroup$
    – RobPratt
    Commented Aug 25 at 18:06
  • $\begingroup$ Dear @RobPratt, yes. Actually the master is a set partitioning. The precedence and the rest of the constraint are in the sub. $\endgroup$
    – A.Omidi
    Commented Aug 25 at 18:25
  • $\begingroup$ You have a linking constraint across $m$. You can impose any relaxation of it into subproblem $m$, but $x_{jm} \le x_{km}$ is not a relaxation. $\endgroup$
    – RobPratt
    Commented Aug 25 at 18:36
  • 1
    $\begingroup$ Precedence is fundamentally a constraint that involves more than one $m$. Instead of decomposing by machines, you could decompose by clusters of tasks. Then any precedences that involve tasks in the same cluster can be imposed in the corresponding subproblem. $\endgroup$
    – RobPratt
    Commented Aug 25 at 19:01
  • 1
    $\begingroup$ Your idea about $w_j$ and $w_k$ then involves linking variables that cannot appear in different subproblems. $\endgroup$
    – RobPratt
    Commented Aug 25 at 19:02

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.