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?


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


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$.


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 $$


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.