Introduction to Linear Optimization

Winter semester 2023/2024 at the University of Wrocław.

Lecture content


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

Lecture 14: Ellipsoid method [Goe]. Separation oracles [Goe, Sve]. Handout.

Exercise session

Literature

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:

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:

Literature: