Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.