Задача о рюкзаке (Knapsack Problem) — это классическая задача комбинаторной оптимизации, входящая в список NP-трудных задач. Суть ее заключается в выборе набора предметов с заданным весом и стоимостью, чтобы максимизировать суммарную стоимость при ограничении по общей грузоподъемности рюкзака. Простота постановки контрастирует со сложностью нахождения точного решения при увеличении числа предметов.

Нелинейное программирование охватывает задачи оптимизации, в которых целевая функция или ограничения являются нелинейными. В отличие от линейных задач, здесь локальный экстремум не всегда является глобальным, а сложность алгоритмов зависит от свойств выпуклости функции. Методы градиентного спуска составляют основу итерационных процедур для поиска локального минимума дифференцируемых функций.

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