Задачи стратегического планирования, такие как проектирование цепей поставок, часто содержат два принципиально разных типа переменных. С одной стороны, это бинарные решения (строить ли завод в этом городе?), а с другой — непрерывные переменные (сколько тонн груза отправить с этого завода?). Попытка решить такую смешанно-целочисленную задачу (MILP) единым блоком приводит к катастрофическому замедлению расчетов из-за огромного дерева перебора. В 1962 году голландский математик Жак Бендерс предложил элегантный алгоритм разложения, который математически изолирует сложные целочисленные переменные от простых непрерывных, совершив революцию в промышленной оптимизации.

Классические задачи маршрутизации транспорта (VRP) относятся к классу статической оптимизации: логист получает полный список заказов вечером, всю ночь суперкомпьютер рассчитывает идеальные маршруты, и утром машины выезжают из депо по жесткому графику. Однако с появлением электронной коммерции (Uber, доставка еды, службы экстренного реагирования) информационная парадигма изменилась. Половина или даже все заказы возникают в режиме реального времени, когда курьеры уже находятся на линии. Для управления этим стохастическим хаосом была создана Динамическая задача маршрутизации (Dynamic VRP, DVRP), требующая передовых алгоритмов перераспределения ресурсов на лету.

Симплекс-метод, разработанный Джорджем Данцигом в 1947 году, превосходно и быстро решал 99 процентов промышленных задач линейного программирования (ЛП). Однако в 1972 году математики Виктор Кли и Джордж Минти сконструировали искусственный многогранник (Куб Кли-Минти), на котором симплекс-метод был вынужден обойти абсолютно все вершины, что требовало экспоненциального времени вычислений. Это породило главную интригу дискретной математики XX века: относится ли линейное программирование к классу задач $P$ (решаемых за полиномиальное время)? В 1979 году советский математик Леонид Хачиян потряс мировой научный мир, опубликовав Метод эллипсоидов, навсегда доказавший, что линейное программирование строго полиномиально.