Целочисленное программирование с фиксированным числом переменных

12

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

Я интерпретирую это следующим образом.

  1. Целочисленное программирование в целом все еще является NP-полным, но если мой типичный размер задачи (скажем, около 10.000 переменных, произвольное количество ограничений) практически осуществим, то я мог бы построить алгоритм, который масштабируется полиномиально по количеству ограничений, но не количество переменных и ограничений.
  2. Результат также применим для двоичного программирования, так как я могу принудительно заставить любое целое число 0-1, добавив соответствующее ограничение.

Правильна ли моя интерпретация?

Имеет ли этот результат какие-либо практические последствия? То есть, есть ли доступная реализация или она используется в популярных решателях, таких как CPLEX, Gurobi или Mosek?

Некоторые цитаты из бумаги:

Для наших целей эта длина может быть определена как n · m · log (a + 2), где a обозначает максимум абсолютных значений коэффициентов A и b. Действительно, такого полиномиального алгоритма, скорее всего, не существует, поскольку рассматриваемая проблема является NP-полной

[...]

Предполагалось [5], [10], что для любого фиксированного значения n существует полиномиальный алгоритм для решения задачи целочисленного линейного программирования. В настоящей статье мы доказываем эту гипотезу, демонстрируя такой алгоритм. Степень полинома, по которой время выполнения нашего алгоритма может быть ограничено, является экспоненциальной функцией от n.

Бернхард Кауслер
источник
2
«Я мог бы построить алгоритм, который масштабируется полиномиально по количеству ограничений или переменных, но не по числу переменных и ограничений». Интересный момент / вопрос - до сих пор мы видели, что это верно для ограничений (с фиксированным числом переменных), но, возможно, было бы интересно спросить, может ли это быть верно для переменных (с фиксированным числом ограничений) ? Интуитивно кажется, что это не должно быть правдой, иначе в общем случае IP был бы просто временем, но я не уверен.
Усул
В разделе 4 статьи Ленстра заявляет, что «задача целочисленного линейного программирования с фиксированным значением m полиномиально разрешима». (m - количество противопоказаний). Это следует из следствия основного результата. Этот раздел мне не понятен. На секунду подумать, может быть, он предполагает фиксированные п И м; это означает, что это полином в «а» (максимум абсолютных значений коэффициентов А и В). (Как следствие, я удалил часть «или переменные» из моего вопроса выше).
Бернхард Кауслер
6
nmmn

Ответы:

19

n

O(n2.5n+o(n)L)LLn

Таким образом, задача является линейно параметризованной с фиксированным параметром числом переменных.

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

2) Да, заставить переменные принимать двоичные значения просто, как вы заметили.

L

O(2nnm+8nnmlogmlogm+n2.5n+o(n)slogm)
ms
Серж Гасперс
источник
1
Ах, спасибо за термин "линейный фиксированный параметр". Вот о чем статья Ленстры. Смотрите также: en.wikipedia.org/wiki/Parameterized_complexity
Бернхард Кауслер
4
nO(n2nm)
T(n,m,s)nmsO(2nm+(logm)T(n,f(n),s)O(s)f(n)nO(n)
1
Это не меняет основных фактов вашего ответа, но другой релевантной ссылкой является К.Л. Кларксон. Алгоритмы Лас-Вегаса для линейного и целочисленного программирования, когда размерность мала. J. ACM 42 (2): 488-499, 1995, doi: 10.1145 / 201019.201036.
Дэвид Эппштейн
2
mnO(n2.5n+o(n)L)T(n,f(n),s)f(n)=4nL=4nsf(n)O(2nnm+n2.5n+o(n)(logm)s)
4

Вот несколько моментов, касающихся практического значения результатов типа Lenstra, и возможных реализаций в CPLEX, Gurobi и т. Д. Одним из ключевых шагов в большинстве таких алгоритмов для IP является переход на «хорошие» или «тонкие» направления, т.е. гиперплоскости, вдоль которых ширина многогранника не слишком велика (полином по переменным и размеру данных). Но Махаджан и Ральфс (препринт здесь ) показали, что проблема выбора оптимальной дизъюнкции является NP-полной. Таким образом, было бы трудно создать практически эффективные реализации этого класса алгоритмов.

Большинство алгоритмов, реализованных в таких пакетах, как CPLEX, можно классифицировать как методы ветвления и вырезания. Это семейство методов, как правило, хорошо работает на экземплярах IP, которые выполнимы, и часто способны находить почти оптимальные решения. Но в центре внимания алгоритмов типа Lenstra находятся наихудшие случаи IP, с которых невозможно начать, и цель состоит в том, чтобы доказать их целочисленную невозможность (и они изучают сложность этой задачи). AFAIK, нет класса проблем с практической значимостью, которые соответствуют этому описанию. Таким образом, люди из CPLEX / Gurobi, вероятно, не будут реализовывать алгоритмы типа Lenstra в ближайшее время.

kbala
источник