I have to linearize the following constraint,
$$ \sum_{i \in V_C} \sum_{j \in V} \sum_{k \in K} y_{ik} \cdot x_{ijk\ell} \leq I_\ell \qquad \forall \ell \in V_D $$
where $y$ is a integer variable smaller than $v_i$ and $x$ is a binary variable. I have found some other question about this but there they do not have the combination of a integer value with a binary and no summation. Does anyone know how to linearize this constraint?
Best Answer
The following assumes that $y_{ik} \geq 0$.
First, let's introduce a new set of variables $z_{ijk\ell}$: \begin{gathered} \sum_{i,j,k} z_{ijkl} \leq I_\ell \qquad \forall \ell \\ y_{ik} \cdot x_{ijk\ell} = z_{ijk\ell} \qquad \forall i,j,k,\ell \end{gathered} I hope you don't mind that for brevity I've dropped the index sets. This is equivalent (in $x$ and $y$) to \begin{gathered} \sum_{i,j,k} z_{ijkl} \leq I_\ell \qquad \forall \ell \\ y_{ik} \cdot x_{ijk\ell} \leq z_{ijk\ell} \qquad \forall i,j,k,\ell \end{gathered} This works because when the original inequality is feasible, we can always choose to have equality hold: but if there is slack in that inequality, we could distribute that slack across the values of $z_{ijk\ell}$ without changing equivalence.
Now that we've done that, we can use this equivalence: $$y_{ik} \geq 0, ~~ y_{ik} \cdot x_{ijk\ell} \leq z_{ijk\ell} \quad\Longleftrightarrow\quad 0 \leq z_{ijk\ell}, ~~ y_{ik} - v_i ( 1 - x_{ijk\ell} ) \leq z_{ijk\ell}$$ If $x_{ijk\ell}=0$, then $z_{ijk\ell}\geq 0$ will be active. If $x_{ijk\ell}=1$, then the second constraint will be active, and it will be equivalent to $y_{ik} \leq z_{ijk\ell}$.
So the final conversion is \begin{gathered} \sum_{i,j,k} z_{ijkl} \leq I_\ell \qquad \forall \ell \\ y_{ik} - v_i (1- x_{ijk\ell}) \leq z_{ijk\ell} \qquad \forall i,j,k,\ell \\ 0 \leq z_{ijk\ell} \qquad \forall i,j,k,\ell \end{gathered}