Integer Linear Programming: Sum of Products of Binary Variables

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.

• It is not clear - the binary values can be negative or only (0,1)? – Moti Aug 25 '18 at 4:49
• each binary variable is either 0 or 1 – hrsc Aug 25 '18 at 4:52

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.

• I appreciate your help. I made the variables to be continuous, which made nearly a 60% of speed improvement for a few instances I checked. But, I am not sure if this change will always return feasible integer solutions or not. I need to check more. – hrsc Aug 28 '18 at 7:27
• With respect to your suggestion for the first approach, I am not sure why omitting those constraints you mentioned should work. But, one thing about the variables is that for each i, at most one product of $x_i y_i$ has the value 1, and at most one product of $v_i w_i$ is equal to 1 given 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$. – hrsc Aug 28 '18 at 7:34
• As I said, the second approach works only in certain cases, but for some instance I have checked, it takes less than 1% of time spent by the first approach. It would be good if it was possible to put some simple constraints imposing upper bounds on $\lambda$ and $\xi$ to make them have the precise meanings of $\Sigma_{i=1}^N x_i y_i$ and $\Sigma_{i=1}^N v_i y_i$, respectively. – hrsc Aug 28 '18 at 7:46

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}