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 xp,xs,xo von Pizzen, Sandwiches und Proteinshakes zu finden, die unter den Anzahlen, die den Tagesbedarf abdecken, die Kosten minimieren.

Das Problem kann man in eine lineare Kostenfunktion (Zielfunktion) mit einem linearen Ungleichungssystem (Nebenbedingungen) übersetzen, d. h. einem Halbraumschnitt. Für d groß kann man diesen wie oben erklärt nicht vollständig ausrechnen.

Problem der linearen Programmierung: Gegeben seien cRd, ARn×d und bRn.
Gesucht ist xRd mit cTxmin, wobei Axb (Problem der linearen Programmierung).

cTx heißt Zielfunktion, die n Ungleichungen Axb heißen Nebenbedingungen (NBen) und alle Punkte xRd mit Axb heißen zulässig bzw. der Bereich heißt Zielbereich.

Es gibt Algorithmen, die das Problem sowohl linear in n als auch linear in d lösen. Im Folgenden geht es aber nur um Algorithmen, die das Problem linear in n lösen, aber mindestens exponentiell in d arbeiten.

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 d zu den NBen gehörigen Hyperebenen mit linear unabhängigen Normalenvektoren). Eine optimale Lösung wird durch höchstens d Bedingungen bestimmt.

Im Folgenden wird nur c:=(0,,0,1) betrachtet, d. h. man sucht den untersten Punkt des Zielbereichs (oBdA durch Rotation möglich). Außerdem soll die optimale Lösung immer eindeutig sein (oBdA durch kleine Rotation von c möglich).

Prune-and-Search-Algorithmus

Zweidimensionaler Fall

