4
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – prubin
    Commented Nov 20, 2022 at 19:58
  • $\begingroup$ Also, when you say "linear program" do you actually mean "integer linear program"? $\endgroup$
    – prubin
    Commented Nov 20, 2022 at 20:01
  • $\begingroup$ @prubin yes ILP. Also, I had forgotten the all-zero column, which is needed and also makes checking the identity matrix unnecessary. Edited now. $\endgroup$ Commented Nov 20, 2022 at 20:14
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Nov 21, 2022 at 4:02

1 Answer 1

3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Looks like this enforces only the $\implies$ direction, but that is enough. Also, the $= 1$ should be relaxed to $\ge 1$, right? $\endgroup$
    – RobPratt
    Commented Nov 20, 2022 at 21:23
  • $\begingroup$ @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. $\endgroup$
    – prubin
    Commented Nov 20, 2022 at 22:31
  • $\begingroup$ 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. $\endgroup$ Commented Nov 25, 2022 at 19:47
  • 1
    $\begingroup$ 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. $\endgroup$
    – prubin
    Commented Nov 25, 2022 at 20:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.