0

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!

Thanks.

Yuval Filmus
  • 57,157
icobes
  • 1,109
  • 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. – joriki Mar 20 '11 at 07:09
  • @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. – Mike Spivey Mar 20 '11 at 22:37

1 Answers1

1

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

Yuval Filmus
  • 57,157