Introduction to Linear Optimization
Introduction to Linear Optimization
Winter semester 2023/2024 at the University of Wrocław.
Lecture 1: Class structure, introduction to linear programs. Presentation slides. handout.
Lecture 2: 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. Handout.
Lecture 3: Basics of convexity theory. Handout.
Lecture 4: Polytopes, polyhedra, vertices, basic feasible solutions. Handout.
Lecture 5: The simplex method, unbounded case, exceptional case [MG 5.1-5.7]. Handout.
Lecture 6: Duality [MG 6]. Handout.
Lecture 7: Total unimodularity and its uses for proving that a polytope has all vertices integral. [Sch, Section 8] Max Flow Min Cut theorem. [Lav]. Handout not yet available, homework sheet.
Lecture 8: Combinatorial algorithms for flows in networks -- Ford-Fulkerson, Dinitz as well as its O(n^3) variant by Malhotra, Kumar and Maheswari [Sch, Section 4]. Handout.
Lecture 9: Integrality of the spanning tree polytope via the uncrossing technique. Handout.
Lecture 10: Modelling LPs with a computer solver. Lecture recording, Jupyter notebook, PDF version.
Lecture 11: Complementary slackness conditions, use of complementarity in Set Cover (dual rounding, primal-dual approximation). Handout.
Lecture 12: Introduction to matchings, alternating paths and alternating forests for maximum unweighted matching. [Von] Recording part 1. Primal-dual algorithm for minimum cost perfect matching in bipartite graphs.[Salv 4]. Recording part 2. Handout.
Lecture 13: Blossom algorithm for maximum unweighted matching [Salv 4]. Minimum cost perfect matching polytope for general graphs (formulation, dual). Minimum cost perfect matching in general graphs via primal-dual (sketch) [Sch, Section 5]. Handout.
Lecture 14: Ellipsoid method [Goe]. Separation oracles [Goe, Sve]. Handout.
Exercises are included in the lecture handout.
There will be 4 mandatory homework sheets. The first is to be released soon.
Mandatory homework 1, deadline: November 29, 12:15.
Mandatory homework 2, deadline January 3, 12:15. Please only submit electronically.
Mandatory homework 3+4, deadline January 31, 12:15. Please only submit electronically. Dataset.
[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. Original URL currently unavailable, a mirror is hosted at https://web.archive.org/web/20230815204709/https://faculty.math.illinois.edu/~mlavrov/docs/482-fall-2019/lecture24.pdf . Originally 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
[Sve] Ola Svensson: Approximation Algorithms and Hardness of Approximation Lecture Notes, Lecture 9 and 10. https://theory.epfl.ch/osven/courses/Approx13/Notes/lecture9and10.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)