Introduction to Linear Optimization

Spring semester 2025 at the University of Wrocław.

Lecture 1: Class structure, introduction to linear programs. 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: Affine independence, basics of convexity theory. Caratheodory theorem. 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.
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: Spanning tree polytope and the uncrossing lemma. [Sve]. Handout.
Lecture 10: Modelling LPs with a computer solver. Lecture recording (from previous years), 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] Primal-dual algorithm for minimum cost perfect matching in bipartite graphs.[Salv 4]. Exercises for next week will happen live, no (non-mandatory) homework was assigned. 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]. Exercises for next week will happen live, no (non-mandatory) homework was assigned.
Lecture 14: The ellipsoid method [Goe], separation oracles [Sve]. Handout.

Exercise session

• The exercise session will utilize a hybrid format. Half of the exercises are included in the lecture handout, and half will be shown at the exercise sessiond and solved live. 

• There will be 2 mandatory homework sheets.

• Homework 1. Deadline: May 20, 14:15.

• Homework 2. Deadline: June 18, 23:59. Please only submit electronically. Dataset.

Exercise session passing criteria: 

1. At least 3 exercises presented in front of the class, each in a different session.

2. At least 50% of overall points from the mandatory homework sheets.

3. At least 50% of points from the midterm test.

4. All extra exercises presented in front of the class which are not counted as part of 1. will be converted into extra points for the mandatory tasks.

5. Attendance at the exercise session each week is not mandatory, aside from the requirements above.

Literature

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

Syllabus

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)