Gleichwertigkeit von Machbarkeitsprüfung und Optimierung für lineare Systeme

Ein Weg zu zeigen, dass die Überprüfung der Machbarkeit eines linearen Ungleichungssystems so schwierig ist wie die lineare Programmierung, ist die durch die Ellipsoidmethode gegebene Reduktion. Noch einfacher ist es, die optimale Lösung zu erraten und über die binäre Suche als Einschränkung einzuführen.

Diese beiden Reduktionen sind polynomisch, aber nicht stark polynomisch (dh sie hängen von der Anzahl der Bits in den Koeffizienten der Ungleichungen ab).

Gibt es eine stark polynomielle Reduktion von der LP-Optimierung zur LP-Machbarkeit?

ds.algorithms linear-programming Suresh Venkat
quelle

nicht wirklich. Es ist wie du sagst. Mir ist klar, dass die LP-Optimierung die LP-Machbarkeit löst. Ich bitte um die gegenteilige Ermäßigung.

Suresh Venkat

Nun, die Ausgabe für die Optimierung kann so viele Bits haben wie "die Anzahl der Bits in den Koeffizienten", während die Machbarkeit ja / nein ist. Wenn Sie also mit Reduktion etwas "Black-Box" -Ey meinen, muss die Antwort negativ sein.

Noam

Wenn die Machbarkeitsprüfung jedoch nicht nur eine Ja / Nein-Antwort gibt, wie oben von Noam erörtert, sondern im Fall der Machbarkeit eine machbare Lösung bietet, lautet die Antwort Ja, durch LP-Dualität.

Kristoffer Arnsfelt Hansen

@SureshVenkat: Angenommen, das Primale ist ein Maximierungsprogramm in Variablen

, und das Duale ist dann ein Minimierungsprogramm in Variablen

. Bilden Sie dann das Ungleichungssystem in den Variablen

, indem Sie die Bedingungen sowohl für die ursprüngliche als auch für die duale Lösung zusammen mit einer Ungleichung verwenden, die besagt, dass der Wert der ursprünglichen Lösung mindestens der Wert der dualen Lösung ist. Es kann auch auf die Fälle eingegangen werden, in denen die LP nicht realisierbar und unbegrenzt ist.

x

$x$

y

$y$

x, y

$x,y$

Kristoffer Arnsfelt Hansen

Was ist mit Polytopen / Polyedern, die durch implizite Einschränkungen definiert sind?

Chandra Chekuri

Antworten:

Die Antwort lautet ja, und tatsächlich kann man die Machbarkeit der linearen Ungleichungen sogar auf das Entscheidungsproblem reduzieren!

$\max c^Tx\ \text{s.t.}\ Ax \leq b\ ;\ x\geq 0$

Wir haben außerdem Zugang zu einem Orakel, das bei einem Ungleichungssystem ja / nein zurückgibt, ob das System durchführbar ist. $S=\{Bz \leq d\}$

Die Reduktion läuft nun wie folgt ab:

Testen Sie, ob möglich ist. Wenn nicht, können wir melden, dass P UNFÄHIG ist. $S_1=\{Ax \leq b\ ;\ x \geq 0\}$
Bilden Sie das duale Programm D: . $\min b^Ty\ \text{s.t.}\ A^Ty \geq c\ ;\ y \geq 0$
Testen Sie, ob durchführbar ist. Wenn nicht, können wir melden, dass P UNBEGRENZT ist. $S_2=\{Ax \leq b\ ;\ x\geq 0\ ;\ A^Ty\geq c\ ;\ y\geq0 \ ;\ b^Ty \leq c^Tx\}$
Iterieren Sie über die Ungleichungen von und versuchen Sie, sie einzeln als Gleichungen (dh addieren Sie die umgekehrte Ungleichung) zum System hinzuzufügen . Wenn das System durchführbar bleibt, behalten wir die Einschränkung in bei und entfernen sie ansonsten wieder. Sei das System der Randbedingungen (lineare Gleichungen), das auf diese Weise addiert wird. Das System ermittelt nun vollständig eine optimale Grundlösung für P. $S_1$ $S_2$ $S_2$ $S_3$ $S_3$
Berechnen Sie mit Hilfe der Gaußschen Elimination auf dem System eine optimale Lösung zu P. $S_3$ $x$

Kristoffer Arnsfelt Hansen
quelle

Die Schritte 4 und 5 werden nicht benötigt. Wenn machbar ist, haben wir die optimale Lösung für .

S_{2}

$S_2$

P

$P$

Hengxin

@hengxin. In der ersten Zeile meiner Antwort steht, dass die Antwort ja ist, selbst wenn man überlegt, sich auf das Entscheidungsproblem zu beschränken. Im Folgenden gehe ich offensichtlich von dieser Annahme aus und daher sind die Schritte 4 und 5 erforderlich.

Kristoffer Arnsfelt Hansen