4
$\begingroup$

In an scheduling optimization problem, for job $l$, $\xi_l$ is binary variable that $\xi_l=1$ shows job $l$ is selected. $t_{r,l}$ and $t_{e,l}$ are registration time and time that job is completed. Also, each job can wait for $t_l$. In this problem, one contrarian disallows any parallel activities. This constraint is XOR: \begin{align} &\begin{cases}T_{r,l}+t_l\geq (\xi_l+\xi_{l^\prime}-1)(T_{e,l^\prime}+t_{l^\prime})\quad\forall l\neq l^\prime\\\hspace{3cm}\text{xor}\\T_{r,l^\prime}+t_{l^\prime}\geq (\xi_l+\xi_{l^\prime}-1)(T_{e,l}+t_{l})\quad\forall l\neq l^\prime\end{cases} \end{align} How can I merge these two part in one (linear form) constriction? Can I represent this constraint using other equation?

$\endgroup$
  • 1
    $\begingroup$ It would be great if you consolidated all your posts and provided complete information on your problem in one place. $\endgroup$ – CMichael Sep 20 '19 at 11:21
  • 5
    $\begingroup$ Actually I disagree somewhat with @CMichael's suggestion. On SE it is generally preferred to have a separate post for each question (rather than one post with many questions) so that individual questions can be answered, voted on, etc. On the other hand, I agree that it might make sense for you to include a more complete set of information in one of your posts, and then link to it from other posts to provide additional context. $\endgroup$ – LarrySnyder610 Sep 20 '19 at 12:15
  • 3
    $\begingroup$ But I think an even more useful suggestion would be to make your posts somewhat more generic. This will make them easier for us to understand and answer, and will also make them more useful to future readers. For example, maybe your XOR constraints are equivalent to $x_1 \ge y_1z_1$ XOR $x_2 \ge y_2z_2$ for suitable continuous variables $x$ and $z$ and binary variables $y$; then you can ask the question that way, and translate the answers to your specific instance. $\endgroup$ – LarrySnyder610 Sep 20 '19 at 12:19
  • 1
    $\begingroup$ Larry you are of course right with respect to breaking it apart into atomic problems. But this series of posts started off without mentioning scheduling and I asked for clarification on that respect. Then a new post emerged which used my comment to ask something similar and now we learn for the first time what the timestamps mean (eg registration time). In a sense this is the most complete of the bunch but I have a hard time seeing the bigger picture which may ultimately be decisive. $\endgroup$ – CMichael Sep 20 '19 at 12:42
  • 1
    $\begingroup$ @CMichael agreed; these questions would benefit from a bigger picture. $\endgroup$ – LarrySnyder610 Sep 20 '19 at 17:38
1
$\begingroup$

Let $L$ be the count of $\xi_l$.

To prevent any $\xi_l=1$ when $\xi_{l^\prime}=1$, we can have $\sum\xi_l+\xi_{l^\prime}L\le L$.

To prevent the case when all binary are $0$, we can have $\sum\xi_l+\xi_{l^\prime}>0$.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.