# Another difficult constraint for an ILP

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

$$\min \sum_{1\leq i $$\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 $$\sum_{k=1}^h d_{k,i,j} \leq h - 1 + t_{i,j}\quad \text{for }1\leq i

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

• Just to be sure, you specifically want row $k$ to contain a 1 and row $p$ to contain a zero in every column $i_j,$ as opposed to the less stringent condition that the rows differe there ($a_{k,i_j} \neq a_{p,i_j}$)?
– prubin
Nov 22, 2022 at 16:47
• Yes exactly, at least $m$ ones must have a corresponding zero at the same column in another row, the same row for all zeroes. Nov 22, 2022 at 17:07

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