Самая быстрая сложность для комбинаторного алгоритма ILP?

Я интересно, что это лучший известный алгоритм, в терминах big- нотации, для решения целочисленных линейного программирования? $O$

Я знаю, что проблема в полном, поэтому я не ожидаю ничего полиномиального. И я знаю, что есть много эвристик и тому подобного, которые используются в практических приложениях, таких как CPLEX, но меня больше интересует формальная сложность точного алгоритма в худшем случае. $NP$

Некоторые -полные задачи имеют алгоритмы во времени где а - многочлен. Покрытие вершин, независимый набор и 3SAT попадают в эту категорию, но обычные SAT и TSP не (насколько мы знаем). $NP$ $O(b^n p(n))$ $1 < b < 2$ $p$

Могут ли быть сделаны такие заявления о целочисленном программировании или конкретных подэлементах?

Если у кого-нибудь есть справка по связанной проблеме Quantifier Free Presburger Arithmetic, меня это тоже очень заинтересует.

algorithms complexity-theory reference-request np-complete integer-programming jmite
источник

Аардал, Карен, Роберт Вейсмантел и Лоуренс А. Уолси. «Нестандартные подходы к целочисленному программированию». Дискретная прикладная математика 123.1 (2002): 5-74. дает много ссылок. Может быть, вы можете найти ответ, посмотрев на них, или проследив, какие новые статьи ссылаются на этот. Посмотрите на Раздел 2 в частности.

Юхо

В чем разница между

O ({1.1}^{n})

$O(1.1^{n})$

O (99^{n})

$O(99^{n})$

Седобородый

@greybeard, не так много для P против NP, но очень много с точки зрения реальной управляемости, в зависимости от констант, это имеет огромное значение.

Jmite

O (b^{n})

$O(b^n)$

O (c n)

$O(cn)$

b

$b$

c

$c$

@jmite Готово. Была ли для вас какая-либо ссылка или вы смогли найти какую-то новую информацию?

Юхо

Ответы:

Из того, что я могу сказать путем поиска, определенное исследование выглядит так:

Аардал, Карен, Роберт Вейсмантел и Лоуренс А. Уолси. «Нестандартные подходы к целочисленному программированию». Дискретная прикладная математика 123.1 (2002): 5-74.

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

Для фиксированного числа переменных целочисленное линейное программирование решается за полиномиальное время по алгоритму Ленстры.

Юхо
источник

хорошо, но какой алгоритм самый быстрый?

15:00

@vzn Я не знаю, это не более чем ответ, охватывающий "конкретные подэкземпляры".

Юхо