MIP- If then with either or

312 Views Asked by At

I need something like this It may sound silly but I couldn't find a way to express this.

x,te,ts decision variables, x bool, te,ts >=0;

if $x[m,i]+x[m,j]-1 > 0$ then either $te[i]+d-ts[j]<=0$ or $te[j]+d-ts[i]<=0$;

If this was only either or I can make it with big-$M$ method, or I can convert an if then to either or, but I have a nested situtiation

Is it possible to express this in a linear programming model? Or maybe my decision variables are wrong.

1

There are 1 best solutions below

3
On BEST ANSWER

It looks like you want to assign jobs to machines, and if jobs $i$ and $j$ both get assigned to machine $m$ then you want to process job $i$, wait $d$ units, and process job $j$, or vice versa. You can do this by introducing binary variables $p_{ij}$ for $i \not= j$, together with linear constraints: \begin{align} x_{m,i} + x_{m,j} - 1 &\le p_{ij} + p_{ji} &&\text{for all $m$ and $i < j$} \tag1 \\ te_i + d - ts_j &\le M_{ij} (1 - p_{ij}) &&\text{for $i \not= j$} \tag2 \end{align} Constraint $(1)$ enforces $x_{m,i} \land x_{m,j} \implies p_{ij} \lor p_{ji}$, and constraint $(2)$ enforces $p_{ij} \implies te_i + d \le ts_j$.