Order Solution

Problem 1:
Suppose we have 100 students to be divided into teams of 10 each. Each student is allowed to
list up to 5 other students that they do not want to work with. How can we form feasible teams
for the projects?
a) Formulate this as mathematical program (preferably with linear constraints) using the
variable definition “xst = 1 is student s is placed on team t, else 0” for all students s and
teams t.
b) Formulate this as a mathematical program (preferably with linear constraints) using the
variable definition “yss’ = 1 is student s is placed on the same team as student s’, else 0”
for all pairs of students s and s’.
c) Formulate this as a mathematical program (preferably with linear constraints) using the
variable definition “z
g = 1 if group g is chosen as a team, else 0” for all feasible groups of
students g.
d) Compare these formulations – which is the easiest to understand? Which has the most
variables? Constraints?

Problem 2:
As director of the Study Abroad Office, I am trying to match students with Study Abroad
opportunities. There are 100 students and 50 Study Abroad locations. At most 5 students can
attend any one location. Each of the students ranks their preference of locations, with one
being the best and 30 being the worst.
a) Formulate a mathematical program to find the best assignment of students to locations.
b) How could you modify the problem to ensure that at most 30 unique locations are
assigned?
Problem 3:
Suppose we have a set of students and a set of projects.
Each project has a minimum and maximum number of students it can take. Each student needs
a project.
Each project needs at least one student with good communication skills. Each project needs at
least one student with good programming skills.
Each student specifies their favorite project.
Write a mathematical program that maximizes the number of students who get their top choice.
Be sure in your solution to explicitly state the parameters, the variables, the objective, the
constraints, and the variable restrictions!

Problem 4:
Suppose we have a set of students and a set of projects.
NOT ALL PROJECTS HAVE TO BE STAFFED!
Each project THAT IS STAFFED has a minimum and maximum number of students it can take.
Each student needs a project.
Each project THAT IS STAFFED needs at least one student with good communication skills.
Each project THAT IS STAFFED needs at least one student with good programming skills.
Each student specifies their favorite project.
Add the constraint that at most P project topics can be assigned.
Write a mathematical program that maximizes the number of students who get their top choice.
Be sure in your solution to explicitly state the parameters, the variables, the objective, the
constraints, and the variable restrictions!
Problem 5:
Consider the following set of constraints:
a + 2b + 3c + 4d + 5e = 6
5a + 4b + 3c + 2d + 5e = 6
a, b, c, d, e > 0
Identify all basic solutions. Which of these are basic feasible solutions?