# Constraint for two binary vectors to be different

If I have a matrix $$A$$ of binary variables $$a_{i,j}$$, $$1 \le i \le n$$, $$1 \le j \le m$$, how can I enforce in an Integer Linear Program with binary variables, the condition that every two columns must be different?

I know from here how to do it for a single row (two elements), for example requiring that the XOR of the two values be equal to $$1$$, but how to do it on the full column? Is making the OR over all the rows the only option?

If you encode the column to be a single binary number, the first column is either larger or less than the second column. Define binary variables $$b_{j, j'}$$ forall $$1 \leq j < j' \leq m$$. $$\sum_{i} 2^i(a_{i, j} - a_{i, j'}) \geq 1 - 2^{n+1} b_{j, j'}\\ \sum_{i} 2^i(a_{i, j} - a_{i, j'}) \leq -1 + 2^{n+1}(1 - b_{j, j'})$$

This model has less auxiliary variables but many large coefficients.

• I think the subscripts are transposed. This seems to enforce a difference between rows $i$ and $i'.$
– prubin
Nov 21, 2022 at 16:32

Let binary decision variable $$x_{ijk}$$ indicate whether columns $$j$$ and $$k$$ (with $$j) differ in row $$i$$, and impose linear constraints \begin{align} \sum_i x_{ijk} &\ge 1 &&\text{for j Constraint \eqref{1} enforces $$\bigvee_i x_{ijk}$$ for column pair $$(j,k)$$. Constraint \eqref{2} enforces $$x_{ijk} \implies a_{ij} + a_{ik} = 1$$. Because $$a$$ is binary, $$a_{ij} + a_{ik} = 1$$ is equivalent to $$a_{ij} \not= a_{ik}$$.

This is an "alldifferent" constraint. In addition to the two approaches already described, I'll describe two more.

# Binary encoding

Yet another way is to use a binary encoding of a location that differs, rather than a one-hot encoding as in RobPratt's answer. In particular, we'll have binary decision variables $$x_{jk\ell}$$, where $$x_{jk\lg n} \cdots x_{jk1} x_{jk0}$$ is intended to be interpreted as the binary representation of a row $$i$$ such that $$a_{i,j} \ne a_{i,k}$$. To ensure this representation is valid, we add the constraint

$$(x_{jk0} \ne i_0) \lor (x_{jk1} \ne i_1) \lor \dots \lor (x_{jk\lg n} \ne i_{\lg n})$$

for every $$i,j,k$$ such that $$a_{i,j} = a_{i,k}$$. Here I write $$i_\ell$$ for the $$\ell$$th bit of the binary representation of $$i$$. The above constraint can be expressed as a linear inequality as

$$1 \le \sum_{i_\ell=0} x_{jk\ell} + \sum_{i_\ell=1} (1-x_{jk\ell}),$$

where the first sum ranges over $$\ell$$ such that $$i_\ell=0$$ and the second sum ranges over $$\ell$$ such that $$i_\ell=1$$, and we have one linear inequality per $$i,j,k$$ such that $$a_{i,j}=a_{i,k}$$ and $$j.

This approach uses about $$0.5 m^2 \lg n$$ binary variables and $$0.5 m^2 n$$ linear inequalities. Compare to RobPratt's answer, which uses $$m^2 n$$ binary variables and $$m^2 n$$ linear inequalities. So, this approach is more concise than RobPratt's answer: it uses significantly fewer variables and $$2\times$$ fewer inequalities. However, it is possible that it might play less well with solvers (e.g., because randomized rounding is less likely to be effective).

# Sorting networks

Another approach is to build a sorting network to sort the $$m$$ columns, then after they are put into sorted order, add constraints to ensure that each adjacent pair of columns are different.

You can build a sorting network to sort the $$m$$ columns using $$O(\log^2 m)$$ layers, where each layer has $$O(m)$$ comparators. You can express each comparator in ILP using $$O(n)$$ binary variables and $$O(n)$$ linear inequalities. This leads to a sorting network that uses $$O(mn\log^2 m)$$ variables and inequalities. The final check that each adjacent pair of columns are different can be done with $$O(mn)$$ variables and inequalities.

So, in total, this gives a solution that encodes your problem as an ILP instance with $$O(mn \log^2 m)$$ variables and inequalities. For small $$m,n$$, this is probably worse than the other approaches, but for large values of $$m$$, it is possible that this might work better.