Constraint for two binary vectors to be different

Question

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?

Answer 1

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.

Answer 2

Let binary decision variable $x_{ijk}$ indicate whether columns $j$ and $k$ (with $j<k$) differ in row $i$, and impose linear constraints \begin{align} \sum_i x_{ijk} &\ge 1 &&\text{for $j<k$} \tag1\label1\\ x_{ijk} \le a_{ij} + a_{ik} &\le 2-x_{ijk} &&\text{for all $i$ and $j<k$} \tag2\label2 \end{align} 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}$.

Answer 3

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

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.