Assistance in formulating binary constraint(s)

Question

I would like to seek some advice on modeling the following logical condition:

Given two groups of binary decision variables $A_{i}, i=1...n,$ and $B_{j}, j=1...m$.

$A_{i}=1- B_{j}, \forall i, \forall j$

i.e., if one of $A_{i}=1$, all $B_{j}$ must be zero, and vice-versa.

Besides, the above equality constraint, I would like to include tighter cuts, but have only managed to come up with the following:

$\left\lvert B\right\rvert *A_{i}\le \left\lvert B\right\rvert-\sum_{j=1}^{j=m}B_{j}, \forall i$

$A_{i}\ge 1-\sum_{j=1}^{j=m}B_{j}, \forall i$

Thank you!

Answer 1

Via conjunctive normal form: $$ A_i \implies \bigwedge_j \lnot B_j \\ \lnot A_i \lor \bigwedge_j \lnot B_j \\ \bigwedge_j (\lnot A_i \lor \lnot B_j) \\ \bigwedge_j (1-A_i +1- B_j\ge 1) \\ \bigwedge_j (A_i +B_j\le 1) \\ $$ The other implication $$B_j \implies \bigwedge_i \lnot A_i$$ yields the same linear constraints.

From your comment, you also want to enforce $$\lnot A_i \implies \bigwedge_j B_j,$$ which yields $A_i+B_j\ge 1$. Together, these two sets of inequality constraints become the equality constraints $A_i+B_j=1$. There are only two solutions to this linear system, and you can capture that more compactly (with $n+m$ constraints instead of $nm$ constraints) by introducing a single binary variable $z$, with $A_i=z$ for all $i$ and $B_j=1-z$ for all $j$.

Answer 2

I would add an auxiliary variable $z\in\{0,1\}$:

$$ z \geq a_i \ \ \forall a_i \in A $$

Then you can write:

$$ b_j \leq 1-z \ \ \forall b_j \in B $$

If $z=0$, then the constraint is redundant. However, if $z=1$, then all elements of $B$ have to be 0.

---

Update: @RobPratt correctly pointed out that the above formulation allows for $a_i = b_j = 0$, which violates the requirement the initial requirements. To fix this, I suggest to add:

$$ z \leq \sum_i a_i \\ \sum_j b_j = 1 -z $$