Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Extended Formulations
Санкт-Петербург / осень 2019, посмотреть все семестры

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

В теоретической информатике многие задачи оптимизации могут быть сформулированы как задачи линейного программирования. Для этого с каждым допустимым решением задачи оптимизации отождествляют точку, так чтобы целевая функция соответствовала линейной функции над полученными точками. Такая трансформация дает доступ к методам линейного программирования для получения оптимального решения. К сожалению, для многих задач оптимизации "прямой" способ получения задачи линейного программирования ведет к программе очень большого размера. В таких случаях расширенные формулировки (extended formulations) предоставляют возможность уменьшить размер программы. Это обусловило появление интенсивного интереса к расширенным формулировкам.

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

Дата и время Занятие Место Материалы
12 октября
17:15–18:45
Лекция, Лекция ПОМИ РАН видео
12 октября
19:00–20:30
Лекция, Лекция ПОМИ РАН видео
13 октября
11:15–12:45
Лекция, Лекция ПОМИ РАН видео
13 октября
13:00–14:30
Лекция, Лекция ПОМИ РАН видео
13 октября
15:30–17:00
Лекция 5, Лекция ПОМИ РАН видео