Линейное программирование

Общая информация
ЛекторМ. А. Бабенко
Семестрвесна 2011
Дата начала16.04.2011
Количество пар10
Язык курсарусский
Вопросы к экзамену
Видеоhttp://lektorium.tv/course/?id=22810
Анонсы
Встреча ВКонтактеhttp://vkontakte.ru/event25953949
Встреча на сайте T&Phttp://theoryandpractice.ru/courses/2601-lineynoe-programmirovanie
Анонс на сайте it-event.ruhttp://it-event.ru/2487/
Аннотация

Линейное программирование (ЛП) возникло в 40-х годах прошлого века как один из разделов теории оптимизации. Довольно быстро оно стало популярным методом для решения задач экономики и планирования, в которых переменные принимают вещественные значения. В ряде случаев удавалось также приспособить ЛП и для дискретных задач, но систематическое изучение приложений ЛП к комбинаторике началось лишь несколько десятилетий спустя. Одним из пионеров в этой области, несомненно, является Джек Эдмондс, чьи работы по полиэдральной комбинаторике радикально расширили наши познания о связи комбинаторных и линейных задач.

Настоящий курс преследует несколько целей.

Во-первых, мы познакомимся с основными понятиями ЛП, изучим теоремы отделимости, линейной двойственности и обсудим полиномиальную разрешимость задачи ЛП с помощью метода эллипсоидов.

Во-вторых, с самого начала большое внимание будет уделяться связи ЛП с теорией целочисленного программирования, комбинаторикой и оптимизацией. Мы рассмотрим понятия тотальной унимодулярности и тотальной двойственной целочисленности линейных программ, а также выясним, как записывать подобные "хорошие" программы для большого количества комбинаторных задач.

В курсе предполагается дать обзор современных направлений полиэдральной комбинаторики. Мы обсудим понятие субмодулярности и его связи с теорией матроидов. В качестве примера будет разобрана задача о субмодулярном потоке, и на её основе получены многочисленные следствия, как совершенно элементарные (вроде теоремы Форда-Фалкерсона или Дилворта), так и более содержательные (например, теорема Нэша-Вильямса о наличии k-связной направленной ориентации у всякого 2k-связного ненаправленного графа).

Наконец, будут кратко изложены основные элементы полуопределенного программирования (SDP) и его приложений к приближенным алгоритмам (например, задаче о максимальном разрезе).

Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Лекция 1
(16.04.2011 - 17:20 - 18:55)

Задачи линейного и целочисленного программирования. Формы задач: стандартная и каноническая. Разрешимость задачи ЛП за конечное время, элиминация Фурье-Моцкина. Полиэдры, политопы и их вершины. Оптимум совместной ограниченной задачи достается в вершине. Пример: политоп паросочетаний графа. Алгебраический критерий вершины для задачи в стандартной форме.
Lecture notes: http://www-math.mit.edu/~goemans/notes-lp.ps (Sections 1-5)
http://lektorium.tv/lecture/?id=13276
2. Лекция 2
(16.04.2011 - 19:05 - 20:40)

Базисные допустимые решения. Конечность числа вершин. Тотально унимодулярные матрицы. Целочисленность полиэдра, задаваемого тотально унимодулярной матрицей. Достаточный признак тотальной унимодулярности. Тотальная унимодулярность матрицы в задачах о двудольном паросочетании и об оптимальной циркуляции. Оракулы отделения, метод эллипсоидов.
Lecture notes: http://www-math.mit.edu/~goemans/notes-lp.ps (Section 6), http://www-math.mit.edu/~goemans/18433S09/matching-notes.pdf, http://www-math.mit.edu/~goemans/18433S09/polyhedral.pdf (Section 3.5), http://www-math.mit.edu/~goemans/18433S09/ellipsoid.pdf, http://www-math.mit.edu/~goemans/18433S09/flowscuts.pdf (Section 6.1), http://users.eecs.northwestern.edu/~nickle/combOpt/lec12.pdf
http://lektorium.tv/lecture/?id=13277
3. Лекция 3
(17.04.2011 - 11:15 - 12:50)

