Discrete Optimization Course, Spring 2025

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

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

Лекции сопровождаются семинарами, на которых будут представлены разные универсальные эвристики для решения дискретных задач. Студенты смогут апробировать эти алгоритмы на конкретных задачах, в частности, задаче коммивояжёра.