Linear programming (LP) was introduced in the fourth decade of the 20th century and was initially regarded as a branch of optimization theory. Quite rapidly LP had become a popular method for solving economic and planning problems with variables ranging over the set of reals. In certain cases it turned out possible to adapt LP to discrete problems as well. However, a systematic study of LP approaches in combinatorics had started only a few decades later. This area was pioneered by Jack Edmonds, whose research in polyhedral combinatorics vastly improved our knowledge of connections between combinatorial and linear problems.

The course has multiple goals.

First, we shall study the very foundations of LP including linear separability and duality. We shall discuss the ellipsoid method and use it to derive a polynomial-time solvability of general LP problems.

Second, a great deal of attention will be payed to connections between LP and discrete programming, combinatorics, and optimization. The key notions here are that of total unimodularity and total dual integrality. We shall construct examples of such good linear programs for a large number of combinatorial problems.

A survey of some more recent techniques will also be given. Submodularity and its connection to matroids will be discussed. We shall learn basic facts on submodular flows. The latter powerful tool will allow us to derive numerous consequences. Some of them are pretty elementary (like the theorems of Ford-Fulkerson or Dilworth). Others are more involved (like Nash-Williams' theorem that claims existence of a k-connected directed orientation of every 2k-connected undirected graph).

Finally, the elements of semi-definite programming (SDP) and its use in approximate algorithms will be covered. We shall consider MAX-CUT, which is a famous for its SDP-based approximation.