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.


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.

  • $\begingroup$ It is not clear - the binary values can be negative or only (0,1)? $\endgroup$ – Moti Aug 25 '18 at 4:49
  • $\begingroup$ each binary variable is either 0 or 1 $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – hrsc Aug 28 '18 at 7:27
  • $\begingroup$ 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$. $\endgroup$ – hrsc Aug 28 '18 at 7:34
  • $\begingroup$ 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. $\endgroup$ – 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}


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.