I have six binary variables (b1, b2, b3, b4, d1 and d2). I wonder if somebody here could help me to convert the following conditional constraints into linear ones: If b1 + b2 + b3 + b4 = 4 Then d1 = 0 Or d2 = 0 I tried to solve this problem by defining two other binary variables, is this correct? b1 + b2 + b3 + b4  4 <= c1 d1 <= M*c2 d2 <= M*(1  c2) c1 + c2 <= 1 b1, b2, b3, b4, d1, d2, c1, c2 => binary asked 20 Oct '15, 13:37 mvaguimaraes 
Hint: rewriting the logical proposition \[\bigwedge_{i=1}^4 b_i \implies \neg d_1 \vee \neg d_2\] in conjunctive normal form yields a single linear constraint that does the job, without any auxiliary binary variables. answered 20 Oct '15, 15:16 Rob Pratt Thanks for the reply! But I don't know if I understood what you said or if it can be applied to what I'm doing. I want to convert the conditional constraint above into a linear constraint in order to solve a problem using Gurobi on MatLab. Since I need to give Gurobi a constraint Matrix with the index of each variable, I can't see a way to do that using the conjuctive normal form you wrote it down for me. Would you mind explaining it to me a little bit more?
(20 Oct '15, 15:32)
mvaguimaraes
See this related post that contains both an example and a reference: https://www.orexchange.org/questions/7335/ilpconsecutiveadjacentvariablesconstraint?page=1&focusedAnswerId=7343#7343
(20 Oct '15, 15:49)
Rob Pratt
Thanks once again! Following the logic on this example I got this: if ( b1 + b2 + b3 + b4 = 4 ) then ( d1 = 0 or d2 = 0 ) <=> not ( b1 + b2 + b3 + b4 = 4 ) or ( not ( d1 ) or not ( d2 ) ) <=> ( b1 + b2 + b3 + b4 = 0 ) or (d1 = 1 or d2 = 1) <=> 1  ( b1 + b2 + b3 + b4 ) + d1 + d2 <= 1 <=> b1  b2 b3  b4 + d1 + d2 <= 0 Is this correct?
(20 Oct '15, 16:23)
mvaguimaraes
Almost. Think of b1 + b2 + b3 + b4 = 4 as b1 = 1 and b2 = 1 and b3 = 1 and b4 = 1. Then use the fact that NOT of AND becomes OR of NOT.
(20 Oct '15, 17:18)
Rob Pratt
If I understood what you said correctly, it would be something like that: if ( b1 + b2 + b3 + b4 = 4 ) then ( d1 = 0 or d2 = 0 ) <=> if ( b1 = 1 and b2 = 1 and b3 = 1 and b4 = 1 ) then ( d1 = 0 or d2 = 0 ) <=> not (b1 = 1 or b2 = 1 or b3 = 1 or b4 = 1 ) or ( not ( d1 ) or not ( d2 ) ) <=> ( b1 = 0 or b2 = 0 or b3 = 0 or b4 = 0 ) or (d1 = 1 or d2 = 1) <=> (1  b1) + (1  b2) + (1  b3) + (1  b4) + d1 + d2 <= 1 <=> b1  b2 b3  b4 + d1 + d2 <= 3 Am I right?
(20 Oct '15, 18:53)
mvaguimaraes
That is closer, but you still have some errors. Here's a full derivation: \begin{align} &\bigwedge_{i=1}^4 b_i \implies \neg d_1 \vee \neg d_2 \\ &\neg\bigwedge_{i=1}^4 b_i \vee \neg d_1 \vee \neg d_2 \\ &\bigvee_{i=1}^4 \neg b_i \vee \neg d_1 \vee \neg d_2 \\ &\sum_{i=1}^4 (1  b_i) + (1  d_1) + (1  d_2) \ge 1 \\ &\sum_{i=1}^4 b_i + d_1 + d_2 \le 5, \end{align} which is another way of saying that not all six binary variables can be equal to 1.
(20 Oct '15, 19:58)
Rob Pratt
Thank you very much my friend!
(20 Oct '15, 20:07)
mvaguimaraes
showing 5 of 7
show 2 more comments
