Latest news
 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
 180125: The course plan has been updated as indicated below. Check also the timeedit schedule. Note that the lecture tomorrow (180126) is moved to 1517.
 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 DantzigWolfe 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
General information
 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
timeedit schedule
and the
detailed course plan
Updated course plan 180125
Updated course plan 180202 (added lecture room)  Links to more courses in Optimization at Chalmers and University of Gothenburg.
Teacher
Examiner and lecturer is professor AnnBrith StrömbergCourse aim and contents
The course aim and contents are described atCourse 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
PingPong event
"TMA521/MMA511 Largescale 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
here.
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.)
Course literature
 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.
Literature
 Excerpt from Wolsey: Integer Programming, 1998 (handed out);
 Excerpt from Lawler: Combinatorial Optimization: Networks and Matroids, 1976 (handed out);
 Chapter 2.1–2.2 from the book Knapsack problems—Algorithms and computer implementations by Martello and Toth.
Lagrangian relaxation (four lectures, I–IV)
I: Review of Lagrangian duality for convex optimization problems, i.e., with a zero duality gap.
Literature
 Lasdon Ch. 8.1–4
 Alternative: Andréasson et al., Ch. 6.1–3
II: Methodologies for solving Lagrangian dual problems, in particular the class of subgradient optimization algorithms.
Literature
 Lasdon Ch. 8.5–7(8)
 Alternative: Andréasson et al., Ch. 6.4
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.
Literature
 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 nearoptimal dual solution. We present the use of ergodic sequences and socalled core problems.
Literature
 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)
 Largescale 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 DantzigWolfe decomposition. Application to linear optimization problems. Extension of the DantzigWolfe 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.
Literature
 Lasdon Ch. 3 & 4.1
 "A primer in column generation" by Desrosiers and Lübbecke (2005) (reachable from Chalmers domain)
 "Branchandprice: Column generation for solving huge integer programs" by Barnhart et al (1998) (reachable from Chalmers domain)
Computational complexity (one lecture)
An introduction to complexity, with examples from our research on industrial maintenance planning.
Literature
 The opportunistic replacement problem: Almgren, Andréasson, Patriksson, Strömberg, Wojciechowski, and Önnheim (2012) (reachable from Chalmers domain).
Introduction of project 2 (one lecture)
The industrial research project behind the second course project is presented (lecture 11).
Workshop (12)
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 DantzigWolfe decomposition is a cutting plane method. While DantzigWolfe 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.
Literature
 Lasdon Ch. 7.3.
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.
Literature
 Barcelo, Fernandez, and Jörnsten (1991) (reachable from Chalmers domain).
Presentation sessions (17–18)
Students' presentations of their project findings (Project 2)
Project 1
You 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.
Project description

Problem files
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 branchandbound 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 2
You will investigate the use of DanzigWolfe 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 .datfiles provided below. Project description

Karin Thörnblad's licentiate thesis
 Chapter 10 in the book Column Generation (Desaulniers, Desrosiers, Solomon, editors): DantzigWolfe 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)
 AMPLfiles for solving the engineer's model (version 2011): MTC3_v4_proj_course.zip

AMPLfiles for solving the timediscrete model (version 2011):
MTC6_v2_proj_course.zip
 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 AMPLscripts at LOOPING AND TESTING 2