I need to enforce the following constraint:
$[y_{i}, y_{i} + c_{i}) \cap [y_j, y_j + c_j) = \varnothing$ if $x_{ik} = 1$ and $x_{jk} = 1$.
Here, $x_{*} \in \{0,1\}$ and $y_* \in \mathbb{Z^+},$ are the decision variables, and $c_*$ are constants.
I have tried expressing the intersection as:
\begin{equation} y_i \ge (y_j + c_j)\cdot x_{ik} \cdot x_{jk} \\ \text{or} \\ y_j \ge (y_i + c_i)\cdot x_{ik} \cdot x_{jk} \end{equation}
Next, we can introduce a new variable $w_{ijk} = 1$ iff $x_{ik} + x_{jk} = 2$, $w_{ijk} = 0$ otherwise. This helps us modify the problem as:
\begin{equation} y_i \ge (y_j + c_j)\cdot w_{ijk} \\ \text{or} \\ y_j \ge (y_i + c_i)\cdot w_{ijk} \end{equation}
I do understand that introduction of $w_*$ will lead to a significant increase in the number of variables, but I am hoping that the fact that the problem remains linear will help in reaching the solution faster.
I have two questions:
- Is this formulation linear? Or am I missing something.
- Is there a more elegant way of achieving the same.
You want to enforce $$(x_{i,k} \land x_{j,k}) \implies (y_{i} + c_{i} \le y_j \lor y_j + c_j \le y_{i}).$$ Let $\overline{y}_{i,j}$ be a finite upper bound on $y_{i,j}$. Introduce binary variables $z_{i,j}$ and linear constraints \begin{align} x_{i,k} + x_{j,k} - 1 &\le z_{i,j} + z_{j,i} &&\text{for $i<j$ and all $k$} \tag1\\ y_{i} + c_{i} - y_j &\le (\overline{y}_{i} + c_{i})(1-z_{i,j}) &&\text{for $i\not=j$} \tag2 \end{align} Constraint $(1)$ enforces $(x_{i,k} \land x_{j,k}) \implies (z_{i,j} \lor z_{j,i})$. Constraint $(2)$ enforces $z_{i,j} \implies y_{i} + c_{i} \le y_j$.
A classical reference is Manne, On the Job-Shop Scheduling Problem, Operations Research (1960).