1. LP vs ILP: P vs NPh
1.1 Засунем ILP задачу в LP-солвер
1.2 Вариант 1: получилось целое решение. Def целый полиэдр.
1.3 Вариант 2: получилось вещественное решение, попробуем округлить
1.3.1 пример с VC 2-opt
1.3.2 пример с трегуольником
1.3.3 оцениваем округление (2-opt)
1.3.4 понятие integrality gap

2. Возвращаемся к целым полиэдрам.
2.1 Строим ILP для паросочетания
2.2 нецелый пример: треугольник
2.3 факты: полиэдр целый iff граф двудольный
2.4 cutting planes: добавляем условия, чтобы вырезать лишнее (proofless)
2.5 Дальнейшная цель: показать целочисленность в двудольном случае

3. Totally Unimodular
3.1 Определение
3.2 Утв1: {x | Ax <= b} целый forall b если A - t.u.
3.3 Утв2: {x | Ax = b} целый forall b если A - t.u.
3.4 Утв3: Если {x | Ax <= b} целый forall b, то A - t.u.
3.5 Утв2 => Утв1
3.6 Доказательство Утв1
3.7 Достаточное условие T.U.
3.8 Применение к паросочетаниям
3.9 Применение к потоку

4. Приятная минутка: доказываем, что k-регулярный граф имеет совершенное паросочетание

5. Политоп произвольной комбинаторной задачи
5.1 Введение: (E, F, w): ground set, feasible set, функция веса
5.2 Политоп над индикаторами conv(a1, ..., ak) = {sum_i lambda_i a_i | lambda_i >= 0, sum lambda_i = 1}
5.3 Утв1: conv(a1, ..., ak) политоп (следствие Фурье-Моцкина)
5.4 Утв2: любой индикатор остаётся вершиной
5.5 Утв3: других вершин не появилось

--------------------- Перерыв --------------

6. Лемма Фаркаша: {Ax = b, x>=0} infeasible iff exists y: A^T y >= 0, b^T y < 0.
6.1 Следствие LP in NP intersect coNP

7. Строим двойственную программу
7.1 Теорема о слабой двойственности
7.2 Следствие о том, что если одно unbounded, то другое Infeasible
7.3 Теорема о сильной двойственности

8. Применяем: строим двойственную программу для паросочетания (ого, теорема Кёнига)

9. Универсальные правила перехода к двойственности
9.1 Снова применяем для паросочетания

10. Последствия двойственности: TDI, max weighted matching.

[skipped] Эллипсоиды
[skipped] Бывает оракул отделения


reference
----------
http://math.mit.edu/~goemans/18453S17/polyhedral.pdf (здесь есть про двойственность, TU, интересные полиэдральные вещи, которые мы не обсудили)
правда изложение чуть-чуть отличается местами

А вот здесь можно почитать ещё один пример как LP помогает с приближенными решениями.
pages.cs.wisc.edu/~shuchi/courses/787-F09/scribe-notes/lec10.pdf

Видеозаписи курса Бабенко