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 is accessed from here PDF or here PS.
Downloads for Lecture 2 is accessed from here PDF.
Questions on the network design problem is accessed from here PDF or here PS.
We present methodologies for solving Lagrangian dual problems, in
particular the classes of subgradient optimization and bundle
algorithms.
Literature: Lasdon Ch. 8.5-7(8).
Alternative: Andréasson, Evgrafov, and Patriksson Ch. 6.4.
Downloads for Lectures 3-4 is accessed from here
PDF.
Updated (080909) and complete downloads for Lectures 3 and 4 is accessed from
here
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; Andréasson, Evgrafov, and Patriksson Ch. 6.7.
Downloads for Lecture 5 is accessed from here
PDF.
Here is an updated (after the lecture 080910) version of Lecture 5
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);
Alternative: Andréasson, Evgrafov, and Patriksson Ch. 6.5.
The paper by Larsson, Patriksson, and Strömberg is found here in PDF format (reachable from Chalmers domain).
Downloads for Lecture 8 is accessed from here PDF.
The paper by Larsson and Patriksson is found here in PDF format (reachable from Chalmers domain).
Downloads for Lecture 9 is accessed from here
PDF.
Here is an updated (after the lecture 080923) version of Lecture 9
PDF.
The paper by Barnhart et al is found here PDF (reachable from Chalmers domain).
Downloads for Lecture 10 is accessed from here PDF.
Downloads for Lecture 12 (which also covers Branch-and-price) is accessed from here 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.)
Project description files updated 4 September 2008
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 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 25 September. On 30 September and 1 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 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.
The following update of the 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 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. 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.
All computations must be made on a linux computer in Mathematical Sciences student's lab.
The clock time limits for the respective problems and settings are given by:
(a) Counting from the initialization of the problem: 1 min and 3 min, respectively.
(b) Counting from the completion of the bundle code: 10 sec and 40 sec, respectively.
Three winners will be announced:
(I) The group that on average reaches the best feasible solutions within the fixed CPU time according to (a).
(II) The group that on average reaches the best feasible solutions within the fixed CPU time according to (b).
(III) The group that on shortest average time reaches a feasible solution with value less than or equal to 236 and 230, respectively.
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. NOTE: If the format problem is too difficult to handle then you may strike this problem.
On the report:
Provide
(1) a sufficiently good summary of the
heuristics that you first tested but threw away, and the reasons
why;
(2) same for the heuristic that you finally settled for,
including the final parameter settings;
(3) for each problem tested
with the final method - not only the competition ones - provide the
following information: primal objective values plotted against
iterations and/or CPU times, tables of best solutions found in the
literature and computed by yourselves, INCLUDING lower and upper
bounds, and - not the least important - a summary
explanation/interpretation of your results. [Why did your heuristic
work well on some problems and not on others?]
On the presentation:
Here is a latex template for producing nice slides for your oral presentation
LaTeX file!
Do not forget to hand over the final report to the examiner and your opponents well before the seminar!
Good Luck!