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

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

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