Extended Formulations

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

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