I need to make a constraint for the following condition:

Student 1 can only be on the team if students 2, 3, 4, and 5 are also on the team.

I'm not sure how to model this using equations. The equations must not have "and", "or", or "not equal to" signs in them. These equations are likely going to involve an M term in them (where M represents an arbitrarily large number).

I have defined binary variable $Y_i$ to equal 1 if student $i$ is chosen on the team and 0 otherwise.

Any help making the equations would be appreciated!


  • $\begingroup$ When you encode true and false by $1$ and $0$, you can encode logical operations as arithmetical operations using $a\cdot b$ for logical AND and $1-(1-a)\cdot(1-b)=a+b-ab$ for logical OR. $\endgroup$ – joriki Mar 20 '11 at 7:09
  • $\begingroup$ @joriki: You can do that, but then the nonlinear $ab$ term means that you don't have a linear integer program anymore. OP doesn't mention it specifically, but all the constraints do need to be linear here in order for the underlying algorithm to work. $\endgroup$ – Mike Spivey Mar 20 '11 at 22:37

Use $4Y_1 \leq Y_2 + Y_3 + Y_4 + Y_5$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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