Effizientes Lösen eines Systems strenger linearer Ungleichungen mit allen Koeffizienten gleich 1 ohne Verwendung eines allgemeinen LP-Lösers?

Gemäß dem Titel gibt es außer der Verwendung eines Allzweck-LP-Lösers einen Ansatz zum Lösen von Ungleichungssystemen über Variablen wobei Ungleichungen die Form ? Was ist mit dem Sonderfall von Ungleichungen, die eine Gesamtordnung über die Summen der Mitglieder der Potenzmenge von ? $x_i, \ldots, x_k$ $\sum_{i \in I} x_i < \sum_{j \in J} x_j$ $\{x_i, \ldots, x_k\}$

ds.algorithms linear-algebra linear-programming Jonderry
quelle

@Ankur: Es spielt keine Rolle, ob es sich um ganze oder reelle Zahlen handelt. Wenn dies strenge Ungleichungen sind, können Sie sie zu Rationalen abrunden und sie dann mit dem kleinsten gemeinsamen Nenner multiplizieren, um eine ganzzahlige Lösung zu erhalten.

Peter Shor

Ich habe keine Ahnung, was Sie in 30 Minuten codieren können (in welcher Sprache?). Wenn das das Kriterium für „einfach“ ist, ist das dann überhaupt eine Frage in der theoretischen Informatik?

Tsuyoshi Ito

Guter Punkt Peter Shor. jonderry, ich nehme meine Aussage zurück. Ich dachte, dass das kombinatorische Problem, diese strengen Ungleichungen zu erfüllen, und das konvexe analytische Problem, einen inneren Punkt eines Kegels zu finden, qualitativ unterschiedlich sind. Ich habe mich geirrt.

Ankur

@Tsuyoshi: Es muss nicht trivial sein, aber ich bin gespannt, ob dies nach ersten Grundsätzen möglich ist, ohne die zusätzliche Leistung eines vollständigen LP-Lösers zu nutzen, insbesondere für den Sonderfall, in dem wir eine Bestellung haben aller Teilmengen-Summen (beachten Sie in diesem Fall, dass die Polynomzeit in der Anzahl der Variablen exponentiell ist).

Jonderry

Dann denke ich: "Kann dieses Problem effizient gelöst werden, ohne allgemeine Algorithmen für die lineare Programmierung zu verwenden?" ist eine gute Möglichkeit, Ihre Frage besser zu formulieren.

Tsuyoshi Ito

Antworten:

Bei Ihrer ersten Frage ohne die Gesamtreihenfolge lautet die Antwort auf Ihre Frage, dass sie im Wesentlichen so schwierig ist wie die lineare Programmierung. Hier ist ein Überblick über einen Beweis.

wir zunächst eine Variable , die wir . Wählen wir nun eine andere Variable , die wir nennen werden . Wir wollen sicherstellen, dass Berücksichtigen Sie dazu die Ungleichungen usw. Bei einer ausreichend langen Kette wird dies uns sagen, dass oder für einige sehr große ( ist eine Fibonacci-Zahl und wächst daher exponentiell in ). $x_1>0$ $\epsilon$ $x_i$ $1$

ϵ ≪ 1 .

$\epsilon \ll 1\, .$

x_{1} < x_{2},

$x_1 < x_2,$

x_{1} + x_{2} < x_{3},

$x_1 + x_2 < x_3,$

x_{2} + x_{3} < x_{4},

$x_2+x_3 < x_4,$

N x_{1} < x_{i}

$Nx_1 < x_i$

ϵ < 1 / N

$\epsilon < 1/N$

N

$N$

N

$N$

i

$i$

Wir können jetzt ein lineares Programm mit ganzzahligen Koeffizienten erstellen. Wenn wir einen Koeffizienten von 3 für , addieren wir die Ungleichungen und lassen stehen in für 3 . Wenn Sie größere Koeffizienten wünschen, können Sie diese erhalten, indem Sie die Koeffizienten in binärer Notation ausdrücken und Ungleichungen , die garantieren, dass , usw. Um die rechte Seite zu erhalten, machen wir dasselbe mit der Variablen $x_t$

x_{t} < x_{t^{'}} < x_{t^{″}} < x_{t} + ϵ

$x_t < x_{t'} < x_{t''} < x_t + \epsilon$

x_{t} + x_{t^{'}} + x_{t^{″}}

$x_t + x_{t'} + x_{t''}$

x_{t}

$x_t$

x_{u} \approx 2 x_{t}

$x_u \approx 2x_t$

x_{v} \approx 2 x_{u}

$x_v \approx 2x_u$

x_{i} = 1

$x_i = 1$ . Mit dieser Technik können wir lineare Programme der OP-Form verwenden, um die Machbarkeit für beliebige lineare Programme mit ganzzahligen Koeffizienten ungefähr zu überprüfen, eine Aufgabe, die im Wesentlichen so schwierig ist wie die lineare Programmierung.

Ich weiß nicht, wie ich die zweite Frage analysieren soll, wenn ich nach dem Fall frage, in dem es eine Gesamtreihenfolge für alle Teilmengen gibt.

Peter Shor
quelle