Difficult linearization of a constraint

Question

My previous question was about this ILP with all binary variables:

$$\min \sum_{1\leq i<j\leq n-1-h} t_{i,j}$$ $$\sum_{i=1}^{n-1-h} a_{k,i} = \lfloor (n-1)/2\rfloor \qquad \text{for }k\in[h];$$ $$a_{k,i} + a_{k,j} \leq 2 d_{k,i,j}\qquad \text{for }1\leq i<j\leq n-1-h,\ k\in[h];$$ $$\sum_{k=1}^h d_{k,i,j} \leq h - 1 + t_{i,j}\quad \text{for }1\leq i<j\leq n-1-h$$

for $n=53$ and $h=13$. Only as a background, in case someone is interested, it was related to this setup for the union-closed sets conjecture.

Unfortunately, the minimum found in one answer to the linked question is zero. I hoped to get a fairly high value.

However, not all restrictions were put into the problem.

Another one that could be added, due to the original problem, is this: add to the matrix $A$ of variables $a_{i,j}$, $1 \le i \le h$, $1 \le j \le n-1-h$, $13$ additional columns forming an identity matrix, plus one all zero column. After that, verify that the logical AND of any two columns of the so expanded matrix is an existing column of the same expanded matrix (although obviously it is not necessary to check the identity matrix). Intuitively, this tends to increase the number of zeroes per column, or at least does not allow a solution where the zeroes are uniformly distributed among the columns.

Is there a way to add that restriction in an integer linear program?

I understand that might be quite difficult, but maybe there is a way not to add the full restriction, but a reduced version of it, easier to implement, maybe some property (e.g. in the count of $0$s) implied by it.

Any hint?

Answer 1

One way to do it involves adding binary variables $z_{i,j,\ell},$ where $i<j$ index a pair of original columns and $\ell$ indexes a column in the expanded matrix. We will enforce $z_{i,j,\ell}=1 \implies a_{k,\ell} = a_{k,i} \cdot a_{k,j}$ for all rows $k,$ where $[a_{.,.}]$ is your expanded matrix. To ensure that the AND of any two original columns is a column in the expanded matrix, you just need the constraints $$\sum_\ell z_{i,j,\ell} = 1 \quad\forall i < j.$$Constraints to enforce the definition of $z$ are: $$a_{k,\ell} \le a_{k,i} + 1 - z_{i,j,\ell}$$ $$a_{k,\ell} \le a_{k,j} + 1 - z_{i,j, \ell}$$ and $$a_{k,\ell} \ge a_{k,i} + a_{k,j} + z_{i,j,\ell} - 2,$$ where all these constraints are enforced for all rows $k,$ original columns $i<j$ and expanded columns $\ell.$