Motivation
Diätproblem: Beim Diätproblem benötigt ein Mensch am Tag 10/15/5 Einheiten Kohlenhydrate/Proteine/Fett. Um diesen Bedarf zu decken, stehen drei Lebensmittel zur Auswahl: Eine Pizza
kostet 3 Euro und liefert 4/1/3 Einheiten. Ein Sandwich kostet 4 Euro und liefert 5/1/2 Einheiten. Ein Proteinshake kostet 6 Euro und liefert 2/10/0 Einheiten. Die Aufgabe ist es nun, solche Anzahlen
Das Problem kann man in eine lineare Kostenfunktion (Zielfunktion) mit einem linearen Ungleichungssystem (Nebenbedingungen) übersetzen, d. h. einem Halbraumschnitt. Für
Problem der linearen Programmierung: Gegeben seien
Gesucht ist
Es gibt Algorithmen, die das Problem sowohl linear in
Die optimale Lösung des Problems muss nicht eindeutig sein. Es gibt jedoch immer eine optimale Lösung, die eine Ecke des Zielbereichs ist (d. h. Schnitt von
Im Folgenden wird nur
Prune-and-Search-Algorithmus
Zweidimensionaler Fall
Prune-and-Search-Algorithmus: Seien
Der Prune-and-Search-Algorithmus unterteilt die NBen in Oben-NBen
Prune-Schritt: Beim Prune-Schritt werden zwei NBen vom gleichen Typ betrachtet, also z. B.
Search-Schritt: Der Search-Schritt implementiert das Orakel, d. h. in diesem Schritt wird für eine vertikale Gerade
Sei dazu
Liegt
unterhalb , dann schneidet den Zielbereich (der Teil von zwischen und ist zulässig). Die Steigungen der Geraden durch entscheiden nun, ob das Optimum links oder rechts von (oder auf ) liegt.Liegt
oberhalb , dann schneidet den Zielbereich nicht, dieser liegt dann vollständig auf einer Seite von . Das Optimum liegt nun auf der Seite von , auf der der Schnittpunkt der Geraden durch liegt (sind diese parallel, so ist der Zielbereich leer).
Zeitbedarf eines Search-Schritts:
naive Vorgehensweise: Wähle ein Paar von Hyperebenen, wende den Prune-Schritt an, um eine NB wegzulassen, und wiederhole. Die Laufzeit ist dann jedoch
besser:
Unterteile
und jeweils in Hyperebenen-Paare desselben Typs.Berechne den Schnittpunkt von jedem Hyperebenen-Paar sowie den
-Median der
Schnittpunkte.Wende den Search-Schritt mit der vertikalen Geraden
durch den -Median an.Entscheidet das Orakel, dass das Optimum auf einer Seite liegt (z. B. rechts), so gilt dies auch für alle Vertikalen durch die Schnittpunkte auf der anderen Seite von
(z. B. links). Daher kann man für alle Hyperebenen-Paare auf der anderen Seite den Prune-Schritt anwenden, d. h. es können der NBen weggelassen werden.Wiederhole.
Zeitbedarf:
Beweis: Die Berechnung des
Der Algorithmus funktioniert auch, wenn der Zielbereich leer ist oder nach unten unbeschränkt ist (dazu speichert man ein Intervall
Dreidimensionaler Fall
dreidimensionaler Fall: Unterteile
Search-Schritt: Es werden wieder zwei Hyperebenen vom gleichen Typ betrachtet (z. B.
Gibt es eine Lösung, so schneide die beiden
-Hyperebenen, die zu den beiden Geraden gehören, welche die -Lösung definieren. Auf der Seite der vertikalen Ebene, auf der die Schnittgerade „nach unten“ geht, liegt das -Optimum (falls es existiert).Gibt es keine Lösung, dann liefert der
-Algorithmus ein Zertifikat der Unzulässigkeit. Schneide die drei -Hyperebenen, die zu den drei Geraden des Zertifikats gehören. Auf der Seite der vertikalen Ebene, auf der der Schnittpunkt liegt, liegt das -Optimum (falls es existiert), denn der Zielbereich liegt vollständig auf dieser Seite der vertikalen Ebene.
naive Vorgehensweise: Wähle ein Paar von Hyperebenen, wende einen Prune-Schritt analog zum
besser:
Teile jeweils
und in Paare auf, schneide die Hyperebenen und erhalte Geraden im Raum.Projiziere die Geraden in die
- -Ebene.Drehe die
- -Ebene, sodass ungefähr Geraden Steigung haben und Geraden Steigung .Paare jeweils eine Gerade mit Steigung
mit einer Geraden mit Steigung und erhalte Kreuzchen (und berechne deren Schnittpunkte).Befrage das Orakel mit der vertikalen Ebene im Raum durch den
-Median der Kreuzchen-Schnittpunkte.Bilde von den Kreuzchen-Schnittpunkten auf der „falschen“ Seite des Orakels den
-Median und befrage das Orakel mit der vertikalen Ebene durch diesen Schnittpunkt (aber mit allen Hyperebenen).Ist das Optimum z. B. „rechts unten“, so kann im Kästchen „links oben“ bei jedem Kreuzchen von den vier beteiligten NBen jeweils eine NB weggelassen werden.
Zeitbedarf:
Beweis: In jedem Schritt reduziert sich die Anzahl an NBen um den Faktor
Zeitbedarf in
RIC-Algorithmus (SeidLP)
RIC-Algorithmus für LP (SeidLP): Der Einfachheit halber wird hier nur der
Permutiere die Halbräume zufällig zu
. Nimm an, dass die -Koordinate von endlich ist, wobei das Optimum der ersten NBen sei (d. h. erste beide NBen nach oben offen und Steigung von positiv und die von negativ).Füge
nacheinander hinzu und stelle sicher, dass das Optimum der bislang betrachteten NBen aufrecht erhalten wird.
Beobachtung: Gilt
Gilt
Worst-Case-Laufzeit:
Durch die Randomisierung tritt dieser Fall jedoch sehr selten ein.
Zeitbedarf:
Beweis: Sei
Das Optimum
Man erhält damit
LP-artige Probleme
Beispiele
Beispiele für LP-artige Probleme: Folgende Probleme haben viele Gemeinsamkeiten. Dazu sei
kleinster einschließender Ball: Gegeben sind
Punkte in .
Gesucht ist der kleinste -dimensionale (abgeschlossene) Ball, der alle Punkte enthält.
Es gilt .lineare Programmierung: Gegeben sind
Halbräume in .
Gesucht ist der unterste Punkt im Schnitt aller Halbräume.
Es gilt .kleinste einschließende Ellipse: Gegeben sind
Punkte in .
Gesucht ist die kleinste -dimensionale (abgeschlossene) Ellipse, die alle Punkte enthält.
Es gilt .kleinster einschließender Donut: Gegeben sind
Punkte in .
Gesucht ist der kleinste -dimensionale (abgeschlossene) Donut, die alle Punkte enthält (d. h. mengentheoretische Differenz zweier konzentrische Bälle).
Es gilt .Polyederdistanz: Gegeben sind zwei disjunkte Polyeder im
durch ihre Halbräume.
Gesucht ist die Distanz der beiden Polyeder zueinander.
Es gilt .
Manche Probleme, wie den kleinsten einschließenden Donut, kann man als LP-Problem darstellen, andere jedoch nicht, wie den kleinsten einschließenden Ball. Die Probleme sind jedoch alle „LP-artig“.
Gemeinsamkeiten:
kleine Basis: Die optimale Lösung wird nur durch wenige Eingabeobjekte bestimmt, deren Anzahl
von der Gesamtzahl an Objekten unabhängig ist.Monotonizität: Die Lösung wird nicht besser, wenn Objekte hinzugefügt werden.
Lokalität: Wenn sich die Lösung
durch Hinzufügung eines Objekts verschlechtert, verschlechtert sich auch die Lösung, wenn man das Objekt zu den Objekten hinzufügt, die definieren (die beiden „neuen“ Lösungen stimmen i. A. nicht überein!).
Definition
LP-artiges Problem: Ein LP-artiges Problem ist ein Paar einer endlichen Menge an Nebenbedingungen und der Zielfunktion mit einer total geordneten Menge,
sodass für alle
(Monotonizität) undaus
und für ein folgt,
dass (Lokalität).
Basis: Sei
kombinatorische Dimension: Die komb. Dimension von
basisregulär:
lp_type-Algorithmus
Grundoperationen auf LP-artigen Problemen: Es wird angenommen, dass folgende Grundoperationen in
Test auf Verletzung: Gilt
?Basis-Berechnung: Berechne die Basis von
von .
lp_type-Algorithmus: Der lp_type-Algorithmus berechnet aus einer Teilmenge
Prüfe, ob
.Falls ja, so gebe
zurück.Falls nein, so mache Folgendes:
Wähle
zufällig und berechne .Prüfe, ob
.Falls ja, so berechne eine Basis
von und gebe zurück.Falls nein, so gebe
zurück.
Satz (Korrektheit): Der Algorithmus terminiert stets und arbeitet korrekt.
Beweis: Beim ersten rekursiven Aufruf von lp_type verkleinert sich
Weil das Bild von
Die Korrektheit des Algorithmus ist klar: Im ersten Fall wird korrekterweise
Laufzeit des lp_type-Algorithmus
Lemma: Sei
Dann ist
Beweis: Angenommen, es gilt
Seien
erzwungen: Seien
Dann heißt
Wenn
versteckte Dimension: Seien
Nach obigem Lemma reduziert sich die versteckte Dimension bei jedem rekursiven Aufruf um mindestens
Lemma: Sei
, und .
Folgerung: Es gilt
Als Konsequenz daraus ergibt sich, dass jedes lineare Programm in