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

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

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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

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

Date and time Class|Name Venue|short Materials
12 October
17:15–18:45
Лекция, lecture ПОМИ РАН No
12 October
19:00–20:30
Лекция, lecture ПОМИ РАН No
13 October
11:15–12:45
Лекция, lecture ПОМИ РАН No
13 October
13:00–14:30
Лекция, lecture ПОМИ РАН No
13 October
15:30–17:00
Лекция, lecture ПОМИ РАН No