• Here is the bipartite matching example we discussed in class.

• This file can be used to find all of the vertices (solutions). Run with

  lrs < bipartite.ine

• It turns out there are only two vertices, both integer.

    1  1  0  0  1  1  1  0 
    1  0  1  1  0  1  0  1

• Solving with a uniform objective, and choosing --interior with glpsol, we get the non-integer optimal solution

    x[1,A].val = 0.5
    x[1,B].val = 0.5
    x[2,A].val = 0.5
    x[2,D].val = 0.5
    x[3,C].val = 1.0
    x[4,B].val = 0.5
    x[4,D].val = 0.5

• This can be visualized as dot and pdf.

In CS3997 this year, I have decided to have "debates" instead of presentations. This means that I need to make sure that each student has has exactly one topic, and every topic is assigned to an even number of students.

Another constraint is that I asked the students to list in order their top 3 preferences. I wanted to maximize (within reason) "student happiness", so I give weight 4 for their first choice, 2 for the second, and 1 for their third.

Finally, the students are numbered 1...26 in the order they sent me their preferences. I decided to enforce "first-come first-serve" in the objective function, so the happiness of student 1 has more weight than student 26. How much more is a bit of a subjective choice.

If you don't want to look at the solution yet, the students preferences are available separately. 'happy[i,j]' measures how happy student i is being assigned topic j

Almost the real solution is available. In actuallity, I first solved the problem for the first 18 students (so they didn't have to wait), and use the following

 printf { i in students, j in topics : x[i,j]=1 } "s.t. fix_%d_%d: x[%d,%d]=1;\n",i,j,i,j; 

to print out some constraints, which I then cut and past into the model, and resolved a week or so later when I had all of the data.