2
$\begingroup$

Let's assume we have event $i=1,2,\cdots,k$, denoted as $\text{event}_i$. We know for a fact that $\text{event}_i$ is smaller then $\text{event}_{i+1}$ i.e., $\text{event}_i \leq \text{event}_{i+1}$. Now we have given some events $a,b,c,d \leq k$. How do I formulate the constraint that: if $\text{event}_a \leq \text{event}_b$ then $\text{event}_c \leq \text{event}_d$?

My try was:

\begin{align}\text{event}_a + Mz &> \text{event}_b\\\text{event}_c + M(1-z) &\leq \text{event}_d\end{align} where $z \in\{0,1\}$, $M$ large.

Improve this question
$\endgroup$
8
  • $\begingroup$ Given that you have weak inequalities, do you mean that each event is no larger than the subsequent event? $\endgroup$
    – TheSimpliFire ♦
    Dec 4, 2022 at 15:36
  • $\begingroup$ I must have that if event a is before event b then event c must be before event d $\endgroup$
    – OpenAtTheClose
    Dec 4, 2022 at 15:38
  • $\begingroup$ Your formulation seems to be ok. Just try with a solver or in excel to confirm. $\endgroup$
    – Sutanu Majumdar
    Dec 4, 2022 at 15:39
  • $\begingroup$ How would you formulate a constraint which has to be like: Either event a is before event b or event a is before event c, or both. $\endgroup$
    – OpenAtTheClose
    Dec 4, 2022 at 15:47
  • $\begingroup$ "Either a is before b or a is before c" is the same as "if b is before a then a is before c". $\endgroup$
    – prubin ♦
    Dec 4, 2022 at 17:04

1 Answer 1

Reset to default
7
$\begingroup$

You want to enforce the logical implication $$\text{event}_a \leq \text{event}_b \implies \text{event}_c \leq \text{event}_d.$$ Introduce a binary variable $z$ and enforce \begin{align} \text{event}_a \leq \text{event}_b \implies z = 1 \tag1\label1\\ z = 1 \implies \text{event}_c \leq \text{event}_d \tag2\label2 \end{align} Equivalently, by contraposition of \eqref{1}, \begin{align} z = 0 \implies \text{event}_a > \text{event}_b \tag3\label3\\ z = 1 \implies \text{event}_c \leq \text{event}_d \tag4\label4 \end{align} Now big-M modeling yields \begin{align} \text{event}_b - \text{event}_a &< M_1 z \tag5\label5\\ \text{event}_c - \text{event}_d &\le M_2(1-z) \tag6\label6 \end{align} This is very similar to what you tried, except that your second $M$ needs the opposite sign. Because MILP disallows strict inequalities, you need to introduce a positive tolerance $\epsilon$ and replace \eqref{5} with $$\text{event}_b - \text{event}_a +\epsilon \le M_1 z.$$ The effect is that you are enforcing $$\text{event}_a - \epsilon < \text{event}_b \implies \text{event}_c \leq \text{event}_d.$$

Improve this answer
$\endgroup$

Your Answer

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

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