4

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?

Fabius Wiesner
  • 393
  • 1
  • 7
  • Do you mean the logical AND of any two columns including the identity columns, or do you mean that the logical AND of any two original columns must be a column in the expanded matrix (including identity columns), or something else? – prubin Nov 20 '22 at 19:58
  • Also, when you say "linear program" do you actually mean "integer linear program"? – prubin Nov 20 '22 at 20:01
  • @prubin yes ILP. Also, I had forgotten the all-zero column, which is needed and also makes checking the identity matrix unnecessary. Edited now. – Fabius Wiesner Nov 20 '22 at 20:14
  • 1
    Please [edit] your question to state the desired constraint in a self-contained way, so we don't have to read the prior question to understand what constraint you are trying to enforce. – D.W. Nov 21 '22 at 04:02

1 Answers1

3

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

prubin
  • 39,078
  • 3
  • 37
  • 104
  • Looks like this enforces only the $\implies$ direction, but that is enough. Also, the $= 1$ should be relaxed to $\ge 1$, right? – RobPratt Nov 20 '22 at 21:23
  • @RobPratt: Good point about implication v. equivalence. I've corrected what I wrote. As far as relaxing the first equation, if it were actually equivalence then yes, you would need to relax the equation. Given that it is implication, both $=1$ and $\ge 1$ work. With equality, $z_{i,j,\ell}=1$ means column $\ell$ is the "official" (but not necessarily exclusive) AND of columns $i$ and $j.$ In terms of solver performance, I don't know if it makes a difference, but I suspect "=" makes things a bit tighter. – prubin Nov 20 '22 at 22:31
  • Just to be sure, this works also for $l=i$ or $l=j$ right? I just need to remove some constraint and simplify $a_{k,l}$ with $a_{k,i}$ or $a_{k,j}$ where needed, I think. – Fabius Wiesner Nov 25 '22 at 19:47
  • 1
    Yes, it works for $\ell = i$ and $\ell = j,$ and yes, you can simplify things a bit in those cases. For instance, when $\ell = i$ the first and third constraints are redundant and you just need the second one. – prubin Nov 25 '22 at 20:10