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

Метод Нелдера-Мида, широко известный как метод деформируемого многогранника, представляет собой один из самых популярных и надежных алгоритмов прямого поиска. Разработанный в 1965 году Джоном Нелдером и Роджером Мидом, этот алгоритм решает задачи нелинейной безусловной минимизации функций многих переменных без использования вычисления градиентов или матриц Гессе. Это свойство делает его бесценным инструментом для оптимизации сложных функций черного ящика, зашумленных данных и недифференцируемых математических моделей, где классические ньютоновские методы терпят сокрушительное поражение.

Метод поиска с запретами (Tabu Search, TS), предложенный Фредом Гловером в конце 1980-х годов, является одной из самых влиятельных и результативных метаэвристик в комбинаторной оптимизации. В отличие от простых алгоритмов локального спуска, которые неизбежно застревают в первом встречном локальном минимуме, и методов имитации отжига, использующих слепую вероятностную стратегию для выхода из ловушек, алгоритм поиска с запретами наделен интеллектуальной адаптивной памятью, позволяющей ему методично и детерминированно исследовать ландшафт целевой функции.

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