- The course starts Tuesday the 16th of January 2018 at 08.00 in MVF23. Welcome!
- Downloads for Lecture 1
- Downloads for Lecture 2
- Downloads for Lecture 3
- Downloads for Workshop 5, Wednesday 24th of January. Be prepared to discuss these questions at the workshop.
- Downloads for Lecture 4
- 18-01-25: The course plan has been updated as indicated below. Check also the time-edit schedule. Note that the lecture tomorrow (180126) is moved to 15-17.
- Downloads for Lecture 6
- Extra downloads for Lecture 6: inconsistent optimization problems
- Downloads for Lecture 7
- Downloads for Lecture 8
- Updated lecture notes for Lecture 7 (180202; mainly notations in the figures)
- Updated lecture notes for Lecture 8 (180202; handouts)
- Additional updates of Lecture 8 (180202; corrections)
- Downloads for Lecture 9
- Downloads for Lecture 10
- Downloads for Lecture 11. Introduction to the second project
- During the workshop on Wednesday, February 14, we will discuss how to tackle the production scheduling models in the second project by the column generation principle. Prepare for this session by extracting the model to be solved and suggesting how to define the Dantzig-Wolfe decomposition for this model and try to characterize the (integer) master problem. Also, suggest what subproblems will have to be solved. Include pros and cons for various aspects of the suggested solution procedure.
- Downloads for Lecture 15. Benders' decomposition
- Downloads for Lecture 16
- The study material for the oral exam is now published under Requirements
- This page is created as a student support and contains course information, schedules, lecture notes, and project information etc. and will be continuously updated during the course.
Here are the
detailed course plan
Updated course plan 18-01-25
Updated course plan 18-02-02 (added lecture room)
- Links to more courses in Optimization at Chalmers and University of Gothenburg.
TeacherExaminer and lecturer is professor Ann-Brith Strömberg
Course aim and contentsThe course aim and contents are described at
Course requirements and examination
- To pass the course you must take active part in the two scheduled
workshops, and in the two course projects. The findings of your
projects are to be presented in the form of written reports as well as
orally during seminars. Each group must also act as
opponents/discussants on another group's projects, and each student
must take active part in all of these activities.
- Presence is mandatory at the two scheduled workshops as well as
at the two presentation sessions (see the detailed course plan).
- All handing in of programs and reports is made in the
"TMA521/MMA511 Large-scale optimization Spring 18".
- Project groups consist of two or one persons.
- In order to reach a better mark (i.e., 4, 5, or VG) than "pass"
(i.e., 3 or G) you can take an oral exam, based on the lecture
material of the course and the projects. A majority of the possible
topics that may be discussed during such an exam are gathered in the
study material that is found
In addition, you should be ready to discuss both of the course's projects.
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 (VG, respectively) questions. (A "question" refers to a chapter in the study material.)
- The book Optimization Theory for Large Systems by Leon S. Lasdon, Dover Publications 2002, ISBN: 9780486419992.
- Material on Lagrangean duality is also found in the book An Introduction to Continuous Optimization by N. Andréasson, A. Evgrafov, M. Patriksson, E. Gustavsson, Z. Nedělková, K. C. Sou, and M. Önnheim, Studentlitteratur 2016.
- Articles from scientific journals (see below in the lectures overview).
Overview of the lectures
Simple and hard problems
What distinguishes a simple optimization problem, or a difficult one? We will learn about some simple problems, such as linear programming and classes of network flow problems. We also study the related topics of matroid problems (and intersections of matroids) and greedy algorithms. Other examples of simple/hard problems are continuous/binary knapsack problems.
Lagrangian relaxation (four lectures, I–IV)
I: Review of Lagrangian duality for convex optimization problems, i.e., with a zero duality gap.
II: Methodologies for solving Lagrangian dual problems, in particular the class of subgradient optimization algorithms.
III: Specialization of Lagrangian duality for applications to integer linear optimization. In particular, we discuss the strength of different relaxations, and relate Lagrangian relaxation to continuous relaxations and the convexification of the original problem.
- Complementary material: Andréasson et al., Ch. 6.7
IV: Primal recovery concerns how to obtain an optimal solution to the primal problem using, e.g., a near-optimal dual solution. We present the use of ergodic sequences and so-called core problems.
- Larsson, Patriksson, and Strömberg (1999) (reachable from Chalmers domain)
- A further developed averaging strategy: Gustavsson, Patriksson, and Strömberg (2015)
- Generalization to inconsistent convex optimization problems: Önnheim, Gustavsson, Strömberg, Patriksson, and Larsson (2017)
- Recovery of primal solutions from dual subgradient methods for mixed binary linear programming: Aldenvik and Schierscher (2015)
- Large-scale binary linear optimization solved by dual subgradient optimization, primal ergodic sequences, and core problems: Juneberg (2001)
- Complementary material: Andréasson et al., Ch. 6.5
Workshop on discrete network design and Lagrangean relaxation
Presence is mandatory.
The material to be prepared to discuss can be downloaded from
"Latest news", above.
Column generation (three lectures, I–III)
Development of cutting plane methods, column generation, and Dantzig-Wolfe decomposition. Application to linear optimization problems. Extension of the Dantzig-Wolfe decomposition to integer linear optimization. Application to the classic cutting stock problem as well as its combination with the branch & bound method, known as branch & price.
Computational complexity (one lecture)
An introduction to complexity, with examples from our research on industrial maintenance planning.
Introduction of project 2 (one lecture)
The industrial research project behind the second course project is presented (lecture 11).
Technical discussions on Project 2
Presentation sessions (13–14)
Students' presentations of their project findings (Project 1)
Benders decomposition (one lecture)
The dual correspondance to Dantzig-Wolfe decomposition is a cutting plane method. While Dantzig-Wolfe decomposition does not extend to integer programming, the cutting plane method does, whence it is referred to as Benders decomposition. We derive it and discuss its applications.
Combining decomposition principles (one lecture)
Finally, for a basic problem in the field of facility location, we take a closer look at the workings of a combination of several of the decomposition methods treated in this course.
Presentation sessions (17–18)
Students' presentations of their project findings (Project 2)
Project 1You will investigate the use of Lagrangian relaxation on a VLSI design problem. You have access to codes in Matlab and C to perform data collection as well as to solve the Lagrangian subproblems and illustrate the solutions, but you must write the Lagrangian optimization code in Matlab yourself.
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.)
MSc thesis by Juneberg
- Article by Feo & Hochbaum
MSc thesis (2015) by
Pauline Aldenvik and Mirjam Schierscher
Ideas for utilizing ergodic sequences of subproblem solutions for finding good feasible (i.e., integer) solutions:
Recovery of primal solutions from dual subgradient methods for mixed binary linear programming; a branch-and-bound approach.
- The deadlines for handing in the programs and the complete report, as well as the dates for the oral presentations are specified in the detailed course plan above.
Project 2You will investigate the use of Danzig-Wolfe decomposition and column generation to solve a flexible job shop scheduling problem. AMPL model files and scripts as well as several data files are available (see below). Your task is to construct the column generation scheme and apply it to the instances in the .dat-files provided below.
- Project description
Karin Thörnblad's licentiate thesis
- Chapter 10 in the book Column Generation (Desaulniers, Desrosiers, Solomon, editors): Dantzig-Wolfe decomposition for job shop scheduling (2005) (reachable from Chalmers' domain)
- Chapter 11 in the book Column Generation (Desaulniers, Desrosiers, Solomon, editors): Applying column generation to machine scheduling (2005) (reachable from Chalmers' domain)
- AMPL-files for solving the engineer's model (version 2011): MTC3_v4_proj_course.zip
AMPL-files for solving the time-discrete model (version 2011):
- More data files (version 2015): Alla_datfiler_MTC6_v2.zip
- Chapters from the AMPL book
- AMPL CPLEX 12.2 Users Guide
- The AMPL homepage offers several example implementations of decomposition algorithms using AMPL-scripts at LOOPING AND TESTING 2