В дискретной математике известно немало примеров оптимизационных задач, которые не просто эффективно разрешимы по отдельности, но и тесно связаны между собой, а именно образуют пары, в которых минимум в одной задаче равен максимуму в другой. Наиболее известными примерами таких пар, вероятно, можно считать утверждения о равенстве максимального потока и минимального разреза, размера максимального двудольного паросочетания и минимального вершинного покрытия, максимального размера антицепи в посете и минимального размера разбиения на цепи и т.д. Про задачи внутри пары говорят, что они двойственны друг другу.

Является ли каждое из этих соотношений случайным совпадением или мы имеем дело с некоторой общей метатеорией и ее частными проявлениями? Можем ли мы, имея на руках комбинаторную задачу, каким-либо общим способом попытаться построить ее двойственную?

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

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

Во второй части в зависимости от интереса слушателей мы пойдем одним из двух возможных путей. Мы либо сфокусируемся на сравнительно простых (с точки зрения полиномиальной разрешимости) оптимизационных задачах, в первую очередь касающихся двудольных графов, и изучим ряд эффективных алгоритмов на них.

Альтернативно мы можем обсудить структурно намного более сложные вопросы, где даже само существование полиномиального алгоритма представляет собой непростой вопрос (например, недвудольные графы и взвешенные паросочетания в них, матроиды и их пересечения, субмодулярные потоки).

Курс предполагается замкнутым и самодостаточным, никаких дополнительных знаний за пределами базовых понятий линейной алгебры и алгоритмов не потребуется.