We present methodologies for solving Lagrangian dual problems, in
particular the classes of subgradient optimization and bundle
For applications to integer programming, we specialize Lagrangian
duality. In particular, we discuss the strength of different
relaxations relate Lagrangian relaxation to continuous relaxations
and the convexification of the original problem.
The exam will be arranged thus: Apart from questions on the projects, and any side questions that may be relevant, the main part of the exam will consist of questions from the above study material. A selection will be made at random among them, making sure that the three (3) questions selected will cover the course material well enough and also include both grade 4 and 5 questions. (A "question" refers to a chapter in the study material.)
Important dates: Deadline for handing in the Matlab programs and their descriptions is 21 September. Deadline for the complete report, with Matlab-supported graphics of the best feasible solution for each problem, convergence charts for the subgradient algorithm (together with a discussion on your experience with using it!), and discussions on your feasibility heuristics, its complexity, and your experience with it (for example, did it always manage to find a feasible solution?) is 24 September. On 30 September and 2 October, there will be discussion sessions on Project 1. Each gruop should then give an oral presentation of their solution of the project assignment.
Based on the codes available, you are to code your own method in which you can optimally choose parameters based on a set of test problems. Recommended means are to use the C code to generate good Lagrangian dual solutions on file, import them to Matlab together with the problem file, and then construct your heuristic entirely within Matlab. (The algorithm does of course not have to be constructed based on the Lagrangian dual solution!) If you are familiar with Cplex and C, you can instead add the corresponding lines of code to the C program given.
The following sparse bundle optimization program should be used: New Sparse Bundle (including documentation).
For a file bla.tar, do 'tar xvf bla.tar' and you should get a subdirectory called Bla. Use the instructions in the documentation to find everything you need. Finally, use the following link to find further test problems: Beasley's OR-library on the set covering problem. Please also browse the web for further problems that you may test.
Note that unless you have set the path for the programs 'bundle' and 'sg', you must run them at their respective location using the commands './bundle' and './sg', otherwise unix will not find them.
Here are the the competition instructions and THE INSTANCES
Do not forget to hand over the final report to the examiner and your opponents well before the seminar!