Given four sets of binary variables $x_{1..N}$, $y_{1..N}$, $v_{1..N}$, and $w_{1..N}$ such that $\Sigma_{i=1}^{N} x_i = \Sigma_{i=1}^{N} y_i = \Sigma_{i=1}^{N} v_i = \Sigma_{i=1}^{N} w_i = 1$, I need to linearize the following constraint:
$\Sigma_{i=1}^{N} x_i y_i \leq \Sigma_{i=1}^{N} v_i w_i$.
All binary variables have value in $\{0, 1\}$. This constraints means that if for an $i \in \{1,.., N\}$, it holds that $x_i=y_i=1$, then for a $j \in \{1,.., N\}$, it must hold that $v_j=w_j=1$. In other words, if the dot product of vectors $\textbf{x}$ and $\textbf{y}$ is one, then the dot product of vectors $\textbf{v}$ and $\textbf{w}$ must also be 1 (based on the assumption in the first line, all vectors $\textbf{x}$, $\textbf{y}$, $\textbf{v}$, and $\textbf{w}$ are unit vectors in $R^{N}$).
1. Approach 1
I know that I can introduce for each $i$, a new variable $\alpha_i$ to mean that $\alpha_i = x_i y_i$ by the following constraints:
$\alpha_i \leq x_i$
$\alpha_i \leq y_i$
$\alpha_i \ge x_i + y_i -1$,
and, in a similar manner, introduce a new variable $\beta_i$ to mean $\beta_i = v_i w_i$, and, finally, replace the original constraint by the following:
$\Sigma_{i=1}^{N} \alpha_i \leq \Sigma_{i=1}^{N} \beta_i$.
The problem of this approach is that it considerably slows down my program implemented in cplex.
I need to use a different approach that is faster than this.
thanks
2. Approach 2
One other approach was to introduce only two new binary variables $\lambda$ and $\xi$, whose values are in $\{0, 1\}$ and restricted by the following constraints:
$\lambda \ge x_i+y_i-1 \;\;\;\;\;\;\;\;\;\;\;\; , \forall i\in \{1,…,N\}$
$\xi \ge v_i+w_i-1 \;\;\;\;\;\;\;\;\;\;\;\; , \forall i\in \{1,…,N\}$,
Accordingly, the original constraint is formulated by the following constraint:
$\lambda \leq \xi$.
This approach is extremely faster than the first approach, but it works only for one case, where for an $i \in \{1,…, N\}$, it holds that $x_i=y_i=1$, which enforces that it must hold that $v_j=w_j=1$ for a $j \in \{1, …, N\}$. For the other case, where for no $i$, it holds that $x_i = y_i = 1$, the value of $\lambda$ is not constrained to by 0, and so it makes problem.
Best Answer
The following should do what you want, with only one set of $N$ additional binary variables $\beta_j$: \begin{align} x_i + y_i - 1 &\le \sum_{j=1}^N \beta_j &\text{for all $i$}\\ \beta_j &\le v_j &\text{for all $j$}\\ \beta_j &\le w_j &\text{for all $j$} \end{align}
Alternatively, you can aggregate the last two constraints at the expense of weakening the linear programming relaxation: \begin{align} x_i + y_i - 1 &\le \sum_{j=1}^N \beta_j &\text{for all $i$}\\ 2\beta_j &\le v_j + w_j &\text{for all $j$} \end{align}