Randomisierte Rundung von Lösungen zu linearen Programmen

Question

Ganzzahl lineare Programmierung (ILP) ist ein unglaublich leistungsfähiges Werkzeug für die kombinatorische Optimierung. Wenn wir ein Problem als Instanz eines ILP formulieren können, finden Löser garantiert das globale Optimum. Die Durchsetzung von Integral Solutions hat jedoch eine Laufzeit, die im schlimmsten Fall exponentiell ist. Um mit dieser Barriere fertig zu werden, können mehrere Annäherungsmethoden im Zusammenhang mit ILPs verwendet werden.

• Primal-Dual-Schema
• Randomisierte Rundung

Das ursprüngliche Schema ist eine vielseitige Methode, die uns eine "verpackte" Möglichkeit gibt, einen gierigen Algorithmus zu finden und seine Annäherungsgrenzen mit der entspannten Dual-LP zu beweisen. Die resultierenden kombinatorischen Algorithmen sind in der Regel sehr schnell und funktionieren in der Praxis recht gut. Die Beziehung zur linearen Programmierung ist jedoch näher mit der Analyse verbunden. Aufgrund dieser Analyse können wir leicht zeigen, dass Einschränkungen nicht verletzt werden.

Randomisierte Rundung erfordert einen anderen Ansatz und löst die entspannte LP (unter Verwendung von Innen- oder Ellipsoidmethoden) und rundet Variablen gemäß einer Wahrscheinlichkeitsverteilung. Wenn Annäherungsgrenzen nachgewiesen werden können, dass diese Methode wie das ursprüngliche Dualschema sehr nützlich ist. Ein Teil ist mir jedoch nicht ganz klar:

Wie zeigen randomisierte Rundungsschemata, dass Einschränkungen nicht verletzt werden?

Es scheint, dass naiv eine Münze umgedreht, während sie zu einer 0: 1-Lösung führt, die Einschränkungen verletzen könnte! Jede Hilfe, die dieses Problem beleuchtet, wäre geschätzt. Vielen Dank.

Answer 1

Wenn Sie umrunden, müssen Sie natürlich überprüfen, ob die Rundung die Machbarkeit bewahrt.

Betrachten wir zum Beispiel die entspannt LP-Formulierung von Scheitelpunktbedeckungen. $$ begin {array} {lll} text {min} & sum_ {v in v} c (v) x_v & text {st} & x_u+x_v ge1 & quad (u, v ) in e & x_v ge 0. & quad v in v end {Array} $$

Es ist bekannt, dass die Lösung für dieses Problem halbintegral ist, dh jede Variable beträgt entweder $ 0 $, $ 1 $ oder 1/2 $. Das Rundungsschema funktioniert wie folgt, wenn Ihre Lösung $ x_V = 1/2 $ enthält zusammenfassen und setzen Sie $ x_v = 1 $. Die Einschränkungen des ILP waren $$ begin {array} {lll} & x_u+x_v ge1, & quad (u, v) in e & x_v in {0,1 }. & quad v in v end {Array} $$ Beide Einschränkungen werden nach der Rundung erfüllt. Und Sie haben eine schöne 2-Anerkennung.

Answer 2

Ja, das ist verwirrend im ersten Blick.

Ich sehe es so:

STEP1) Generieren Sie eine lineare Programmlösung [alle linearen Programmbeschränkungen sind hier erfüllt - außer dass es sich nicht um eine ganzzahlige Lösung handelt].

Schritt2) Randomisieren Sie es (ändern Sie den Wert auf Ganzzahlen gemäß einer von Ihnen ausgewählten Wahrscheinlichkeitsverteilung).

Schritt 3) Stellen Sie sicher, dass die randomisierte Lösung korrekt ist (indem Sie nur wenige Änderungen vornehmen).

Zum Beispiel in der SET-Cover. Nach der Randomisierung können Sie eine Sammlung von Sets erhalten, die nicht unbedingt ein festgelegter Cover sind. In diesem Fall sollten Sie einige Sets hinzufügen, die alle unbedeckten Elemente abdecken (und somit die gewünschte Lösung erhalten).

Um so große Änderungen in der randomisierten linearen Programmlösung zu vermeiden, befolgen Sie ein randomisiertes Rundungsschema, das mit hoher Wahrscheinlichkeit garantiert, dass eine Lösung nach der Runden gefunden wird (dh Sie müssen nicht viele Änderungen in der linearen Programmlösung vornehmen, um das zu erhalten, was Sie erhalten wollen).

Sehen Sie dies als Referenz: 1