Hand-in exercise 3 in Linear and Combinatorial Optimization, VT1, 2008.

A group of students needs to determine a schedule for computer laboratory exercises. Each student has marked which occassions are not possible for her/him.
These constraints are given in a matrix c, where c_{ij} is 1 if lab time j is impossible for student i.

c=[...
0 0 0 0 0 0 0 0 0; ...
1 1 0 0 0 0 0 1 1; ...
1 1 0 1 1 1 0 1 1; ...
0 0 0 0 0 0 0 1 0; ...
1 1 0 1 0 1 1 0 0; ...
1 0 0 1 0 0 0 0 0; ...
0 0 1 1 1 1 0 0 0; ...
0 0 0 0 0 0 0 0 0; ...
0 1 0 0 1 0 0 0 0; ...
0 0 1 0 1 0 0 0 0; ...
1 1 0 1 1 1 1 1 1; ...
1 1 0 1 1 1 1 1 1; ...
0 0 0 0 0 0 0 0 0; ...
0 0 0 0 1 0 0 0 0; ...
1 1 0 1 1 1 0 1 0; ...
1 1 0 1 1 0 0 0 0; ...
0 0 1 1 0 1 0 0 0; ...
0 0 1 1 0 1 0 0 0; ...
1 1 0 1 1 1 0 1 1; ...
0 0 0 0 0 0 0 0 0; ...
0 0 0 0 0 0 0 0 0; ...
0 0 0 0 0 0 0 0 0; ...
0 0 1 1 1 1 1 0 0; ...
0 0 0 1 1 1 0 1 1; ...
0 0 0 1 1 1 1 1 0; ...
0 0 0 0 0 1 0 1 1; ...
0 0 0 0 0 0 0 0 0; ...
0 0 0 0 0 0 0 0 0; ...
0 0 0 0 0 0 0 0 0; ...
0 0 0 0 1 0 0 0 0; ...
0 0 0 0 0 0 1 1 1; ...
1 0 0 1 0 1 1 0 0; ...
1 1 1 0 0 0 0 0 0; ...
1 1 0 0 0 0 0 0 0; ...
0 0 0 0 1 1 1 1 1];

Task:

1. There are 12 computers in the class room (one per student). Only 3 out of the 9 lab times should be used. Formulate the problem as a combinatorial optimization problem. Try to find a reasonable objective function on your own. Describe the function as well as the domain of feasible solutions.

2. Sketch a solution method which would solve the problem even if the number of students or lab times would be large.

3. Solve the problem for the above case (with matrix c) using any method.

Present your solution by handing in a written report by Friday 22 February 2008. Send your solution to klasj@maths.lth.se. Please attach any matlab scripts if you are using Matlab.