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.
Your second approach makes no sense to me. With only two new binary variables, the best you will be able to determine is whether any product $x_i y_i = 1$, not how many such products equal 1.
In the first approach, did you give the $\alpha_i$ the domain $[0,1]$ (i.e., make them continuous variables)? I would not expect that to slow the solution very much. Those variables do not need to be declared integer-valued. It is possible that, by branching on them early, CPLEX might solve the problem faster, but my experience is that fewer integer variables is usually better.
Regarding the first approach, I believe you could omit the constraints $\alpha_i \le x_i$, $\alpha_i \le y_i$ and $\beta_i \ge v_i + w_i - 1$. This would allow the solver to set $\alpha_i = 1$ when either $x_i$ or $y_i$ was 0, and would let it set $\beta_i = 0$ when both $u_i$ and $v_i$ were 1, but the original constraint $\sum_i x_i y_i \le \sum_i u_i v_i$ would still be met: at least as many $\alpha_i$ would be 1 as the number of unit products on the left, and at most as many $\beta_i$ would be 1 as the number of unit products on the right.