Симплекс-метод. Вырожденные задачи, проблема зацикливания симплекс-метода. Различные способы выбора опорных индексов. Скелет политопа и его диаметр, связь с числом шагов симплекс-метода. Гипотеза Гирша. Двойственная линейная программа для задачи в стандартной форме. Слабая двойственность и ее следствия. Лемма Фаркаша. Сильная двойственность для задачи в стандартной форме. Построение двойственной программы для задачи в общей форме. Двойственность для задачи о максимальном двудольном паросочетании, вершинные покрытия.
Lecture notes: http://www-math.mit.edu/~goemans/notes-lp.ps (Section 7-10), http://www-math.mit.edu/~goemans/18433S09/polyhedral.pdf (Sections 3.1-3.3)
http://lektorium.tv/lecture/?id=13278
4. Лекция 4
(17.04.2011 - 13:00 - 17:35)

Системы допустимых множеств и их политопы, связь между комбинаторной и линейной задачами. Частично-упорядоченные множества, цепи и антицепи. TDI-системы. Функционалы, оптимумы которых достигаются в данной вершине, оценка ранга конуса. Всякая TDI-система с целочисленной правой частью задает целочисленный полиэдр.
Lecture notes: http://www-math.mit.edu/~goemans/18433S09/polyhedral.pdf (Section 3.4), http://www-math.mit.edu/~goemans/18997-CO/co-lec4.ps, http://users.eecs.northwestern.edu/~nickle/combOpt/lec4.pdf
http://lektorium.tv/lecture/?id=13279
5. Лекция 5
(17.04.2011 - 15:35 - 17:10)

Конусы и целые точки в них, базисы Гильберта. Существование конечного базиса Гильберта у любого рационального конуса. Всякий рациональный полиэдр задается TDI-системой, а всякий целочисленный -- TDI-системой с целочисленной правой частью. Максимальный размер цепи равен минимальному покрытию антицепями, обобщение на взвешенный случай. Доказательство свойства TDI для системы, задающей политоп цепей.
Lecture notes: http://www-math.mit.edu/~goemans/18997-CO/co-lec4.ps, http://www-math.mit.edu/~goemans/18997-CO/co-lec6.ps, http://users.eecs.northwestern.edu/~nickle/combOpt/lec4.pdf
http://lektorium.tv/lecture/?id=13280
6. Лекция 6
(23.04.2011 - 17:20 - 18:55)

Краткое напоминание: целочисленные полиэдры и комбинаторные задачи, тотальная унимодулярность и тотальная двойственная целочисленность. Доказательство тотальной двойственной целочисленности политипа паросочетаний в графе общего вида. Условия дополняющей нежесткости в паре линейно двойственных программ. Задача о кратчайших путях в направленном графе, запись в виде линейной программы, потенциалы вершин и приведенные длины. Прямо-двойственный алгоритм поиска кратчайшего пути.
Lecture notes: http://users.eecs.northwestern.edu/~nickle/combOpt/lec5.pdf, http://books.google.ru/books?id=u1RmDoJqkF4C&lpg=PA109&ots=S8wLM_9-H9&pg... (Section 5.4)
http://lektorium.tv/lecture/?id=13281
7. Лекция 7
(23.04.2011 - 19:15 - 20:50)

Задача о вершинно-взвешенном мультиразрезе, описание политопа. Двойственная линейная программа, T-пути и мультипотоки. Полуцелочисленность, 2-приближенный алгоритм и оракул отделения. Задача о кратчайшем ветвлении, описание верхней оболочки политопа. Прямо-двойственный алгоритм поиска кратчайшего ветвления.
Lecture notes: http://www-math.mit.edu/~goemans/18433S09/matroid-intersect-notes.pdf (Section 5.4), http://books.google.ru/books?id=EILqAmzKgYIC&lpg=PP1&pg=PA121 (Section 14.3), http://math.mit.edu/~goemans/18433S07/arborescence.pdf
http://lektorium.tv/lecture/?id=13282
8. Лекция 8
(24.04.2011 - 11:15 - 12:50)

