La complexité la plus rapide connue pour l'algorithme ILP combinatoire?

Je me demande quel est l'algorithme le plus connu, en termes de notation Big- $O$ , pour résoudre la programmation linéaire en nombres entiers?

Je sais que le problème est $NP$ complet, donc je ne m'attends à rien de polynomial. Et je sais qu'il y a beaucoup d'heuristiques et autres qui sont utilisées dans des applications pratiques comme CPLEX, mais je suis plus intéressé par la complexité formelle du pire des cas d'un algorithme exact.

Certains problèmes complétés par ont des algorithmes dans le temps où et est un polynôme. La couverture Vertex, le set indépendant et le 3SAT entrent dans cette catégorie, mais pas le général-SAT et le TSP (à notre connaissance). $NP$ $O(b^n p(n))$ $1 < b < 2$ $p$

De telles déclarations peuvent-elles être faites à propos de la programmation entière ou de sous-instances particulières?

Si quelqu'un a une référence pour le problème connexe de l'arithmétique sans quantificateur libre, je serais très intéressé par cela aussi.

algorithms complexity-theory reference-request np-complete integer-programming jmite
la source

Aardal, Karen, Robert Weismantel et Laurence A. Wolsey. "Approches non standard de la programmation entière." Mathématiques appliquées discrètes 123.1 (2002): 5-74. donne beaucoup de références. Peut-être pouvez-vous trouver la réponse en les regardant ou en retraçant les articles les plus récents qui citent celui-ci. Regardez la section 2 en particulier.

Juho

Quelle est la différence entre

O ({1.1}^{n})

$O(1.1^{n})$

O (99^{n})

$O(99^{n})$

greybeard

@greybeard, pas beaucoup pour P vs NP, mais beaucoup en termes de tractabilité dans la vie réelle, selon les constantes, cela fait une énorme différence.

jmite

Je souhaite que j'espérais un rappel initial que, étant donné

, une différence dans

entraîne un ensemble de fonctions différent, tandis que l'une dans

ne fonctionne pas et, par conséquent, est abstraite .

O (b^{n})

$O(b^n)$

O (c n)

$O(cn)$

b

$b$

c

$c$

greybeard

@jmite Done. La référence vous a-t-elle été utile ou avez-vous pu trouver de nouvelles informations?

Juho

D'après ce que je peux dire en cherchant, le sondage définitif semble être:

Aardal, Karen, Robert Weismantel et Laurence A. Wolsey. "Approches non standard de la programmation entière." Mathématiques appliquées discrètes 123.1 (2002): 5-74.

En particulier, la section 2.1 discute de la programmation entière en dimension bornée et présente des algorithmes dus à différents auteurs. En effet, l'enquête répertorie de nombreuses références et discute de quelques implémentations pratiques.

Pour un nombre fixe de variables, la programmation linéaire entière est résolue en temps polynomial par l'algorithme de Lenstra.

Juho
la source

très bien, mais quel est l'algorithme le plus rapide connu?

2015

@vzn Je ne sais pas, c'est tout au plus une réponse couvrant "des sous-instances particulières".

Juho

La complexité la plus rapide connue pour l'algorithme ILP combinatoire?

Réponses: