# Expressing conditional constraints as linear constraints

 0 1 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 13●3 accept rate: 0%

 1 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 1.2k●2●6 accept rate: 28% 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.or-exchange.org/questions/7335/ilp-consecutiveadjacent-variables-constraint?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
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

×27
×23
×14
×4
×2