For more difficult problems, we review classic relaxation methods. We investigate how to prove that a problem is difficult by relating it to a known difficult by means of "polynomial transformations". We take a closer look at the discrete network design problem, and discuss its properties. Literature: Notes.
Downloads for Lecture 1: PS or PDF-format. 4-page format is found here: PS or PDF.
Downloads for Lecture 2: PS or PDF-format. 4-page format is found here: PS or PDF.
We review Lagrangian duality for problems without a duality gap. Literature: Notes.
We present methodologies for solving Lagrangian dual problems, in particular the classes of subgradient optimization and bundle algorithms. Literature: Notes.
Downloads for Lecture 2-3: PS or PDF-format. 4-page format is found here: PS or PDF.
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. Literature: Notes.
Downloads for Lecture 3-4: PS or PDF-format. 4-page format is found here: PS or PDF.
We discuss the topic of primal recovery, that is, how to obtain an optimal solution to the primal problem. We discuss the use of Lagrangian heuristics as well as the use of ergodic sequences and master problems, thereby touching already now the subject of price decomposition, Dantzig-Wolfe decomposition and column generation. Literature: Notes, Larsson, Patriksson, and Strömberg (1999).
Downloads for Lecture 4-5: The paper by Larsson, Patriksson, and Strömberg is found here in PDF format.
Downloads for Lecture 5: PS or PDF-format. 4-page format is found here: PS or PDF. Warning! The PS files are big!
Downloads for Lecture 5: The paper by Larsson and Patriksson is found here in PDF format.
Downloads for Lecture 8-10: PS or PDF-format. 4-page format is found here: PS or PDF.
The project description is found here: Swedish PS, Swedish PDF-format, or English PS, English PDF-format.
The problem files are here: gsp.c, sph.c, visagrid.m, p6.m, p10.m, p11.m. (The file gsp.c should be compiled in Matlab ("mex gsp.c") in order to create the gsp command.)
Important dates: Deadline for the Matlab program and its description: 31 March. Deadline for complete LaTeX-based 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?): 23 April.
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 competion then is as follows: Once all groups have finished coding and adjusting their algorithms, a small set of new test problems shall be solved with the current parameter settings fixed. Two winners will be announced: the group that on average reaches the best solutions within a fixed CPU time, and the group that on average reaches the final solution the quickest, under a solution quality constraint.
The master's thesis describing the C code is found here: PDF-format.
The source code and data files used in the thesis are found in the following four tar-files: Bundle, Examples, Hidden, and Subgradient. For a file bla.tar, do 'tar xvf bla.tar' and you should get a subdirectory called Bla. Use the instructions in the thesis to find everything you need; look especially at Section 5 (5.4.1, 5.5 in particular), and the numerical results found in Appendix D. Finally, use the following link to find further test problems: Beasley's OR-library on the set covering problem.
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.
The TRULY final problem to be solved is the problem scpcyc10.txt, whose input format is given here. There are two clock time limits: (a) Counting from the initialization of the problem: 1 hour. (b) Counting from the completion of the (first) run of the bundle code: 15 minutes.
Important dates: Deadline for the construction and initial test of your algorithm on the test problems given in Examples data set: 14 May. Deadline for the completion of the final test and the writing of the report: 28 May.
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.)
The examination will take place during week 36, that is, between Monday the 30th of August and Friday the 3rd of September. It is up to you to ask for a specific date and time, and we will arrange it together. You will be given three questions of varying difficulty and spanning most of the course material, but the exact choice of questions will be probabilistic. One of the questions will be of grade 3 type, one of grade 4 and one of grade 5. If you do well on the first and second, you will get grade 4, and if you also do well on the third one then you will be given the grade 5. The whole process, for a given student, must be over in three hours, including self-study of the questions in isolation, and the oral discussion.