Assistance in formulating binary constraint(s) - Operations Research Stack Exchange most recent 30 from or.stackexchange.com 2022-01-20T20:35:28Z https://or.stackexchange.com/feeds/question/7121 https://creativecommons.org/licenses/by-sa/4.0/rdf https://or.stackexchange.com/q/7121 3 Assistance in formulating binary constraint(s) Mike https://or.stackexchange.com/users/3682 2021-10-16T10:52:32Z 2021-10-18T12:12:14Z <p>I would like to seek some advice on modeling the following logical condition:</p> <p>Given two groups of binary decision variables <span class="math-container">$A_{i}, i=1...n,$</span> and <span class="math-container">$B_{j}, j=1...m$</span>.</p> <p><span class="math-container">$A_{i}=1- B_{j}, \forall i, \forall j$</span></p> <p>i.e., if one of <span class="math-container">$A_{i}=1$</span>, all <span class="math-container">$B_{j}$</span> must be zero, and vice-versa.</p> <p>Besides, the above equality constraint, I would like to include tighter cuts, but have only managed to come up with the following:</p> <p><span class="math-container">$\left\lvert B\right\rvert *A_{i}\le \left\lvert B\right\rvert-\sum_{j=1}^{j=m}B_{j}, \forall i$</span></p> <p><span class="math-container">$A_{i}\ge 1-\sum_{j=1}^{j=m}B_{j}, \forall i$</span></p> <p>Thank you!</p> https://or.stackexchange.com/questions/7121/-/7122#7122 1 Answer by Richard for Assistance in formulating binary constraint(s) Richard https://or.stackexchange.com/users/133 2021-10-16T12:00:41Z 2021-10-18T12:12:14Z <p>I would add an auxiliary variable <span class="math-container">$z\in\{0,1\}$</span>:</p> <p><span class="math-container">$$z \geq a_i \ \ \forall a_i \in A$$</span></p> <p>Then you can write:</p> <p><span class="math-container">$$b_j \leq 1-z \ \ \forall b_j \in B$$</span></p> <p>If <span class="math-container">$z=0$</span>, then the constraint is redundant. However, if <span class="math-container">$z=1$</span>, then all elements of <span class="math-container">$B$</span> have to be 0.</p> <hr> <p>Update: @RobPratt correctly pointed out that the above formulation allows for <span class="math-container">$a_i = b_j = 0$</span>, which violates the requirement the initial requirements. To fix this, I suggest to add:</p> <p><span class="math-container">$$z \leq \sum_i a_i \\ \sum_j b_j = 1 -z$$</span></p> https://or.stackexchange.com/questions/7121/-/7124#7124 4 Answer by RobPratt for Assistance in formulating binary constraint(s) RobPratt https://or.stackexchange.com/users/500 2021-10-16T13:58:44Z 2021-10-16T14:27:39Z <p>Via conjunctive normal form: <span class="math-container">$$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) \\$$</span> The other implication <span class="math-container">$$B_j \implies \bigwedge_i \lnot A_i$$</span> yields the same linear constraints.</p> <p>From your comment, you also want to enforce <span class="math-container">$$\lnot A_i \implies \bigwedge_j B_j,$$</span> which yields <span class="math-container">$A_i+B_j\ge 1$</span>. Together, these two sets of inequality constraints become the equality constraints <span class="math-container">$A_i+B_j=1$</span>. There are only two solutions to this linear system, and you can capture that more compactly (with <span class="math-container">$n+m$</span> constraints instead of <span class="math-container">$nm$</span> constraints) by introducing a single binary variable <span class="math-container">$z$</span>, with <span class="math-container">$A_i=z$</span> for all <span class="math-container">$i$</span> and <span class="math-container">$B_j=1-z$</span> for all <span class="math-container">$j$</span>.</p>