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