# Assistance in formulating binary constraint(s)

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!

• Your first constraint and subsequent description are inconsistent, Did you mean instead $A_i\le 1-B_j$? Oct 16 '21 at 13:49
• Nope, maybe it would help to retain the first one and ignore the remaining constraints. Thank you.
– Mike
Oct 16 '21 at 13:57
• I am kinda perplexed, I just both tried the equality and inequality versions. It seems that inequality version outperforms the equality version. May I ask if you could offer some insights? Thank you
– Mike
Oct 16 '21 at 14:20
• Hard to say without seeing your full model. Probably best to open a separate question for that. Oct 16 '21 at 14:32
• Sure, thank you!
– Mike
Oct 16 '21 at 14:49

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

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

• Dear Richard, may I ask if you meant that I should use the two constraints which you suggested to replace the two which I have originally created? Thank you!
– Mike
Oct 16 '21 at 12:23
• This formulation allows $A_i=0$ and $B_j=0$, which violates $A_i=1-B_j$. Oct 17 '21 at 18:31
• Unfortunately, your modification is too strong because $\sum_j b_j = 1-z$ allows at most one $b_j$ to be $1$. Oct 18 '21 at 14:06