4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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}$)? $\endgroup$
    – prubin
    Nov 22, 2022 at 16:47
  • $\begingroup$ Yes exactly, at least $m$ ones must have a corresponding zero at the same column in another row, the same row for all zeroes. $\endgroup$ Nov 22, 2022 at 17:07

1 Answer 1

2
$\begingroup$

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

$\endgroup$

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.