Vtyjkyuk

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 $textbfx$ and $textbfy$ is one, then the dot product of vectors $textbfv$ and $textbfw$ must also be 1 (based on the assumption in the first line, all vectors $textbfx$, $textbfy$, $textbfv$, and $textbfw$ 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 iin 1,...,N$

$xi ge v_i+w_i-1 ;;;;;;;;;;;; , forall iin 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.