Introduction to Linear and Discrete Optimization (ADM1)

I gave this course in the winter term 2021/2022 at TU Berlin. Its goal is to learn how to formulate optimization problems as linear or integer programs, to understand the methods used to solve those problems, and to analyze their complexity in a mathematically rigorous way.

List of addressed topics:

• Basics of Linear Programming (LP)
• Simplex Method
• LP Duality
• Minimum Spanning Trees & Shortest Path
• Maximum Flow Problem / Min-cost Flow Problem
• Bipartite Matchings
• Complexity of Linear Programming
• Large-Scale Linear Programming'

Slides:

This slides are largely based on a former version prepared by Prof. Martin Skutella and Prof. Max Klimm.

• Chapter 1: Introduction
• Chapter 2: Linear Programming Basics
• Chapter 3: Geometry of Linear Programming
• Chapter 4: The Simplex Method
• Chapter 5: Implementating the Simplex Algorithm
• Chapter 6: Anticycling and Phase I
• Chapter 7: Duality
• Chapter 8: Optimal Trees and Paths
• Chapter 9: Efficiency of Algorithms
• Chapter 10: Maximum Flows
• Chapter 11: Bipartite Matchings
• Chapter 12: Minimum-cost flows
• Chapter 13: Complexity of Linear Programming
• Chapter 14: Representation of Polyhedra
• Chapter 15: Large-scale Linear Programmming
• Chapter 16: Sensitivity Analysis