В классических транспортных сетях часто возникает необходимость не просто передать максимальный объем ресурса от источника к стоку, но и сделать это с минимальными финансовыми затратами. Каждая транзитная магистраль обладает не только физическим лимитом пропускной способности, но и удельным экономическим тарифом за перекачку единицы груза. Задача о максимальном потоке минимальной стоимости (Min-Cost Max-Flow) объединяет в себе топологическую сложность теории графов и финансовую логику транспортной задачи линейного программирования. Ее математический аппарат позволяет виртуозно балансировать между пропускной способностью узких мест логистической цепи и стоимостью их эксплуатации, находя абсолютно идеальный экономический оптимум для глобальных инфраструктурных проектов.

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

Классическая задача о рюкзаке, решаемая методами динамического программирования за псевдополиномиальное время, оперирует лишь одним физическим ограничением (например, максимальным весом или объемом). Однако в реальных задачах логистики, капитального бюджетирования, загрузки трансатлантических судов и распределения виртуальных машин в облачных кластерах объекты обладают сразу множеством критических параметров: весом, габаритами, потреблением электроэнергии, вычислительной мощностью. Так в исследовании операций возникает Многомерная задача о рюкзаке (Multidimensional Knapsack Problem, MKP) — одна из самых математически непреклонных и вычислительно ресурсоемких NP-трудных задач комбинаторной оптимизации.

Проектирование крупных инфраструктурных сетей неизбежно сталкивается с проблемой географической оптимизации. Где построить новые региональные склады маркетплейса, чтобы минимизировать суммарные транспортные издержки при доставке товаров тысячам клиентов? В какой точке города разместить станцию скорой помощи или пожарную часть, чтобы гарантировать максимальную скорость реагирования на экстренные вызовы? В исследовании операций этот гигантский класс пространственных и дискретных оптимизационных моделей известен как Задачи размещения объектов (Facility Location Problems, FLP). Их математическое решение требует синтеза теории графов, целочисленного программирования и метрической геометрии.