Schnellste bekannte Komplexität für kombinatorischen ILP-Algorithmus?

Ich frage mich, welcher Algorithmus in Bezug auf die Big- Notation am bekanntesten ist, um die ganzzahlige lineare Programmierung zu lösen? $O$

Ich weiß, dass das Problem vollständig ist, also erwarte ich nichts Polynomielles. Ich weiß, dass es viele Heuristiken gibt, die in praktischen Anwendungen wie CPLEX verwendet werden, aber ich bin mehr an der formalen Komplexität eines exakten Algorithmus im schlimmsten Fall interessiert. $NP$

Einige vollständige Probleme haben Algorithmen in der Zeit wobei und ein Polynom ist. Vertex Cover, Independent Set und 3SAT fallen in diese Kategorie, General-SAT und TSP nicht (soweit wir wissen). $NP$ $O(b^n p(n))$ $1 < b < 2$ $p$

Können solche Aussagen über Integer Programming oder bestimmte Unterinstanzen gemacht werden?

Wenn jemand eine Referenz für das verwandte Problem der quantifiziererfreien Presburger-Arithmetik hat, würde mich das auch sehr interessieren.

algorithms complexity-theory reference-request np-complete integer-programming jmite
quelle

Aardal, Karen, Robert Weismantel und Laurence A. Wolsey. "Nicht-Standard-Ansätze zur ganzzahligen Programmierung." Discrete Applied Mathematics 123.1 (2002): 5-74. gibt viele Hinweise. Vielleicht können Sie die Antwort finden, indem Sie sich diese ansehen oder nachzeichnen, welche neueren Artikel diese zitieren. Schauen Sie sich insbesondere Abschnitt 2 an.

Juho

Was ist der Unterschied zwischen und

O ({1.1}^{n})

$O(1.1^{n})$

O (99^{n})

$O(99^{n})$

Greybeard

@greybeard, nicht viel für P vs NP, aber viel in Bezug auf die Traktabilität im wirklichen Leben, abhängig von den Konstanten, macht es einen großen Unterschied.

Jmite

Ich wünschte, ich hätte auf eine erste Erinnerung gehofft , dass ein Unterschied in

bei

und

zu einer anderen Menge von Funktionen führt, während einer in

nicht und folglich abstrahiert .

O (b^{n})

$O(b^n)$

O (c n)

$O(cn)$

b

$b$

c

$c$

Greybeard

@jmite Fertig. War der Verweis von Nutzen für Sie oder konnten Sie neue Informationen finden?

Juho

Antworten:

Nach dem, was ich anhand der Suche feststellen kann, scheint die endgültige Umfrage zu lauten:

Aardal, Karen, Robert Weismantel und Laurence A. Wolsey. "Nicht-Standard-Ansätze zur ganzzahligen Programmierung." Discrete Applied Mathematics 123.1 (2002): 5-74.

Insbesondere wird in Abschnitt 2.1 die Ganzzahlprogrammierung in begrenzten Dimensionen erörtert und Algorithmen vorgestellt, die von verschiedenen Autoren stammen. In der Tat werden in der Umfrage viele Referenzen aufgeführt und einige praktische Umsetzungen erörtert.

Für eine feste Anzahl von Variablen ist die ganzzahlige lineare Programmierung durch den Lenstra-Algorithmus polynomiell zeitlösbar.

Juho
quelle

gut, aber was ist der schnellste bekannte Algorithmus?

vzn

@vzn Ich weiß nicht, dies ist höchstens eine Antwort, die "bestimmte Unterinstanzen" abdeckt.

Juho