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:
* Numerical optimization (https://zapisy.ii.uni.wroc.pl/offer/736-numerical-optimization/)
* 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 Shrijver (in particular, Section 2 of https://homepages.cwi.nl/~lex/files/dict.pdf)
