Ganzzahlige Programmierung mit einer festen Anzahl von Variablen

Die berühmte Arbeit von H. Lenstra aus dem Jahr 1983 über die Ganzzahlprogrammierung mit einer festen Anzahl von Variablen besagt, dass Ganzzahlprogramme mit einer festen Anzahl von Variablen zeitpolynomiell in der Länge der Daten lösbar sind.

Ich interpretiere das wie folgt.

Ganzzahlige Programmierung ist im Allgemeinen immer noch NP-vollständig, aber wenn meine typische Problemgröße (sagen wir etwa 10.000 Variablen, eine beliebige Anzahl von Einschränkungen) in der Praxis realisierbar ist, dann könnte ich einen Algorithmus konstruieren, der polynomiell in der Anzahl von Einschränkungen skaliert, jedoch nicht in die Anzahl der Variablen und Nebenbedingungen.
Das Ergebnis kann auch für die Binärprogrammierung verwendet werden, da ich eine beliebige Ganzzahl durch Hinzufügen einer entsprechenden Einschränkung auf 0-1 setzen kann.

Ist meine Interpretation korrekt?

Hat dieses Ergebnis praktische Auswirkungen? Gibt es also eine Implementierung oder wird sie in gängigen Solvern wie CPLEX, Gurobi oder Mosek verwendet?

Einige Zitate aus dem Papier:

Diese Länge kann für unsere Zwecke als n · m · log (a + 2) definiert werden, wobei a das Maximum der Absolutwerte der Koeffizienten von A und b bezeichnet. In der Tat ist es wahrscheinlich, dass kein derartiger Polynomalgorithmus existiert, da das fragliche Problem NP-vollständig ist

[...]

Es wurde vermutet [5], [10] dass für jeden festen Wert von n ein Polynomalgorithmus zur Lösung des ganzzahligen linearen Programmierproblems existiert. In der vorliegenden Arbeit beweisen wir diese Vermutung, indem wir einen solchen Algorithmus zeigen. Der Grad des Polynoms, durch den die Laufzeit unseres Algorithmus begrenzt werden kann, ist eine Exponentialfunktion von n.

co.combinatorics linear-programming integer-programming Bernhard Kausler
quelle

"Ich könnte einen Algorithmus konstruieren, der polynomiell in der Anzahl der Bedingungen oder Variablen skaliert , aber nicht in der Anzahl der Variablen und Bedingungen." Interessanter Punkt / Frage - Bisher haben wir gesehen, dass dies für Einschränkungen gilt (wobei die Anzahl der Variablen feststeht), aber es wäre vielleicht interessant zu fragen, ob dies auch für Variablen gilt (wobei die Anzahl der Einschränkungen feststeht) ? Intuitiv fühlt es sich so an, als ob es nicht wahr sein sollte, sonst wäre IP im Allgemeinen polytime, aber ich bin mir nicht sicher.

Usul

In Abschnitt 4 der Arbeit stellt Lenstra fest, dass "das ganzzahlige lineare Programmierproblem mit einem festen Wert von m polynomiell lösbar ist". (m ist die Anzahl der Beschränkungen) Dies folgt als eine Folge des Hauptergebnisses. Dieser Abschnitt ist mir nicht klar. Bei einem zweiten Gedanken nimmt er vielleicht festes n UND m an; Das heißt, es ist ein Polynom in "a" (dem Maximum der absoluten Werte der Koeffizienten von A und b). (Ich habe den Teil "oder Variablen" aus meiner obigen Frage entfernt).

Bernhard Kausler

@usul: Es ist wahr und es bedeutet nicht, dass IP polytime ist. es bedeutet nur, dass es einen Algorithmus gibt, der Exponentialzeit in

und Polynom in

und einen anderen, der Exponentialzeit in

und Polynom in

n

$n$

m

$m$

m

$m$

n

$n$

Sasho Nikolov

Antworten:

Der derzeit schnellste Algorithmus ist in der Länge des ganzzahligen linearen Programms für jeden festen Wert von linear . In seiner Doktorarbeit fasst Lokshtanov (2009) die Ergebnisse von Lenstra (1983), Kannan (1987) und Frank & Tardos (1987) anhand des folgenden Theorems gut zusammen. $n$

Die ganzzahlige lineare Programmierung kann mit arithmetischen Operationen und Raumpolynom in gelöst werden . Hier ist die Anzahl der Bits im Eingang und die Anzahl der Variablen im ganzzahligen linearen Programm. $O(n^{2.5n+o(n)} \cdot L)$ $L$ $L$ $n$

Somit ist das Problem linear durch die Anzahl der Variablen fest parametrisiert.

1) Ja, die ganzzahlige lineare Programmierung ist "noch" NP-vollständig. Die Laufzeit des obigen theoretischen Ergebnisses hängt nur linear von der Anzahl der Abhängigkeiten ab, sodass die Anzahl der Abhängigkeiten gut skaliert. Ich kenne jedoch keine tatsächliche Implementierung dieses Algorithmus.

2) Ja, die Variablen binäre Werte annehmen zu lassen, ist, wie Sie gesehen haben, ganz einfach.

$L$

Ö (2^{n} n m + 8^{n} n \sqrt{m Log m} Log m + n^{2.5 n + Ö (n)} s Log m)

$O(2^nnm + 8^n n \sqrt{m \log m} \log m + n^{2.5n+o(n)}s\log m)$

m

$m$

s

$s$

Serge Gaspers
quelle

Ah, danke für den Begriff "linearer Festparameter". Darum geht es in Lenstras Artikel. Siehe auch: en.wikipedia.org/wiki/Parameterized_complexity

Bernhard Kausler

n

$n$

O (n 2^{n} m)

$O(n2^n m)$

T (n, m, s)

$T(n,m,s)$

n

$n$

m

$m$

s

$s$

O (2^{n} m + (\log m) T (n, f (n), s)

$O(2^n m + (\log m)T(n, f(n),s)$

O (s)

$O(s)$

f (n)

$f(n)$

n^{O (n)}

$n^{O(n)}$

Dies ändert nichts an den grundlegenden Fakten Ihrer Antwort. Eine weitere relevante Referenz ist KL Clarkson. Las Vegas-Algorithmen für lineare und ganzzahlige Programmierung bei kleinen Dimensionen. J. ACM 42 (2): 488–499, 1995, doi: 10.1145 / 201019.201036.

David Eppstein

m

$m$

n

$n$

O (n^{2.5 n + o (n)} L)

$O(n^{2.5n+o(n)} L)$

T (n, f (n), s)

$T(n,f(n),s)$

f (n) = 4^{n}

$f(n)=4^n$

L = 4^{n} s

$L=4^n s$

f (n)

$f(n)$

O (2^{n} n m + n^{2.5 n + o (n)} (\log m) s)

$O(2^nnm+n^{2.5n+o(n)}(\log m) s)$

Hier sind einige Punkte in Bezug auf die praktischen Auswirkungen von Ergebnissen vom Typ Lenstra und mögliche Implementierungen in CPLEX, Gurobi usw. Einer der wichtigsten Schritte in den meisten solchen Algos für IP ist die Verzweigung in "gute" oder "dünne" Richtungen. dh Hyperebenen, entlang derer die Breite des Polytops nicht zu groß ist (Polynom in Variablen und Datengröße). Aber Mahajan und Ralphs (Preprint hier ) haben gezeigt , dass das Problem der Auswahl eine optimale Disjunktion ist NP-vollständig. Es erscheint daher schwierig, praktisch effiziente Implementierungen dieser Algoklasse zu erstellen.

Die meisten in Paketen wie CPLEX implementierten Algos könnten als Branch-and-Cut-Methoden klassifiziert werden. Diese Familie von Techniken eignet sich in der Regel gut für IP-Instanzen, die durchführbar sind und häufig nahezu optimale Lösungen finden. Der Fokus von Algen vom Typ Lenstra liegt jedoch auf IP-Instanzen im ungünstigsten Fall, die zunächst nicht realisierbar sind, und das Ziel besteht darin , ihre ganzzahlige Unrealisierbarkeit zu beweisen (und die Komplexität dieser Aufgabe zu untersuchen). AFAIK, es gibt keine Klasse von Problemen mit praktischer Relevanz, die zu dieser Beschreibung passen. Daher würden CPLEX / Gurobi-Leute wahrscheinlich bald keine Algen vom Typ Lenstra mehr implementieren.

kbala
quelle