Целочисленное программирование
Задача целочисленного программирования — это задача математической оптимизации или выполнимости, в которой некоторые или все переменные должны быть целыми числами[1]. Часто термин адресуется к целочисленному линейному программированию (ЦЛП), в котором целевая функция и ограничения (за исключением требования целочисленности) линейны.
Целочисленное программирование является NP-трудной задачей. Частный случай 0-1 целочисленного линейного программирования, в котором переменные принимают значения только 0 или 1, является одной из 21 NP-полных задач Карпа.
где — векторы, а — матрица, все элементы которых являются целыми числами. Заметьте, что, как и в случае линейного программирования, ЦЛП-задача, не находящаяся в стандартном виде, может быть приведена к стандартному виду путём исключения неравенств введением дополнительных и искусственных переменных и заменой переменных, на которые не наложено ограничение неотрицательности, двумя переменными.
Допустимые целые точки показаны красным и красные пунктирные линии показывают выпуклую оболочку этих точек, которая является наименьшим многоугольником, содержащим все эти точки. Синие линии вместе с координатными осями определяют многоугольник линейного ослабления, который задаётся неравенствами без требования целочисленности. Цель оптимизации — сдвинуть чёрную пунктирную линию так, чтобы она была как можно выше, но касалась многоугольника. Оптимальные решения целочисленной задачи — точки и , на которых целевая функция принимает значение 2. Единственное решение ослабленной (линейной) задачи — точка , в которой целевая функция принимает значение 2.8. Заметим, что если мы округлим решение задачи линейного программирования до ближайших целых, решение будет недопустимо для ЦЛП.
Следующее рассуждение является сведением задачи минимизации вершинного покрытия к задаче целочисленного программирования, что доказывает NP-трудность.
Пусть — неориентированный граф. Определим задачу линейного программирования следующим образом:
