TMA521/MMA511, Large-scale optimization, 2017/18

Latest news

General information

Teacher

Examiner and lecturer is professor Ann-Brith Strömberg

Course aim and contents

The course aim and contents are described at Chalmers student portal and at GU's homepage

Course requirements and examination

  1. 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.

  2. Presence is mandatory at the two scheduled workshops as well as at the two presentation sessions (see the detailed course plan).

  3. All handing in of programs and reports is made in the PingPong event "TMA521/MMA511 Large-scale optimization Spring 18".

  4. Project groups consist of two or one persons.

  5. 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

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

Lagrangian relaxation (four lectures, I–IV)

I: Review of Lagrangian duality for convex optimization problems, i.e., with a zero duality gap.

Literature

II: Methodologies for solving Lagrangian dual problems, in particular the class of subgradient optimization algorithms.

Literature

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

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.

Literature

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.

Literature

Computational complexity (one lecture)

An introduction to complexity, with examples from our research on industrial maintenance planning.

Literature

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 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

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

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 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.