Algorithm Design Techniques     Fall 2009

COMP-360              Assignment 4          Due: Mon November 9, 5pm

Late assignments, -10% day
Please leave assignments in the drop off box, Trottier 3rd floor.
If you work closely with someone else, indicate the person's name(s) on your homework.
The final write-up of each assignment must, however, be your own work.

Questions 2,3 from the handout
lp_handout.pdf in the hidden folder
For questions 1,4 each student must submit a different solution.

1. In the weighted bipartite matching problem you have an n by n complete bipartite graph, and a weight on each edge (positive or negative).
Your goal is to find the perfect matching with maximum total weight. Formulate this as an integer linear program.
Construct an integer program of this type with n=6, using random weights on the edges.
Solve the problem using lp_solve as an integer linear program, and as an ordinary linear program.
Compare the answers.

2. Handout, Problem 7.12
3. Handout, Problem 7.16. Solve the problem using lp_solve, and verify the solution using the dual variables.
4. Here is a chance to design your ideal schedule.
Choose about 15 of your favourite McGill courses that will be given in the winter, and assign a score of up to 100(best) to each course.
(Forget about prerequisites, etc. just pick any courses you like.)
Now the goal is to choose 5 courses from these that do not overlap timewise, and have maximum total score.
Add at least four constraints to the problem, such as these:
(a) No course on Friday morning (Thursday is pub night)
(b) No three consecutive courses
(c) No more than three courses on any given day
(d) At least two courses on Monday,
(e) No more than 2 courses in the Arts faculty
Formulate this as an integer LP and use lp_solve to find the optimum solution.
If you get no feasible solution, you need to add some more courses, or relax some of the constraints.
Also solve the problem as an LP (ie. do not require an integer solution) and compare with the integer optimum solution.

Note on how to verify an LP solution using the dual:
If you give lp_solve the S4 option it prints a dual solution.
Now you can proceed in either of  two ways:
a) verify that it is in fact a dual solution by checking the dual constraints, then check that by = cx (primal solution)
b) directly multiply the primal constraints by the corresponding dual variables, sum them up, and show this bounds the primal objective function.