Задача о максимальном разрезе в ненаправленном графе. Рандомизированное 2-приближениеМаксимальный разрез как задача целочисленного квадратичного программирования. Переход к векторной и полуопределенным программам. Решение с помощью метода эллипсоидов, отделение от конуса неотрицательно определенных матриц. Округление с помощью метода случайных гиперплоскостей, оценка погрешности.Матроиды, примеры. Базы, их равномощность, ранговая функция. Жадный алгоритм поиска максимального по весу независимого множества. Политоп независимых множеств, прямая и двойственная программы. Явная конструкция оптимальных прямого и двойственного решения. Тотальная двойственная целочисленность политопа независимых множеств.
Lecture notes: http://www-math.mit.edu/~goemans/18433S09/matroid-notes.pdf, http://www-math.mit.edu/~goemans/18997-CO/co-lec9.ps, http://www-math.mit.edu/~goemans/18997-CO/co-lec10.ps, http://users.eecs.northwestern.edu/~nickle/combOpt/lec6.pdf, http://users.eecs.northwestern.edu/~nickle/combOpt/lec7.pdf, http://www.cs.cmu.edu/~anupamg/adv-approx/lecture14.pdf
http://lektorium.tv/lecture/?id=13283
9. Лекция 9
(24.04.2011 - 13:00 - 14:35)

Субмодулярность ранговой функции. Субмодулярные функции на семействе множеств, примеры. Полиматроид и расширенный полиматроид. Жадный алгоритм для оптимизации по полиматроиду и расширенному полиматроиду. Тотальная двойственная целочисленность полиматроида. Задача минимизации субмодулярной функции. Восстановление субмодулярной функции по определяемому ей полиматроиду. Усечение полиматроида октантом. Эквивалентность задач оптимизации по полиэдру и отделения от полиэдра. Двойственный конус полиэдра, отделение от него с помощью метода эллипсоидов.
Lecture notes:
http://users.eecs.northwestern.edu/~nickle/combOpt/lec11.pdf,
http://books.google.ru/books?id=mqGeSQ6dJycC&lpg=PP1&pg=PA766 (Ch. 44)

http://lektorium.tv/lecture/?id=13284
10. Лекция 10
(24.04.2011 - 15:35 - 17:10)

Минимизация субмодулярной функции с помощью метода эллипсоидов. Пересечение матроидов, примеры. Трудность оптимизации по пересечению трех матроидов. Минимаксная формула для пересечения матроидов, вывод теоремы Кёнига-Эгервари. Политоп пересечения матроидов. Тотальная двойственная целочисленность политопа пересечения матроидов. Вывод минимаксной формулы для пересечения матроидов из линейной двойственности. Судмодулярные потоки. Тотальная двойственная целочисленность политопа субмодулярных потоков. Связность в направленных и ненаправленных графах. Существование k-связной ориентации у 2k-связного ненаправленного графа.
Lecture notes: http://books.google.ru/books?id=mqGeSQ6dJycC&lpg=PP1&pg=PA766 (Ch. 44), http://www-math.mit.edu/~goemans/18433S09/matroid-intersect-notes.pdf (Sections 5.1-5.3), http://www-math.mit.edu/~goemans/18997-CO/co-lec13.ps, http://www-math.mit.edu/~goemans/18997-CO/co-lec18.ps, http://www-math.mit.edu/~goemans/18997-CO/co-lec19.ps, http://users.eecs.northwestern.edu/~nickle/combOpt/lec8.pdf
http://lektorium.tv/lecture/?id=13285
Ваша оценка: Пусто Средняя: 4.9 (14 votes)
Share |
Максим Бабенко
Дмитрий Ицыксон на лекции М.А.Бабенко
Максим Бабенко
На лекции Максима Бабенко
Студенты
Лекция М.А.Бабенко
Максим Бабенко и Александр Куликов
Максим Бабенко и студенты
Александр Смаль и Максим Бабенко