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 one by means of "polynomial transformations". We take a closer look at the discrete network design problem, and discuss its properties. Literature: Notes.
For a basic problem in the field of facility location, we take a closer look at the workings of a Lagrangian relaxation method in the literature. Literature: Barcelo.
Downloads for Lecture 1 (updated 2005!): PS or PDF-format. 4-page format is found here: PS or PDF.
On the network design problem: PS or PDF-format.
Downloads for Lecture 2: PS or PDF-format. 4-page format is found here: PS or PDF.
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.
Additional download: Lagrange duality chapter from new book: PS or PDF-format. 2-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 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 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: 22 April. 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?): 29 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.
IMPORTANT NOTE! The above code works with so-called "dense" matrix algebra, which means that the matrix A is stored in dense form. This is ok when the size of the problem is small but for huge problems the matrix-vector multiplications involved in the algorithms to be used would take forever. There is a "sparse" form of the storage of the matrix and of the computations that take into account that the matrix A normally, for huge problems, contains perhaps 5 % or less non-zero elements. In order to work with the larger files you should also download the following tar-file and extract the corresponding programs in a special sub-directory for sparse computations: Sparse Bundle.
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 second largest (in the size n + m) of the non-rail problems you have encountered!
Bonus problem! You are also requested to run your solver, with the same settings, on the problem scpcyc10.txt, whose input format is given here. Why? Because it is a problem specifically constructed to give primal heuristics a hard time, it is truly large, and I would like to see how your solver copes.
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: 23 May. Deadline for the completion of the final test and the writing of the report: 31 May.