Another difficult constraint for an ILP

Question

How can I add to this ILP with all binary variables (again related to this question):

$$\min \sum_{1\leq i<j\leq n-1-h} t_{i,j}$$ $$\sum_{i=1}^{n-1-h} a_{k,i} \ge \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$$

where I have modified $=$ into $\ge$ with respect to the linked question, the requirement that for each row $k$ of the $h \times n-h-1$ matrix $A$ with elements $a_{k,i}$ there exists at least another row $p$ with elements $a_{p,i}$ such that there are at least $m = \lceil(n+1)/4\rceil-1$ indexes $1 \le i_1 \le \ldots \le i_m \le n-1-h$ such that $a_{k,i_j}=1 \land a_{p,i_j}=0$, $1 \le j \le m$?

Answer 1

For lack of anything better, I will use the term "complements" to indicate that a row $p$ satisfies the desired condition with respect to a different row $k.$ For $k \neq p$ and all $i$ we can introduce binary variables $z_{k,p,i}$ and $w_{k,p},$ where $z_{k,p,i}=1 \implies a_{k,i}=1\wedge a_{p,i}=0$ and $w_{k,p}=1\implies$ row $p$ complements row $k.$ The requirement that some row complement row $k$ is just $$\sum_{p \neq k} w_{k,p} \ge 1.$$ The constraints defining $z$ are $$z_{k,p,i} \le a_{k,i}$$ and $$z_{k,p,i} \le 1 - a_{p,i}.$$ Finally, the connection between $w$ and $z$ is $$m\cdot w_{k,p} \le \sum_i z_{k,p,i}.$$