Ресурсы по исследованию операций

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

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

МООК

Курс	Автор	Примечания	Комментарии
Курс Coursera по дискретной оптимизации	ван Хентенрик	МИП и КП	Квоте@: Мне это понравилось. Однако еще не закончил окончательный набор задач.
Базовое моделирование для дискретной оптимизации	Ли и Стаки	Больше внимания CP
Расширенное моделирование для дискретной оптимизации	Ли и Стаки
Решение алгоритмов дискретной оптимизации	Ли и Стаки
Моделирование и решение проблем искусственного интеллекта в Picat	Бартак
ИЛИ(1): Модели и приложения	Кунг		Zaphod@: Эти и следующие два — отличное введение во все, что связано с LP/IP.
ИЛИ(2): Алгоритмы оптимизации	Кунг
ИЛИ(3): Теория	Кунг

Основы LP и MIP

Крышка	Заголовок	Автор	Комментарии
	Введение в линейную оптимизацию	Берцимас и Цициклис	BlackLotus@: Для LP (и, в меньшей степени, для MIP), я думаю, эта книга лучше всего. Патрик@: Проголосовал против Берцимаса-Цициклиса, так как это скорее «Второй курс» по линейному программированию, и для этого, вероятно, лучше всего вместе с «Введением в линейную оптимизацию» . BadBoy@: Мне нужно взглянуть на это. Обычно мне не нравится, как эти ребята преподносят материал, но я могу ошибаться. Kvothe@: Главы 10 («Формулы целочисленного программирования») и 11 («Методы целочисленного программирования») великолепны.
	Линейное программирование	Вандербей
	Комбинаторная оптимизация: многогранники и эффективность	Шрийвер	SpiderWoman@: Я помню, как когда-то мне нравилась «Комбинаторная оптимизация» Шрийвера, но она очень математическая, и я бы не рекомендовала ее тем, кто, например, присоединяется к команде…
	Теория линейного и целочисленного программирования	Шрийвер	BadBoy@: Круто похвастаться в своей библиотеке, во время интервью или произвести на кого-то впечатление. Вы, скорее всего, не прочитаете ее, и она вам не понравится, если только у вас нет докторской степени в области чистой, дважды очищенной математики. Так что это не то, с чего стоит начинать LP или MIP. При этом он содержит массу доказательств и интересной информации. Такие вещи, как полностью унимодулярные матрицы и что они за собой влекут. Библиография невероятно подробно описана, с цитатами на языках оригинала. Это своего рода искусство компьютерного программирования Кнута. Только этот не переваривается. Kvothe@: Не читал, но не доверяю только из-за шрифта.
	Первый курс линейной оптимизации	Ли	Доступно бесплатно по лицензии CC!
	Введение в математическую оптимизацию	Фишетти	BadBoy@: Я прошел итальянскую версию. Выглядит очень хорошо. Мне вообще нравится то, что делает Фишетти.
	Линейное программирование	Хватал	BadBoy@: Мне не нравится эта книга, но именно там я выучил все LP, и обозначения отличные.
	Комбинаторная оптимизация	Пападимитриу и Стейглиц	BadBoy@: Мне понравилось. Оно устарело, но вам стоит его прочитать. Квоте@: На мой вкус немного суховато.
	Целочисленное программирование	Уолси	Unicorn@: Очень кратко, но охватывает большинство интересных частей области (с точки зрения решателя).
	Целочисленное программирование	Конфорти, Корнюжоль и Замбелли	Патрик@: Наверное, самая современная книга по теории/методологии MIP.
	Аспекты комбинаторной оптимизации	Юнгер и Рейнельт	Патрик@: Больше о теоретической стороне и с уклоном в сторону работы бывшего директора ZIB Мартина Гретшеля (она сделана на праздновании его 65-летия), но она включает, как мне кажется, последнюю версию этого вычислительного опроса MIP: «Тобиас Ахтерберг и Роланд Вундерлинг Смешанное целочисленное программирование: анализ 12 лет прогресса».
	50 лет целочисленного программирования: 1958–2008 гг.	Юнгер и др., изд.	Патрик@: Немного устаревший, но очень хороший обзор истории и современного состояния MIP.
	Алгоритмы сетевых потоков	Уильямсон	Unicorn@: Хорошая книга, содержащая множество недавних результатов о сетевых потоках, но при этом интуитивно понятная. Однако только для сетевых потоков, так что это не так уж и универсально. Более полный обзор на французском языке.
	Освещенные алгоритмы: алгоритмы для решения NP-сложных задач	Рафгарден	Unicorn@: Наверное, не самая продвинутая книга из этой колоды! Тем не менее, он представляет собой введение в некоторые алгоритмы ИЛИ (с точки зрения курса алгоритмов). Очень читабельно! Более полный обзор на французском языке.
	Практическая оптимизация	Джилл, Мюррей и Райт	Unicorn@: Старый справочник по непрерывной оптимизации. Если вам нужно какое-либо объяснение этого семейства алгоритмов, эта книга вам поможет. (Более полный обзор на французском языке.)
	Введение в оптимизацию и полудифференциальное исчисление Адамара	Дельфур	Unicorn@: Очень формальная книга о полудифференциальной оптимизации. Нелегко попасть. Более полный обзор на французском языке.
	Иерархия Moment-SOS: лекции по теории вероятностей, статистике, вычислительной геометрии, управлению и нелинейным PDE	Генрион, Корда и Лассер	Unicorn@: Если вы оптимизируете с помощью полиномов или задаетесь вопросом, как далеко вы можете зайти с их помощью, вы получите основы иерархии SoS и незнакомых приложений. Более полный обзор на французском языке.
	Введение в исследование операций	Хиллиер и Либерман	Kvothe@: Хорошее сочетание теории и практики. Хороший первый текст для новичков в этой области, с проработанными примерами и множеством упражнений, некоторые из которых с ответами в конце книги. Недостатки: книга слишком старается привлечь пользователей на свой веб-сайт и использует устаревшие решатели.

