Introduction to Linear Optimization
Introduction to Linear Optimization
Winter semester 2022/2023 at the University of Wrocław.
The course is given jointly by:
Martin Böhm and
Jarosław Byrka.
Lecture 1 (MB+JB): Class structure, introduction to linear programs. Presentation slides.
Lecture 2 (MB): Modelling problems with integer and linear programs. Profit minimization for a bakery. Cutting standard-width paper rolls into requested thinner rolls [MG 2.7]. Maximum independent set as an ILP [MG 3.4]. Shortest path as an LP.
Lecture 3 (JB): Basics of convexity theory. Vertices are the same thing as basic feasible solutions.[Sch, Section 2]
Lecture 4 (JB): Duality, Farkas Lemma. Complementary slackness.
Lecture 5 (MB): The simplex method, unbounded case, exceptional case [MG 5.1-5.7].
Lecture 6 (MB): Analysis of the simplex method. Specifically, proof that the Bland rule does not lead to cycling [MG 5.8].
Lecture 7 (MB): Total unimodularity and its uses for proving that a polytope has all vertices integral. [Sch, Section 8] Flows in networks. Proof that max flow = min cut. [Lav] Ford-Fulkerson algorithm. [Sch, Section 4]
Lecture 8 (MB): The Dinitz algorithm for max flow as well as its O(n^3) variant by Malhotra, Kumar and Maheswari. [Sch, Section 4]. Second mandatory homework.
Lecture 9 (JB): Integrality of other polytopes (spanning tree polytope) [Salv 18]. Separation oracles.
Lecture 10 (JB): The ellipsoid method [Goe 7].
Lecture 11 (MB): Modelling LPs with a computer solver. Lecture recording, Jupyter notebook, PDF version. Third mandatory homework and its dataset. Its deadline is January 30 by email.
Lecture 12 (MB): Introduction to matching. Matching polytope for a bipartite graph. Complementary slackness conditions [Von 4].
Lecture 13 (MB): Primal-dual algorithm for minimum cost perfect matching in bipartite graphs. Blossom algorithm for maximum unweighted matching (sketch) [Salv 4].
Lecture 14 (MB): Minimum cost perfect matching in general graphs via primal-dual [Sch, Section 5]. Fourth mandatory homework. Its deadline is Monday, February 13.
Lecture 15 (MB): Review of the course and all its topics. Final handout in PDF and its source archive.
Exercise session one (PDF).
Exercise session four (PDF).
Exercise session five (PDF).
Exercise session six (PDF).
Exercise session seven (PDF).
Exercise session eleven (PDF).
Exercise session twelve (PDF).
[MG] Jiří Matoušek, Bernd Gärtner. Understanding and Using Linear Programming. Springer 2007 (https://link.springer.com/book/10.1007/978-3-540-30717-4). The book is also available as a PDF under this link (likely unofficially).
[Sch] Lecture notes of Alexander Schrijver (Available online at https://homepages.cwi.nl/~lex/files/dict.pdf).
[Lav] Mikhail Lavrov - Linear Programming course lecture notes. Available online at https://faculty.math.illinois.edu/~mlavrov/docs/482-fall-2019/lecture24.pdf .
[Salv] Mohammad R. Salavatipour - Topics in Algorithms and Combinatorial Optimization Lecture notes. Lecture 18 here: https://webdocs.cs.ualberta.ca/~mreza/courses/CombOpt09/lecture18.pdf and Lecture 4 here: https://webdocs.cs.ualberta.ca/~mreza/courses/CombOpt09/lecture4.pdf.
[Von] Jan Vondrak: Polyhedral techniques in combinatorial optimization. Lecture 4 here: https://theory.stanford.edu/~jvondrak/CS369P/lec4.pdf .
[Goe] Michel X. Goemans: Combinatorial Optimization Lecture Notes. Lecture 7 here: https://math.mit.edu/~goemans/18453S17/ellipsoid-notes.pdf
Linear optimization, or linear programming, is a study of encoding mathematical problems – from the very fundamental in computer science, such as flow and matching problems, to problems central to supply chain and logistics – as problems described by a set of linear equalities, where the quality of a solution is also measured by a linear function.
The centerpoint of linear optimization is the fact that efficient algorithms – in both theoretical and practical sense of the word – exist to find the optimal solution of such a linear system.
We can see the practical impact of linear optimization by the fact that early research into this field has been awarded the 1975 Nobel Memorial Prize in Economics. On the theoretical side, many advanced courses in algorithm design benefit from knowledge of linear programming, among others:
Approximation algorithms (Algorytmy aproksymacyjne, https://zapisy.ii.uni.wroc.pl/offer/algorytmy-aproksymacyjne_8/ )
Online algorithms (Algorytmy online, https://zapisy.ii.uni.wroc.pl/offer/algorytmy-online_16/)
Algorithmic game theory (https://zapisy.ii.uni.wroc.pl/offer/712-algorithmic-game-theory/)
Submodular optimization (Optymalizacja submodularna, https://zapisy.ii.uni.wroc.pl/offer/3160-optymalizacja-submodularna/ )
Scheduling theory (https://zapisy.ii.uni.wroc.pl/offer/3153-scheduling-theory/)
This course offers a thorough introduction to the theory of linear optimization, with a particular focus on both the mathematical background of the area as well as empowering the student to be able to model many computer science problems as linear systems, and solve such systems on a computer with the use of a linear programming solver.
The course is aimed at Bachelor-level (undergraduate) Computer Science students and above, and is appropriate for first-year Master-level students as well. A basic knowledge of linear algebra is expected.
The exercise sessions will consist of a combination of theoretical problem solving practice in class and practical modelling tasks to be solved with the help of a computer solver. The grade for the exercises will be determined by a set of several homework sheets throughout the semester. The course will be concluded with a final exam, which will be oral or written depending on the number of attending students.
The course will be taught completely in English.
Sample topics:
Introduction to linear programming and integer programming.
Modeling with linear and integer programs.
Convexity and its properties.
Hyperplanes, polytopes and polyhedra. Farkas lemma.
Duality in linear optimization.
Ellipsoid method: an algorithm for solving linear programs.
Solution methods for large LPs: separation oracles and column generation methods.
Network flows and their algorithms. Duality between network flows and graph cuts.
Integrality of selected combinatorial polytopes. Linear relaxations of integer programs.
Literature:
Jiří Matoušek, Bernd Gärtner. Understanding and Using Linear Programming. Springer 2007 (https://link.springer.com/book/10.1007/978-3-540-30717-4)
Lecture notes of Alexander Schrijver (in particular, Section 2 of https://homepages.cwi.nl/~lex/files/dict.pdf)