Аспекты комбинаторной оптимизации: Festschrift Мартина Гротшеля

Мартин Гротшель — один из самых влиятельных математиков нашего времени. Он получил множество наград и занимает ряд ключевых позиций в международном математическом сообществе. 10 сентября 2013 года он отпраздновал свое 65-летие. Древо докторских потомков Мартина Гротшеля за 1983–2012 годы, то есть за первые 30 лет, включает 39 детей, 74 внука, 24 правнука и 2 праправнука, всего 139 человек. потомки докторантуры. Эта книга начинается с личной дани Мартину Гротшелю со стороны редакторов (Часть I), статьи его особенного «предшественника» Манфреда Падберга о «Гранях и рангах целочисленных многогранников» (Часть II), а также докторского дерева потомков 1983 г. 2012 (Часть III). Ядро этой книги (Часть IV) содержит 16 статей, соавтором каждой из которых является по крайней мере один потомок доктора. Последовательность статей начинается с вклада в теорию математической оптимизации, включая полиэдральную комбинаторику, расширенные формулировки, выпуклую смешанно-целочисленную оптимизацию, суперклассы совершенных графов, эффективные алгоритмы для поддеревьев-телецентров, соединения в ациклических графах и вытесняющее покрытие ограниченной полосы. , а также эффективная аппроксимация невытесняющего покрытия ограниченной полосы. Сочетание новых теоретических открытий с алгоритмами и экспериментами касается проблем проектирования сетей, задач комбинаторной оптимизации с субмодулярными целевыми функциями и более общих задач смешанно-целочисленной нелинейной оптимизации. Приложения включают проектирование компоновки СБИС, системную биологию, проектирование беспроводных сетей, оптимизацию среднего риска и оптимизацию газовой сети. Вычислительные исследования включают в себя полуопределенный подход ветвей и разрезов для задачи максимального k-разреза, смешанно-целочисленное нелинейное оптимальное управление и смешанно-целочисленную линейную оптимизацию для планирования и маршрутизации летающих самолетов сафари. Две заключительные статьи посвящены вычислительным достижениям в области общей смешанной целочисленной линейной оптимизации [...]