0-1 программирование с постоянным числом ограничений полиномиально разрешимо?

11

В статье «Целочисленное программирование с фиксированным числом переменных» было показано, что целочисленное программирование с постоянным числом ограничений (или переменных) является полиномиально разрешимым.

Это относится к программированию 0-1?

регулярность
источник
Разве программирование 0-1 не является особым случаем целочисленного программирования?
Натанн Коэн
3
Я предполагаю, что нетривиальная часть заключается в следующем: если у вас есть алгоритм черного ящика A, который способен решать целочисленные программы с постоянным числом ограничений (но произвольно много переменных), не очевидно, как использовать A для решения программ 0-1 с постоянным количеством ограничений. Вы не можете просто добавить ограничения вида для каждой переменной x i . 0xi1xi
Юкка Суомела
3
Что такое «программа 0-1 с постоянным количеством ограничений»? Не учитываются ли ограничения ? 0xi1
Джефф

Ответы:

20

Я предполагаю, что под «программированием 0-1 с постоянным числом ограничений» вы подразумеваете следующую проблему:

Максимизируйте некоторую линейную функцию (x_1, x_2, ..., x_n) с учетом ограничений, что каждый x_i находится в {0,1}, и постоянного числа дополнительных линейных ограничений.

Эта задача является NP-полной, даже с 1 дополнительным ограничением, поскольку в этой форме можно записать рюкзак 0-1.

Робин Котари
источник
1
Кроме того, «неограниченный рюкзак», где у вас есть только границы неотрицательности и ограничения целостности без верхних границ 1, все еще NP-труден.
daveagp
0

В упомянутой статье Ленстра показал, что задача выполнимости целочисленной линейной программы

Am,nbZm
xZnAxb

полиномиально разрешима, если n или m постоянна. (Обратите внимание на отсутствие целевой функции.) Этот результат обычно используется при анализе параметризованных задач, т. Е. Он может быть использован для доказательства управляемости фиксированных параметров путем сокращения.

muede
источник
3
Я не уверен, почему вы опубликовали это, но если вы подразумеваете, что разница между версией технико-экономического обоснования и версией оптимизации важна, то нет, это не важно: алгоритм полиномиального времени для версии технико-экономического обоснования можно использовать для решения версия оптимизации также за полиномиальное время путем объединения ее с бинарным поиском.
Цуёси Ито
-1

Целочисленное программирование 0-1 или двоичное целочисленное программирование (BIP) - это особый случай целочисленного программирования, где переменные должны быть 0 или 1 (а не произвольные целые числа). Эта проблема также классифицируется как NP-hard, и фактически версия решения является NP-Complete.

Каран Сапра
источник
3
Хотя IP и BIP являются NP-сложными, это мало говорит о том, являются ли IP и BIP с постоянным количеством ограничений NP-сложными. Действительно, IP с постоянным количеством ограничений находится в P, тогда как BIP с постоянным количеством ограничений по-прежнему NP-сложен.
Робин Котари