3
$\begingroup$

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!

$\endgroup$
10
  • $\begingroup$ Your first constraint and subsequent description are inconsistent, Did you mean instead $A_i\le 1-B_j$? $\endgroup$
    – RobPratt
    Oct 16, 2021 at 13:49
  • $\begingroup$ Nope, maybe it would help to retain the first one and ignore the remaining constraints. Thank you. $\endgroup$
    – Mike
    Oct 16, 2021 at 13:57
  • $\begingroup$ 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 $\endgroup$
    – Mike
    Oct 16, 2021 at 14:20
  • $\begingroup$ Hard to say without seeing your full model. Probably best to open a separate question for that. $\endgroup$
    – RobPratt
    Oct 16, 2021 at 14:32
  • $\begingroup$ Sure, thank you! $\endgroup$
    – Mike
    Oct 16, 2021 at 14:49

2 Answers 2

4
$\begingroup$

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

$\endgroup$
0
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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! $\endgroup$
    – Mike
    Oct 16, 2021 at 12:23
  • $\begingroup$ This formulation allows $A_i=0$ and $B_j=0$, which violates $A_i=1-B_j$. $\endgroup$
    – RobPratt
    Oct 17, 2021 at 18:31
  • $\begingroup$ Unfortunately, your modification is too strong because $\sum_j b_j = 1-z$ allows at most one $b_j$ to be $1$. $\endgroup$
    – RobPratt
    Oct 18, 2021 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.