The department chair intends to assign classes to 3 professors to teach. There are 6 classes in total, so each professor gets assigned 2 classes each. Each professor ranks the classes that they want in order of preference (1-6, with 6 being most desired). This preference also assigns a score to each class. The department chair then chooses to assign the courses to the professors. If he assigns class xn to professor A then the chair gets the number that the professor scored that class as. He does this until each professor has two classes each. The chair wants to maximize his score. What method should the chair use to assign the classes?
example: Courses: x1 x2 x3 x4 x5 x6
Professor A ranking: 1,3,4,5,6,2
Professor B ranking: 2,3,5,1,6,4
Professor C ranking: 5,6,4,3,2,1
So if chair assigns class x1->A, x2->A,x3->b, x4->b, x5->c, x6->c then he would get a score of 1+3+5+1+2+1=12. Obviously this is not optimal but this is a feasible solution.
Using branch-and-bound method can obtain an optimal solution. I've read how to set up branch-and-bound linear equations but I'm a bit unsure how to do it in this particular case. Can someone perhaps give me a lead that could help me set it up?
First you have to define the variables
$x_{ij}=\begin{cases} 1, \texttt{if class i is assigned to professor j } \\ 0, \texttt{else} \end{cases}$
Constraint 1: One professor is assigned to exact two classes
$\sum_{i=1}^6 x_{ij}=2 \quad \forall j\in \{1,2,3 \}$
Constraint 2: One class is assigned to exact one professor
$\sum_{j=1}^3 x_{ij}=1 \quad \forall i\in \{1,2,3,4,5,6 \}$
Let be $s_{ij}$ the score of class $i$ scored by professor $j$.
Then the objective function is
$\min \sum_{i=1}^6 \sum_{j=1}^3 s_{ij} \cdot x_{ij}$
Now you can apply branch & bound. You should first solve the problem not by using binary variables, but using $x,y \geq 0$