Обзоры исследований

Обзор	Автор	Комментарии
175 лет линейного программирования	Чандру и Рао	BadBoy@: Это отличная серия статей. Я столкнулся с этим в IBM в начале 1990-х годов. Я не знаю, кому первому пришла в голову идея представить такое линейное программирование, но Виджей Чандру и Жан-Луи Лассез тоже в этом участвовали. Самое приятное в этом то, что для его понимания вам нужна только линейная алгебра начального уровня, и вы можете доказать практически любую важную теорему в LP, используя основы. Лучше всего была бы книга по ЛП с этим, плюс немного Хватала, немного Вандербея, а потом вопросы реализации и ссылки на соответствующие книги. Хваталу и Вандербею не хватает твердой математической базы. Оно устарело и вскоре должно быть переименовано в «200 лет линейного программирования». Возможно, попытки были и раньше.

Исследовательские статьи

Статья	Автор	Комментарии
Новый алгоритм линейного программирования с полиномиальным временем	Кармаркар	BadBoy@: статья Кармаркара об алгоритме Кармаркара. Пример того, как не следует писать статью. На разработку работающей реализации ушли годы, а тем временем они обнаружили, что это еще один метод внутренней точки.

Моделирование

МИП

Крышка	Заголовок	Автор	Комментарии
	Построение моделей в математическом программировании	Уильямс	Акцент на LP и MIP. Темере@: Мне это очень не понравилось. Структура странная (и искусственное увеличение количества страниц). И это глубоко укоренено в «классических ИЛИ-приложениях» (фокус на экономичности или почти игрушечном планировании) и мало связано с моделями MIP, которые мы обычно используем в Google. Азалия@: Согласна. BadBoy@: Я до сих пор считаю, что в те времена эта книга была великолепной. Я посмотрел на это, может быть, года 2 назад, и, черт возьми. Это устарело. Кроме того, я знаю автора с 1990 года, и мы снова встретились на ISMP 2015. Он отличный парень, на пенсии, ездит на конференции на свои деньги и до сих пор делает отличные презентации. Его работы были великолепны, особенно по методу исключения Фурье. У него очень широкое видение того, что такое LP. Он сыграл важную роль в запуске XpressMP.
	Приложения оптимизации с помощью XpressMP	Гере, Принс, Сево и Хайпке

Руководства по моделированию, выпущенные решателем

Гид	Описание	Комментарии
Рецепты моделирования MOSEK	Сосредоточен на конической выпуклой оптимизации.	Unicorn@ Для меня настоящий справочник при нелинейном моделировании.
Поваренная книга портфолио МОСЭК	Конические модели для оптимизации портфеля

Обзоры исследований: MIP

Обзор	Автор	Описание
Методы формулирования смешанного целочисленного линейного программирования	Вильма	Основное внимание уделяется силе и размеру смешанно-целочисленных формулировок для объединений многогранников кусочно-линейных функций. Больше теоретической стороны, но включает в себя некоторые практические методы, такие как поэтапные формулировки в разделе 8.
Невыпуклые кусочно-линейные функции: расширенные формулировки и простые инструменты моделирования.	Юшетт и Вильма	Более поздние методы расчета кусочно-линейных функций, не вошедшие в приведенный выше обзор.

Обзоры исследований: MINLP

Обзор	Автор	Описание
Смешанно-целочисленная выпуклая представимость	Любин, Вильма и Задик	Только для выпуклых релаксаций.

Оптимизация в условиях неопределенности

Стохастическая оптимизация

Крышка	Заголовок	Автор	Комментарии
	Лекции по стохастическому программированию: моделирование и теория	Шапиро, Денчева и Рущинский
	Введение в стохастическое программирование	Бирж и Луво	Unicorn@: Более теоретическое введение в тему. Я не рекомендую его так сильно, как Лекции по стохастическому программированию.

Обзоры исследований

Обзор	Автор
Оптимизация условной стоимости под риском	Рокафеллар и Урясев

Надежная оптимизация

Крышка	Заголовок	Автор	Комментарии
	Надежная оптимизация	Бен-Тал, Эль-Гауи и Немировский	PDF. Unicorn@: отличный справочник, если приведенные ниже обзоры недостаточно подробны. Большая часть посвящена нелинейным задачам (как правило, не представленным в обзорах). Мне очень нравится раздел 1.1.2, потому что он численно показывает, что небольшие отклонения коэффициентов могут привести к большим невозможностям.
	Надежная и адаптивная оптимизация	Берцимас и Дик Ден Хертог	PDF. Unicorn@: Отличный справочник по всему, что касается надежной оптимизации! Это довольно тщательно, можно было бы добавить немного больше алгоритмов. Более полный обзор на французском языке.

Обзоры исследований

Обзор	Автор
Практическое руководство по надежной оптимизации	Гориссен, Яникоглу и ден Хертог
Теория и приложения робастной оптимизации	Берцимас, Браун и Караманис

Исследовательские статьи

Статья	Автор
Управляемый стохастический анализ в больших размерностях посредством надежной оптимизации ( PDF )	Банди и Берцимас

СтекExchange

Какие справочники являются хорошими для введения в исследование операций?

Рекомендуемые книги/материалы для практического применения исследования операций в промышленности