Company:

Computer Science club at POMI RAS

The Linear Programming (LP) arose in the forties the last century as one of sections of the theory of optimization. Quickly enough it became a popular method for solving of tasks of economy and planning in which variables accept material values. In some cases it was also possible to adapt LP and for discrete tasks, but systematic studying of the LP annexes to combination theory began some decades later. One of pioneers in this area, undoubtedly, is Jack Edmonds whose works on polyhedral combination theory considerably expanded our knowledge about communication of combinatory and linear problems.

This rate pursues several aims.

First, we will get acquainted with the basic concepts of LP, we will study theorems of separability, linear duality and we will discuss polynomial resolvability of a task of LP using a method of ellipsoids. Secondly, from the very beginning much attention will be paid to communication of LP with the theory of integer programming, combination theory and optimization. We will consider concepts of total unimodularity and a total dual tselochislennost of linear programs and also we will find out how to write similar "good" programs for a large number of combinatory tasks.

It is aware it is supposed to give the overview of the modern directions of polyhedral combination theory. We will discuss a concept of submodularity and its communication with the theory of matroid. As an example the task about a submodular flow will be sorted, and on its basis the numerous investigations as absolutely elementary (like Ford-Falkerson or Dilvort's theorem), and more informative are received (for example, Nash-Williams's theorem of presence of the k-coherent directed orientation at any 2k-coherent undirected graph). At last, basic elements of the semi-definite programming (SDP) and its annexes to approximate algorithms will be briefly stated (for example, a task about the maximum section).

***