Prune-and-Search-Algorithmus: Seien H die n zu den NBen gehörigen Hyperebenen in R2.
Der Prune-and-Search-Algorithmus unterteilt die NBen in Oben-NBen H+ (((01)ai<0) und Unten-NBen H ((01)ai>0).

Prune-Schritt: Beim Prune-Schritt werden zwei NBen vom gleichen Typ betrachtet, also z. B. h1,h2H+. Sei die vertikale Gerade durch den Schnittpunkt von h1 und h2. Angenommen, es gäbe ein Orakel, welches mit Sicherheit entscheiden könnte, auf welcher Seite von das Optimum liegt, dann kann man eine Nebenbedingung weglassen (für h1,h2H+ kann man die Hyperebene weglassen, die auf der Optimum-Seite von unterhalb der anderen liegt).

Search-Schritt: Der Search-Schritt implementiert das Orakel, d. h. in diesem Schritt wird für eine vertikale Gerade entschieden, auf welcher Seite von das Optimum liegt.
Sei dazu p± der oberste bzw. unterste Schnittpunkt von mit Hyperebenen hH±.

  • Liegt p+ unterhalb p, dann schneidet den Zielbereich (der Teil von zwischen p+ und p ist zulässig). Die Steigungen der Geraden durch p+ entscheiden nun, ob das Optimum links oder rechts von (oder auf ) liegt.

  • Liegt p+ oberhalb p, 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 p± liegt (sind diese parallel, so ist der Zielbereich leer).

Zeitbedarf eines Search-Schritts: O(n) mit n der aktuellen Anzahl an NBen

naive Vorgehensweise: Wähle ein Paar von Hyperebenen, wende den Prune-Schritt an, um eine NB wegzulassen, und wiederhole. Die Laufzeit ist dann jedoch i=1nO(i)=O(n2).

besser:

  • Unterteile H+ und H jeweils in Hyperebenen-Paare desselben Typs.

  • Berechne den Schnittpunkt von jedem Hyperebenen-Paar sowie den x-Median der
    Schnittpunkte.

  • Wende den Search-Schritt mit der vertikalen Geraden durch den x-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 14 der NBen weggelassen werden.

  • Wiederhole.

Zeitbedarf: O(n)

Beweis: Die Berechnung des x-Medians und das Befragen des Orakels sind linear in der Anzahl an NBen. In jedem Schritt reduziert sich die Anzahl an NBen ungefähr um den Faktor 14. Damit ist der Zeitbedarf O(i=0n(34)i)=O(n).   ƒ

Der Algorithmus funktioniert auch, wenn der Zielbereich leer ist oder nach unten unbeschränkt ist (dazu speichert man ein Intervall [L,R], sodass das Optimum in [L,R] ist, falls es existiert, anfangs [L,R]=[,], dann immer weiter verkleinern). Im ersten Fall liefert der Algorithmus ein Zertifikat der Unzulässigkeit (d. h. drei Halbräume mit leerem Schnitt).

Dreidimensionaler Fall

dreidimensionaler Fall: Unterteile H wie im R2-Fall in H+ und H.

Search-Schritt: Es werden wieder zwei Hyperebenen vom gleichen Typ betrachtet (z. B.
h1,h2H+). Berechne die Schnittgerade der beiden Ebenen und bilde die vertikale Ebene durch die Schnittgerade. Schneide nun alle Hyperebenen mit der vertikalen Ebene, dabei kommt ein zweidimensionales LP-Problem heraus, was mit obigem Algorithmus gelöst werden kann.

  • Gibt es eine Lösung, so schneide die beiden R3-Hyperebenen, die zu den beiden Geraden gehören, welche die R2-Lösung definieren. Auf der Seite der vertikalen Ebene, auf der die Schnittgerade „nach unten“ geht, liegt das R3-Optimum (falls es existiert).

  • Gibt es keine Lösung, dann liefert der R2-Algorithmus ein Zertifikat der Unzulässigkeit. Schneide die drei R3-Hyperebenen, die zu den drei Geraden des Zertifikats gehören. Auf der Seite der vertikalen Ebene, auf der der Schnittpunkt liegt, liegt das R3-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 R2-Fall an, um eine NB wegzulassen, und wiederhole. Die Laufzeit ist dann jedoch i=1nO(i)=O(n2).

besser:

  • Teile jeweils H+ und H in Paare auf, schneide die Hyperebenen und erhalte n2 Geraden im Raum.

  • Projiziere die Geraden in die x-y-Ebene.

  • Drehe die x-y-Ebene, sodass ungefähr n4 Geraden Steigung >0 haben und n4 Geraden Steigung <0.

  • Paare jeweils eine Gerade mit Steigung >0 mit einer Geraden mit Steigung <0 und erhalte n4 Kreuzchen (und berechne deren Schnittpunkte).

  • Befrage das Orakel mit der vertikalen Ebene im Raum durch den y-Median der Kreuzchen-Schnittpunkte.

  • Bilde von den Kreuzchen-Schnittpunkten auf der „falschen“ Seite des Orakels den x-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: O(n)

Beweis: In jedem Schritt reduziert sich die Anzahl an NBen um den Faktor 116, d. h. es bleiben nur 1516 der NBen übrig. Damit ist der Zeitbedarf O(i=0n(1516)i)=O(n).   ƒ

Zeitbedarf in d Dimensionen: O(2O(2d)n)

RIC-Algorithmus (SeidLP)

RIC-Algorithmus für LP (SeidLP): Der Einfachheit halber wird hier nur der R2-Fall betrachtet. Der SeidLP-Algorithmus ist nach Raimund Seidel benannt und funktioniert wie folgt:

  • Permutiere die Halbräume zufällig zu h1,,hn. Nimm an, dass die y-Koordinate von v2 endlich ist, wobei vi:=v({h1,,hi})R2 das Optimum der ersten i NBen sei (d. h. erste beide NBen nach oben offen und Steigung von h1 positiv und die von h2 negativ).

  • Füge h3,,hn nacheinander hinzu und stelle sicher, dass das Optimum der bislang betrachteten NBen aufrecht erhalten wird.

Beobachtung: Gilt vihi+1, dann gilt vi+1=vi.
Gilt vihi+1, dann gilt vi+1hi+1, d. h. vi+1 ist der Punkt auf hi+1 mit minimaler y-Koordinate, der die NBen h1,,hi erfüllt. In diesem Fall löst man daher ein eindimensionales LP-Problem durch den Schnitt von {h1,,hi} mit hi+1 in der Zeit O(i).

Worst-Case-Laufzeit: O(n2) (wenn in jedem Schritt der zweite Fall eintritt)

Durch die Randomisierung tritt dieser Fall jedoch sehr selten ein.

Zeitbedarf: O(n)

Beweis: Sei T(n) die Zeit, die der Algorithmus für n Hyperebenen benötigt. Dann gilt
T(n)=O(1)+i=3n(P(vi1hi)O(1)+P(vi1hi)O(i))=O(n)+i=3nP(vi1hi)O(i), wobei P(vi1hi) die Wahrscheinlichkeit ist, dass vi1 nicht die i-te NB erfüllt (d. h. dass der zweite Fall eintritt).

Das Optimum vi1 ist immer durch genau zwei bestimmte Hyperebenen definiert. Mit Rückwärtsanalyse ist die gesuchte Wahrscheinlichkeit gleich der, dass nach dem Einfügen der i-ten Hyperebene die letzte eingefügte Hyperebene eine von diesen zwei Hypereben war. Weil die Hyperebenen zufällig permutiert sind, folgt daher P(vi1hi)=2i.

Man erhält damit T(n)=O(n)+i=3n2iO(i)=O(n).   ƒ

LP-artige Probleme

Beispiele

Beispiele für LP-artige Probleme: Folgende Probleme haben viele Gemeinsamkeiten. Dazu sei δ die Zahl an Objekten, die die optimale Lösung bestimmen (d. h. wenn man eines von den Objekten weglässt, verbessert sich die Lösung).

  • kleinster einschließender Ball: Gegeben sind n Punkte in Rd.
    Gesucht ist der kleinste d-dimensionale (abgeschlossene) Ball, der alle Punkte enthält.
    Es gilt δd+1.

  • lineare Programmierung: Gegeben sind n Halbräume in Rd.
    Gesucht ist der unterste Punkt im Schnitt aller Halbräume.
    Es gilt δ=d.

  • kleinste einschließende Ellipse: Gegeben sind n Punkte in Rd.
    Gesucht ist die kleinste d-dimensionale (abgeschlossene) Ellipse, die alle Punkte enthält.
    Es gilt δ=d(d+3)2.

  • kleinster einschließender Donut: Gegeben sind n Punkte in Rd.
    Gesucht ist der kleinste d-dimensionale (abgeschlossene) Donut, die alle Punkte enthält (d. h. mengentheoretische Differenz zweier konzentrische Bälle).
    Es gilt δ=d+2.

  • Polyederdistanz: Gegeben sind zwei disjunkte Polyeder im Rd durch ihre Halbräume.
    Gesucht ist die Distanz der beiden Polyeder zueinander.
    Es gilt δ=d+1.

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 n 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 L durch Hinzufügung eines Objekts verschlechtert, verschlechtert sich auch die Lösung, wenn man das Objekt zu den δ Objekten hinzufügt, die L definieren (die beiden „neuen“ Lösungen stimmen i. A. nicht überein!).

Definition

LP-artiges Problem: Ein LP-artiges Problem ist ein Paar (H,w) mit

  • H einer endlichen Menge an Nebenbedingungen und

  • w:P(H)W{±} der Zielfunktion mit W einer total geordneten Menge,

sodass für alle F,GH mit FG gilt, dass

  • w(F)w(G) (Monotonizität) und

  • aus w(F)=w(G)> und w(G{h})>w(G) für ein hH folgt,
    dass w(F{h})>w(F) (Lokalität).

Basis: Sei GH. Dann heißt die kleinste Teilmenge B von G mit w(B)=w(G) Basis von G.

kombinatorische Dimension: Die komb. Dimension von (H,w) ist δ:=maxBasis B|B|.

basisregulär: (H,w) heißt basisregulär, falls |B|=δ für jede Basis B.

lp_type-Algorithmus

Grundoperationen auf LP-artigen Problemen: Es wird angenommen, dass folgende Grundoperationen in O(1) Zeit zur Verfügung stehen. Gegeben sei eine Basis B und eine NB hH.

  • Test auf Verletzung: Gilt w(B{h})>w(B)?

  • Basis-Berechnung: Berechne die Basis von B von B{h}.

lp_type-Algorithmus: Der lp_type-Algorithmus berechnet aus einer Teilmenge GH und einer Basis CG einer Teilmenge GG eine Basis von G und gibt sie zurück.

  • Prüfe, ob G=C.

    • Falls ja, so gebe C zurück.

    • Falls nein, so mache Folgendes:

      • Wähle hGC zufällig und berechne C:=lp\_type(G{h},C).

      • Prüfe, ob w(C{h})>w(C).

        • Falls ja, so berechne eine Basis C von C{h} und gebe lp\_type(G,C) zurück.

        • Falls nein, so gebe C zurück.

Satz (Korrektheit): Der Algorithmus terminiert stets und arbeitet korrekt.

Beweis: Beim ersten rekursiven Aufruf von lp_type verkleinert sich |G| und C bleibt gleich. Induktiv terminiert dieser Aufruf. Beim zweiten rekursiven Aufruf bleibt zwar G gleich, aber die „Lücke“ w(G)w(C) zum Optimum verkleinert sich, da
w(C)=w(C{h})>w(C)=w(G{h})w(C).
Weil das Bild von P(H) unter w endlich ist, kann w(G)w(C) nur endlich viele Werte annehmen, womit dieser Aufruf induktiv ebenfalls terminiert.

Die Korrektheit des Algorithmus ist klar: Im ersten Fall wird korrekterweise G=C zurückgegeben, im zweiten Fall lp\_type(G,C) (was induktiv korrekt ist) oder C, was ebenfalls korrekt ist, da in diesem Fall w(C{h})=w(C) gilt und nach der Lokalität
w(G)=w((G{h}){h})=w(G{h}) folgt (d. h. C ist auch eine Basis von G).   ƒ

Laufzeit des lp_type-Algorithmus

Lemma: Sei w(C{h})>w(C) im lp_type-Algorithmus.
Dann ist hC und h taucht in allen Basen aller rekursiven Aufrufe auf.

Beweis: Angenommen, es gilt hC, dann wäre CC und daher w(C)w(C), ein Widerspruch zu w(C)=w(C{h})>w(C).

Seien C0G{h} eine Basis, die h nicht enthält, und C1 eine Basis, die während lp\_type(G,C) auftritt. Dann gilt w(C1)w(C)=w(C{h})>w(C)=w(G{h})w(C0), d. h. C0 und C1 können nicht gleich sein.   ƒ

erzwungen: Seien CGH und hG.
Dann heißt h in (G,C) erzwungen, falls w(C)>w(G{h}).

Wenn h in (G,C) erzwungen ist, dann gilt zwangsläufig hC. Die erzwungenen Elemente von C sind die Elemente, von denen man bereits weiß, dass sie zur Basis von G gehören.

versteckte Dimension: Seien CGH und hG. Dann heißt
δ(G,C):=δ|{hG|h erzwungen in (G,C)} die versteckte Dimension von (G,C).

Nach obigem Lemma reduziert sich die versteckte Dimension bei jedem rekursiven Aufruf um mindestens 1. Man kann zeigen, dass sich die versteckte Dimension erwartet sogar halbiert.

Lemma: Sei t(k,n) die erwartete Anzahl an Verletzungstests bei Aufruf von lp\_type(G,C) mit |G|=n und δ(G,C)=k. Dann gilt

  • t(δ,0)=0,

  • t(n,0)=nδ und

  • t(n,k)t(n1,k)+1+knδt(n,k1).

Folgerung: Es gilt t(n,k)j=1k1j!k!(nδ)ek!(nδ)=O(n).

Als Konsequenz daraus ergibt sich, dass jedes lineare Programm in d Variablen mit n Nebenbedingungen erwartet in der Zeit O(d!d3n) gelöst werden kann.