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's gravatar image

mvaguimaraes
133
accept rate: 0%

edited 20 Oct '15, 15:51


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.

link

answered 20 Oct '15, 15:16

Rob%20Pratt's gravatar image

Rob Pratt
1.2k26
accept rate: 28%

edited 20 Oct '15, 15:17

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
(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
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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

Asked: 20 Oct '15, 13:37

Seen: 572 times

Last updated: 20 Oct '15, 20:07

OR-Exchange! Your site for questions, answers, and announcements about operations research.