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
etc.
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.