Промышленное математическое программирование - тема раскрученная в академической среде для стандартизированных случаев, но детали реальных внедрений раскрываются редко и спустя много лет.

В настоящей статье делюсь опытом разработки и внедрения в процессы компании оптимизационного решения на базе математического программирования. Материал расширил исследовательскими элементами и локальным мини benchmark'ом.

Генерация столбцов - подход к решению задач смешанного линейного программирования (MIP) с большим кол-вом переменных или столбцов.

В статье представил теоретическую предпосылку, схему алгоритма и python реализацию подхода. В практической части рассмотрел решение двух задач: задача планирования расписания и задача раскроя.

С вами Алексей Ложкинс, эксперт по анализу данных и машинному обучению в ПГК Диджитал. Мы разрабатываем цифровые продукты для логистической отрасли, в первую очередь, для ж/д перевозок.

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

Моделирование маршрута в виде задачи коммивояжера позволит построить маршрут по всем запланированным локациям без повторений с заданным критерием качества (время, стоимость). Рассмотрим несколько подходов к решению оптимизационной задачи (TSP) с использованием пакета ORTools.

Транспортные, телекоммуникационные и компьютерные сети часто используют Hub-and-Spoke архитектуру для эффективной маршрутизации потоков между множеством отправителей и получателей. Особенность такой топологии заключается в использовании специального объекта сети - хаба. Хабом называется объект сети, который обеспечивает распределение, соединение, переключение, консолидацию, сортировку или перевалку в распределенных системах много-ко-многим. Кроме того, хабы позволяют соединить большой набор пар отправитель/получатель с использованием небольшого кол-ва соединений.

Задача размещения хабов (Hub Location Problem) относится к стратегическому уровню планирования сети. Это накладывает ограничения на возможность оперативной реализации и валидации решения. Одним из способов моделирования и анализа такого рода решений без рисков для текущей сети является математическое моделирование.

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

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

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

На выходных впервые удалось выбраться в Калининград. Я уделил немало внимания исследованию уровня жизни и благополучия области, в основном, ориентируясь на стоимость покупки/аренды жилья, цены в ресторанах и заработок таксистов. Данные достаточно доступные и позволяют сформировать общее представление о положении дел в городе/области.

Помимо экономической составляющей, конечно, старался погрузиться в культурный/исторический аспект жизни города. За короткий промежуток времени достаточно сложно проникнуться всеми особенностями, однако в Калининграде я бы выделил верное следование ограничениям скорости! Благодаря этому, возникает ощущение безопасности, замедления времени и спокойствия.

История города богатая, и в этом мешке событий я нашел кое-что интересное для себя. Речь пойдет о задаче семи пешеходных мостов Кёнигсберга. В свое время Эйлер в процессе размышлений над решением этой задачи положил начало теории графов. В статье рассмотрим задачу с позиции задачи линейного программирования и подтвердим результаты трехсотлетней давности с помощью Python и OR-Tools.

Математическое моделирование, оптимизация, исследование операций, программирование в ограничениях … Продолжим двигаться в этом направлении.

Статья выполнена в рамках проекта “Make optimization simple”, который погружает в область бизнес задач с точки зрения математического моделирования и оптимизации. Посредством готовых библиотек демонстрируются примеры решения такого рода задач.

В этой статье разберем одну из таких постановок. На примере задачи планирования сменного графика сотрудников сети стоматологических клиник пройдем этапы: от формулирования бизнес ограничений до получения готового решения. Для моделирования и поиска решения будем использовать инструменты Python и библиотеку OR-Tools.

Приветствую! Я, Ложкинс Алексей, консультант и разработчик оптимизационных решений и математических моделей для бизнеса. Это первая в цикле работ обучающая статья, часть личного образовательного проекта "Make optimization simple". Цель проекта – продемонстрировать доступность технологий и показать на примерах, что моделировать можно без глубокого математического фундамента.

Из статьи вы узнаете об основных компонентах математической оптимизационной задачи на примере классической задачи о назначениях, в частности, распределение машин такси на заказы. Далее, я покажу, как реализовать программный прототип математической модели посредством Python и библиотеки PuLP, а также продемонстрирую, как получить оптимальное решение задачи всего в одной строке кода без реализации специальных алгоритмов.