Целочисленное программирование
Материал из Википедии — свободной encyclopedia
Задача целочисленного программирования — это задача математической оптимизации или выполнимости, в которой некоторые или все переменные должны быть целыми числами[1]. Часто термин адресуется к целочисленному линейному программированию (ЦЛП), в котором целевая функция и ограничения (за исключением требования целочисленности) линейны.
Целочисленное программирование является NP-трудной задачей. Частный случай 0-1 целочисленного линейного программирования, в котором переменные принимают значения только 0 или 1, является одной из 21 NP-полных задач Карпа.