Modeling a quadratic constraint with a linear expression

Question

In a problem I am trying to model with a MIP program, the following scenario occurs:

I am given binary variables $x_1,\ldots,x_n$ and $y_1,\ldots,y_n$ which can really be regarded as $n$-vectors. What I need to compute is the number of bits in which they differ. In particular I just need to make sure they are only equal in at most one bit.

This can be done by adding the following quadratic constraint

$$\sum_{i=1}^n x_i y_i \leq 1$$

Given the very specific nature of this condition, I am wondering

Is there a better way to express this?

and

Is there a trick to convert this expression into a linear one?

Answer 1

Intropduce a new variable $z_i$ to represent $x_iy_i$ (logical and). Your constraint is $\sum_{i=1}^n z_i \leq 1$, and the product is modelled by $x_i + y_i -1 \leq z_i$.

Answer 2

Suppose $$z_{i} = x_{i} \times y_{i}$$ The constraint $$ \sum_{i=1}^{n} x_{i}y_{i}\le 1 $$ can be reformulated as linear constraints:

1) $$ \sum_{i=1}^{n} z_{i}\le 1 $$ 2) $$ z_{i}\le x_{i} $$ 3) $$ z_{i}\le y_{i} $$ 4) $$ z_{i}\ge x_{i} + y_{i} -1 $$