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

Задача о кратчайшем пути является одной из самых изученных, красивых и практически востребованных проблем комбинаторной оптимизации и теории графов. Она составляет алгоритмический базис работы спутниковых навигаторов, протоколов маршрутизации в интернете (таких как OSPF и BGP) и анализа социальных сетей. Помимо этого, поиск кратчайшего пути часто является важнейшей подзадачей (субрутиной) в сложных методах декомпозиции и генерации столбцов для решения масштабных логистических задач целочисленного программирования.

Задача о покрытии множества (Set Covering Problem, SCP) — классическая и широко распространенная модель дискретной оптимизации. Она возникает каждый раз, когда необходимо выбрать минимальное количество ресурсов для удовлетворения заданного множества потребностей. SCP формирует математический фундамент для колоссальной индустрии составления расписаний экипажей авиакомпаний, оптимизации маршрутов мусоровозов, планирования смен медперсонала и размещения базовых станций сотовой связи.