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 19 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 20 September. On 23 September there will be discussion sessions on Project 1. Each gruop should then give an oral presentation of their solution of the project assignment.
The AMPL homepage offers several examples of implementations of decomposition algorithms using AMPL-scripts at LOOPING AND TESTING 2
Important dates and deadlines (updated 5 October 2011):