Contents

General information
Teachers
Course evaluation
Course requirements and examination
Literature
Overview of the lectures
Project 1
Project 2
Workshop material
List of published lectures

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.

The course schedule is in TimeEdit
Updated version of the course plan (191203)
Updated version of the course plan (191120)
The detailed course plan, including deadlines and presentation dates
The course aim and contents are described at Chalmers student portal and at GU's homepage

Back to the top

Teachers

Examiner, main lecturer, and course responsible: Professor Ann-Brith Strömberg
Teaching assistant and lecturer: PhD student Edvin Åblad
Teacher: Professor Michael Patriksson

Back to the top

Course evaluation

Useful information about the course evaluation process and your role in the same is found on the Student portal.

The student representatives are the following:

Carl Blomgren (MPENM)
Frida Eriksson (MPENM)
Yinfan Hu (MPSCM)
Viktor Ingemarsson (TKMAS)

The mid-course evaluation meeting will take place on Monday, December 2: Notes from the meeting.

Back to the top

Course requirements and examination

In order to pass the course, the student should hand in two project reports (coauthored with another student), hand in a collaboration report for each of the two projects, hold one oral project presentation (with another student), oppose on one project presentation, and take active part in two workshop sessions.
Presence is mandatory at one occasion of each of the two scheduled workshops as well as at one occasion of each of the two presentation sessions (the specific hours are in the detailed course plan).
The findings of your project work are to be presented in the form of two written reports. Each group shall present the findings of one of the projects at a seminar and shall act as opponents/discussants on another groups presentation (of the other project). Each student must take active part in all of these activities.
All handing in of programs and reports are done in Canvas.
Project groups consist of two students.
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 this study material. In addition, you should be ready to discuss both of the course's projects.

Back to the top

Literature

The compendium "Lagrangean duals and subgradient methods for linear and mixed-binary linear optimization", by Ann-Brith Strömberg (2019)
The book chapter "A primer in column generation" by Desrosiers and Lübbecke (2005) (This pdf from Springer is reachable from Chalmers domain)
Articles from scientific journals and book chapters (see below in the lectures overview)

Back to the top

Overview of the lectures

Simple and hard problems (one lecture)

What distinguishes a simple optimization problem, or a difficult one? We will learn about some simple problems, such as linear optimization 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

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)

Lagrangean relaxation (five lectures, I–V)

I: Lagrangean duality, polyhedral descriptions, and optimality conditions for linear optimization problems

Literature: Strömberg (2019), Sections 1–3

II–III: Lagrangean dualization of mixed-binary linear optimization and its convexified counterpart. Conditions for optimality and near-optimality.

Literature: Strömberg (2019), Section 4

IV: Subgradient optimization methods for solving the Lagrangean dual problem and ergodic convergence of primal solutions to the convexified primal problem

Literature: Strömberg (2019), Section 5

V: Recovery of (near-)optimal solutions to the primal mixed-binary optimization problem by the use of dual sequences, near-optimal dual solutions, Lagrangean heuristics, and core problems

Literature: Strömberg (2019), Section 6

Complementary literature on Lagrangean duality and subgradient methods

- Larsson, Patriksson, and Strömberg (1999) (reachable from Chalmers domain)
- A further developed averaging strategy: Gustavsson, Patriksson, and Strömberg (2015)
- On global optimality conditions for discrete optimization: Larsson and Patriksson (2006)
- 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)
- Generalization to inconsistent convex optimization problems: Önnheim, Gustavsson, Strömberg, Patriksson, and Larsson (2017)

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–and–bound method, known as branch–and–price.

Literature: "A primer in column generation" by Desrosiers and Lübbecke (2005) (reachable from Chalmers domain)

Complementary literature on column generation

- "Branch-and-price: Column generation for solving huge integer programs" by Barnhart et al. (1998) (reachable from Chalmers domain)

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.

Literature: Excerpt from "Optimization Theory for Large Systems" (L. S. Lasdon, Dover, 2011) (handed out; paper copies are found in a folder outside Ann-Brith's office)

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): "Computational results from a new Lagrangean relaxation algorithm for the capacitated plant location problem" (reachable from Chalmers domain)

Back to the top

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 Lagrangean subproblems and illustrate the solutions, but you must write the code for subgradient optimization, computation of ergodic sequences, and heuristic algorithms in Matlab yourself.

Project description: Projekt_1_Large_Scale_Optimization.pdf
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.)
Article by Feo & Hochbaum (1986) (describes the VLSI design problem)
MSc thesis by Juneberg (2001) (includes ideas for adaption of step length parameters in subgradient optimization)
MSc thesis (2015) by Pauline Aldenvik and Mirjam Schierscher (includes ideas for utilizing ergodic sequences of subproblem solutions for finding good feasible (i.e., integer/binary) solutions)
The deadlines for handing in the programs and the complete report, as well as the dates for the oral presentations/opposition are specified in the detailed course plan above.

Back to the top

Project 2

You 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 et al., editors): Dantzig-Wolfe decomposition for job shop scheduling (2005) (reachable from Chalmers' domain)
Chapter 11 in the book Column Generation (Desaulniers et al., 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): 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 AMPL-scripts at LOOPING AND TESTING 2

Time limited student licenses for AMPL and several MILP solvers to install on you own computer are available via this link to AMPL licenses for download. Note that these licenses are allowed to be used only within this course. Note also that the teachers cannot provide any support for the installation of these licences.

Back to the top

Workshop material

Questions to be discussed during Workshop 1: Network_Design_Workshop_Questions.pdf
Updated version (changes marked in red): Network_Design_Workshop_Questions_v.191112.pdf

Back to the top

List of published lectures

Back to the top