Задача о максимальном потоке (Maximum Flow Problem) является одной из важнейших задач в теории сетевых потоков. Дана транспортная сеть, где для каждого ребра установлена пропускная способность. Задача заключается в определении такого потока из источника в сток, чтобы суммарный объем переданного ресурса был максимальным, не нарушая при этом ограничений пропускной способности.

Задача о нахождении минимального остовного дерева (Minimum Spanning Tree, MST) является фундаментальной задачей теории графов с огромным количеством прикладных приложений. Остовным деревом связного неориентированного графа называется подграф, включающий все вершины графа и образующий дерево. Минимальное остовное дерево — это то, для которого сумма весов ребер минимальна.

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