# Help with binary variable

I need to make a constraint for the following condition:

Among students 1, 2, 3, and 4, at least two of them must be on the team, if there are any on the team at all.

I have defined Y1, Y2, Y3, and Y4 to be 1 if student i is on the team and 0 if they are not.

My constraint looks as follows:

Y1 + Y2 + Y3 + Y4 >= 2 + MZ (where M is a very large number and Z is another binary variable) Y1 + Y2 + Y3 + Y4 = 0 + M(1-Z)

Would the constraint I wrote be correct to model this situation? Is there a way to make this constraint a single statement rather than two seperate ones?

Thanks for the help!

EDIT: Some more context: I am trying to make a linear programming model and these models cannot have "or" or "and" in them... essentially we must represent everything through equations that the solving software will try and satisfy simultaneously. Thus, the first set would not work since the computer software would try and satisfy both of them at once (since we cannot use OR). Additionally, we can only have equal signs and inequalities so your second one wouldn't work. Is there any other way to model this?

-
Well I just realized the constraint I wrote down makes no sense... it doesn't prevent one of them from being accepted if one of them is satisfied... any help would be much appreciated! –  icobes Mar 19 '11 at 21:16

Try these:

$$y_1 + y_2 + y_3 + y_4 \leq Mz,$$ $$2 - y_1 - y_2 - y_3 - y_4 \leq M(1-z),$$

where $z$ and the $y_i$'s are binary, and $M$ is a very large number.

Why does this work? Basically, the $z=0$ case handles the constraint $y_1 + y_2 + y_3 + y_4 = 0$ and the $z=1$ case handles the constraint $y_1 + y_2 + y_3 + y_4 \geq 2$.

More specifically,

• If $z = 0$ then the first constraint becomes $y_1 + y_2 + y_3 + y_4 \leq 0$, which, since the variables are binary, is equivalent to $y_1 + y_2 + y_3 + y_4 = 0$. The second constraint becomes $2 - y_1 - y_2 - y_3 - y_4 \leq M$, which is always satisfied.
• If $z=1$ then the second constraint becomes $y_1 + y_2 + y_3 + y_4 \geq 2$. The first becomes $y_1 + y_2 + y_3 + y_4 \leq M$, which is always satisfied.

So exactly one of $y_1 + y_2 + y_3 + y_4 = 0$ or $y_1 + y_2 + y_3 + y_4 \geq 2$ must be true, which is what you want.

-
Thank you! Much appreciated. –  icobes Mar 19 '11 at 21:55
@icobes: Just so you know, the approach I describe here is the general one for handling constraints in which exactly one of $f(x) \geq C$ and $f(x) \leq K$ must be true. –  Mike Spivey Mar 20 '11 at 5:06

You might get better responses if you explain further what it is that you are trying to do, and what you consider a 'constraint'. To me, any mathematical statement that limits the possible values of the $Y_i$'s can be called a constraint. So $$Y_1 + Y_2 + Y_3 + Y_4 = 0 \text{ or } Y_1 + Y_2 + Y_3 + Y_4 \geq 2$$ (which you seem to know you want to to express already) seems perfectly valid as a constraint on your system. Alternatively, you could express this more concisely as $$Y_1 + Y_2 + Y_3 + Y_4 \neq 1$$ if you're comfortable with writing down inequalities. (The sum's always going to be a nonnegative integer, so this constrains it to be either 0 or at least 2.)

As it stands, I am not sure why you are introducing Z and M.

-
I am trying to make a linear programming model and these models cannot have "or" or "and" in them... essentially we must represent everything through equations that the solving software will try and satisfy simultaneously. Thus, the first set would not work since the computer software would try and satisfy both of them at once (since we cannot use OR). Additionally, we can only have equal signs and inequalities so your second one wouldn't work. Is there any other way to model this? –  icobes Mar 19 '11 at 21:29