Optimierung

Zusammenfassung

Inhalte

1. Lineare Programmierung 2. Simplexalgorithmus 3. Ellipsoidmethode 4. Dualität 5. Ganzzahligkeit 6. Facility Location 7. Randomisiertes Runden 8. Branch and Bound & Heuristiken 9. Selfish Flows, Spieltheorie&Optimierung

2

• Kanonische Form: Maximiere 𝑐𝑇𝑥 unter 𝐴𝑥 ≤ 𝑏, 𝑥 ≥ 0. – Probleme als LP modellieren – Transformation beliebiger LPs in die

kanonische Form

• Geometrische Anschauung: – Nebenbedingungen definieren

Halbräume – Gleichungen entsprechen Hyperebenen – Lösungspolyhedron 𝒫

• Lösungsraum konvex • Lokales Optimum auch global optimal

3

1. Lineare Programmierung

• Optimum ist ein Knoten („Eckpunkt“)

• Idee des SIMPLEX Algorithmus: Lokale Suche über die Knoten

1. Bestimme einen beliebigen Knoten 𝑣 von 𝒫.

2. Falls es keine verbessernde Kante inzident zu 𝑣 gibt, dann ist 𝑣 optimal, stopp.

3. Folge einer beliebigen verbessernden Kante 𝑒 von 𝑣. Falls 𝑒 unbeschränkt ist so ist das LP unbeschränkt, stopp.

4. Sei 𝑢 der andere Endpunkt von 𝑒. Setze 𝑣 = 𝑢. Gehe zu Schritt 2.

4

2. Simplexalgorithmus

Simplex im Rechner

• Umwandlung des LP in Gleichungsform. • Eine Auswahl von genau 𝒎 Spalten 𝑩 ist eine Basis falls die

Vektoren in B linear unabhängig sind. • Basis: 𝐴𝐵𝑥𝐵 + 𝐴𝑁𝑥𝑁 = 𝑏 • Gleichungssytem von links mit 𝐴𝐵

−1 multiplizieren und erhalte Â𝑥 = 𝑏 bzw.

𝑥𝐵 + Â𝑁𝑥𝑁 = 𝑏

• 𝑥𝐵 = 𝑏 − Â𝑁𝑥𝑁, Basisvariablen als Funktion der NBV.

• für 𝑥𝑁 = 0 ist dann 𝑥𝐵 = 𝑏 und wir erhalten die Basislösung 𝑥𝐵 , 𝑥𝑁 = (𝑏 , 0).

• Basislösungen entsprechen Schnittpunkten von d Nebenbedingungen des entprechenden kanonischen LPs.

5

Reduzierte Kosten und Pivotschritt Reduzierte Kosten

𝑐𝑗 − 𝑐𝐵 𝑘 â𝑘𝑗

𝑚

𝑘=1

Satz 2.1 Falls der Vektor der reduzierten Kosten zu einer Basis 𝐵 keinen positiven Eintrag enthält, so ist 𝐵 optimal. Pivotschritt: Eingangspivotspalte j: Spalte mit positiven reduzierten Kosten. Ausgangspivotspalte 𝑖:

• Fall 1: Alle â𝑖𝑗 ≤ 0. 𝑥𝑗 kann beliebig erhöht werden. LP unbeschränkt.

• Fall 2: Es gibt mindestens ein 𝑖 ∈ {1, … ,𝑚} mit â𝑖𝑗 > 0. Wähle

i = argmin1≤𝑘≤𝑚 𝑏 𝑘

â𝑘𝑗∣ â𝑘𝑗 > 0

Und setzte 𝑥𝑗 =𝑏 𝑖

â𝑖𝑗 .

6

Initiale Basislösung, Komplexität und Laufzeit

• Initiale Basislösung durch ein HilfsLP

• Zahlen wachsen von 𝛼 auf höchstens 𝛼𝑚 𝑚+1 im Laufe des Algorithmus, Cramersche Regel

• Pivotschritt deshalb in polynomieller Zeit durchführbar.

• Anzahl der Pivotschritte im Worst-Case aber exponentiell. (Klee-Minty-Cube)

• Simplex ist kein Polynomzeitalgorithmus!

7

Degenerierte LPs

• Bei degenerierten LP kann es vorkommen, dass in einem Pivotschritt eine oder mehrere Basisvariablen den Wert 0 haben.

• Wenn man die falschen Spalten austauscht so terminiert der Simplexalgorithmus nicht.

Lösungen: 1. Blands Pivotregel:

– Wähle die Eingangsspalte 𝐴𝑗 und die Ausgangsspalte 𝐴𝐵(𝑖), mit möglichst kleinem Index.

2. Pertubierung

8

Pertubierung

Satz 2.4 Es gibt ein 𝛿 > 0, so dass für jedes 𝜖 ∈ (0, 𝛿) gilt:

a) 𝐿𝑃(𝜖) ist nicht-degeneriert.

b) Jede zulässige Basis für 𝐿𝑃(𝜖) ist auch zulässig für LP.

c) Jede optimale Basis für 𝐿𝑃(𝜖) ist auch optimal für LP.

Bemerkung 2.5 Sei 𝛼 der Absolutwert des größten Nenners bzw. Zählers der Eingabezahlen

von LP. Die Aussagen in Satz 2.4 gelten für

𝜖 =1

2𝛼𝑚 −2𝑚. Die Eingabelänge von 𝐿𝑃(𝜖) ist damit

polynomiell in der Eingabelänge von LP beschränkt

9

3.Ellipsoidmethode

• Ellipsoidmethode – Zulässigkeitstest

• Transformationsschritte – Innere und Äußere Kugel

• Methode: – Durch Mittelpunklt verletzte Nebenbedingung – Halbraum H – E-halbe – Ellipse E’

• Gesamtlaufzeit: Volumenargument

10

Zulässigkeit vs. Optimieren

Satz 3.1 Existiert ein polynomieller Algorithmus 𝒜, der entscheidet, ob ein System von linearen Ungleichungen eine Lösung besitzt, so existiert auch ein polynomieller Algorithmus zur Lösung von LPs.

Beweisidee: Zielfunktionsschranke als Nebenbedingung.

- Binäre Suche.

- Größe der Eingabe (-zahlen) beachten.

11

Der Zuässigkeitstest 𝒜

Vorbereitung: Lemma 3.3 Ein lineares Ungleichungssystem LI der Eingabelänge L kann in polynomieller Zeit in ein lineares Ungleichungssystem LI* mit den folgenden Eigenschaften transformiert werden. a) LI* hat genau dann eine Lösung, wenn LI eine Lösung hat. b) Der Lösungsraum von LI* ist in einer Kugel um den

Ursprung mit Radius höchstens 2𝑂(𝐿2) enthalten. c) Wenn der Lösungsraum von LI* nicht leer ist, so enthält er

eine Kugel mit Radius mindestens 2−𝑂 𝐿4 d) Die Eingabelänge von LI* ist beschränkt durch 𝑂(𝐿2).

15

Die Schritte 1. Initiale Ellipsoid 𝐸: Kugel um den Ursprung mit Radius 𝑢.

Nach Annahmen ist nach diesem Schritt 𝑆 in 𝐸 enthalten. 2. Falls das Volumen von 𝐸 kleiner als das Volumen der Kugel

mit Radius 𝑙 ist, terminiere mit der Ausgabe 𝑆 = ∅ . 3. Sei 𝑧 der Mittelpunkt von 𝐸. Wir testen, ob 𝑧 ∈ 𝑆, d.h. ob

𝑧 alle Nebenbedingungen erfüllt. Falls ja, terminiere mit der Ausgabe 𝑆 ≠ ∅.

4. Identifizieren einen Halbraum 𝐻 der 𝑆 enthält: – Wähle Ungleichung die von 𝑧 verletzt wird. – Verschiebe die dazugehörige Hyperebene parallel so,

dass sie durch z verläuft. – Bezeichne die Seite auf der S liegt mit 𝐻 sowie den

Schnitt von H und E mit E-halbe. – Berechne nun die kleinste Ellipse 𝐸′ die E-halbe enthält.

5. Setzt 𝐸 = 𝐸‘ und gehe zu Schritt 2.

16

Laufzeit Volumenargument

Lemma 3.4 Für den in Schritt 4 berechneten Ellipsoid 𝐸′ gilt

𝑣𝑜𝑙 𝐸′ ≤𝑣𝑜𝑙 𝐸

21

2 𝑛+1

.

Beweis nur für Dimension 𝑛 = 2 und 𝑛 = 3.

• Annahme E ist Kreis mit Radius 1 und Mittelpunkt (0,0) und H ist der Halbraum links der y-Achse….

17

4. Dualität

Definition 4.1 Wir betrachten das folgende LP in der kanonischen Form

Maximiere cTx unter Ax ≤ b, x ∈ ℝ≥0d .

Die Anzahl der Nebenbedingungen (ohne die Nichtnegativitätsbedingungen) sei m. Dieses LP bezeichnen wir als primales LP. Das zugehörige duale LP ist definiert als

Minimiere yTb unter yTA ≥ cT , y ∈ ℝ≥0m

oder äquivalent Minimiere bTy unter ATy ≥ cT , y ∈ ℝ≥0

m .

18

Schwache Dualität

Satz 4.2

Das duale LP des dualen LPs ist das primale LP.

Satz 4.3 (Schwaches Dualitätsprinzip)

Sei 𝑥 eine zulässige Lösung für das primale LP und 𝑦 eine zulässige Lösung für das duale LP. Es gilt 𝑦𝑇𝑏 ≥ 𝑐𝑇𝑥.

19

Das starke Dualitätsprinzip

Satz 4.4 Sei 𝑥 eine optimale Lösung für das primale LP und 𝑦 eine optimale Lösung für das duale LP. Es gilt 𝑦𝑇𝑏 = 𝑐𝑇𝑥. Beweisidee: 1. Gleichungsform, x* optimale Lösung 2. Kosten von x* hängen nur von den (nicht-Schlupf-)

Basisvariablen ab. 3. Vektor der reduzierten Kosten gibt uns 2 Ungleichungen 4. Konstruiere y*, Gleicher Wert, nutze die Ungleichungen

aus 3. um Zulässigkeit zu zeigen

20

Anmerkungen • Nicht nur gleicher Zielfunktionswert:

– Wir können aus optimaler primalen Basislösung eine optimale duale Basislösung konstruieren.

– Laufzeit 𝑂(min 𝑚3, 𝑑3 ), für die Berechnung von 𝐴11

−1.

• Komplementärer Schlupf (complementary slackness) 𝑥 und 𝑦 sind optimal, genau dann wenn

𝑦𝑖 𝑎𝑖𝑇𝑥 − 𝑏𝑖 = 0 für alle 𝑖 = 1,… ,𝑚 und (1)

𝑐𝑗 − 𝐴𝑗𝑇𝑦 𝑥𝑗 = 0 für alle 𝑗 = 1,… , 𝑛. (2)

21

5. Ganzzahligkeit

• Integer Linear Programs

• Im Allgemeinen NP-schwer

22

Lösungsraum 𝐴𝑥 = 𝑏, 𝑥 ≥ 0

LP Optimum

ILP Optimum

Zielfunktion

Totale Unimodularität (Gleichungsform)

Definition 5.1 Eine ganzzahlige quadratische Matrix wird als unimodular bezeichnet, wenn ihre Determinante den Wert 1 oder −1 hat. Eine ganzzahlige Matrix 𝐴 wird als total unimodular bezeichnet, wenn jede quadratische, reguläre Teilmatrix von 𝐴 unimodular ist. Satz 5.2 Betrachte ein LP in Gleichungsform Ax = b. Ist A total unimodular, so sind alle Basislösungen dieses LPs ganzzahlig.

23

Beweis Satz 5.2 • Sei 𝐵 eine Basis von 𝐴. • Die Basislösung zu 𝐵 wird durch die Gleichung 𝐴𝐵𝑥𝐵 =

𝑏 beschrieben. • Die Matrix 𝐴𝐵 ist dabei eine quadratische Teilmatrix von 𝐴, die

durch die Spalten in 𝐵 gebildet wird. • Das Umsortieren der Spalten ändert nur das Vorzeichen der

Determinante. • Somit ist 𝐴𝐵 unimodular. • Nach der Cramerschen Regel gilt

𝑥𝐵(𝑖) =det (𝐴𝐵(1), … , 𝐴𝐵(𝑖−1), 𝑏, 𝐴𝐵(𝑖+1), … , 𝐴(𝑚) )

det (𝐴𝐵)

• Die Determinante im Zähler ist ganzzahlig, und die Determinante im

Nenner hat den Wert 1 oder -1, da 𝐴𝐵 unimodular ist.

24

Totale Unimodularität (kanonische Form)

Satz 5.3 Betrachte ein LP in kanonischer Form 𝐴𝑥 ≤ 𝑏. Ist A total unimodular, so sind alle Basislösungen dieses LPs ganzzahlig.

Beweis

• Transformation in Gleichungsform

• Zeige, dass beliebige, quadratische Teilmatrix von (𝐴|𝐸𝑚) unimodular.

25

Matrizen, die total unimodular sind.

Satz 5.4 Eine ganzzahlige Matrix A mit Einträgen aus {−1,0,1} ist total unimodular, • wenn nicht mehr als zwei nicht-nullwertige Einträge

pro Spalte vorliegen, und • wenn die Zeilen in zwei Mengen 𝐼1 und 𝐼2 eingeteilt

werden können, die die folgenden Bedingungen erfüllen: a) Falls eine Spalte zwei Einträge mit demselben Vorzeichen

enthält, so sind die entsprechenden Zeilen unterschiedlichen Mengen zugeordnet.

b) Falls eine Spalte zwei Einträge mit unterschiedlichem Vorzeichen enthält, so sind die entsprechenden Zeilen derselben Menge zugeordnet.

26

Inzidenzmatrizen

Korollar 5.5

Ein LP in Standardform oder in kanonischer Form hat nur ganzzahlige Basislösungen, wenn die Nebenbedingungsmatrix (oder ihre Transponierte) der Inzidenzmatrix eines gerichteten Graphen oder der Inzidenzmatrix eines bipartiten ungerichteten Graphen entspricht.

27

6. Facility Location

– Menge von Facilities 𝐹 (z.B. Standorte für Krankenhäuser) • Betriebskosten 𝑐𝑗

– Menge von Clients 𝐶 (z.B. Patienten) • Verbindungskosten zu Facility 𝑗: 𝑎𝑖𝑗

(z.B. Entfernungskosten zum Krankenhaus)

– Wähle eine Teilmenge der Facilities und weise jedem Client einer dieser Facilities zu, so dass die Summe aus Betriebskosten und Verbindungskosten minimiert wird.

28

Interpretation des Dualen LPs

• Jede Facility 𝑖 bekommt von Client 𝑗 ein Zahlung von 𝛽𝑖𝑗 – Insgesamt höchsten so viel wie die Kosten für die

Facility

• Jeder Client 𝑗 hat Kosten von 𝛼𝑗 die gedeckelt sind durch die Zahlung(en) an die Facilities 𝛽𝑖𝑗 und Entfernungskosten 𝑐𝑖𝑗

• 𝛼𝑗 ist der Teil der Gesamtkosten die Client j übernimmt.

29

Algorithmus

• Phase 1: – Wir erzeugen eine duale Lösung (𝛼, 𝛽).

– Schrittweise 𝑎𝑗 erhöhen, und ggf. 𝛽𝑖𝑗

– Facility öffnen sobald ∑𝛽𝑖𝑗 > 𝑓𝑖

• Phase 2: – Primale Lösung erzeugen (𝑥, 𝑦) – Nur einen Teil der Facilities aus Phase 1 öffnen. – Maximale unabhängige Menge

• Analyse: Benutze die relaxierten Schlupfbedingungen mit (𝛼, 𝛽) und (𝑥, 𝑦).

• Dreiecksungleichung für indirekt verbundene Clients

30

7. Randomisiertes Runden und Set Cover

• Set Cover – 𝐻𝑛-Approximation mit Greedy

• Set Cover (𝑘) – Mengen mit Cadinalität höchstens 𝑘 – 𝐻𝑘-Approximation mit Greedy

• 𝑓-Set Cover – Jedes Elements kommt in max. 𝑓 Mengen vor – 𝑓-Approximation durch LP Relaxation und

deterministisches Runden

• Set Cover – 4 ln(4𝑛)-Approximation durch LP Relaxation und

randomisiertes Runden

32

Set Cover: 4 ln(4𝑛)-Approximation

Wir berechnen mehrere gerundete Lösungen und nehmen alle gewählten Mengen gleichzeitig:

Algorithmus 3

1. Sei 𝑥∗ die optimale Lösung des relaxierten LP

2. FOR 𝑖 = 1 TO ln(4𝑛) a) FOR 𝑗 = 1 TO 𝑚: Wähle 𝑆𝑗 mit W’keit 𝑥𝑗

∗

b) Sei 𝐶𝑖 die Menge aller in dieser Iteration gewählten Teilmengen.

3. Ausgabe: 𝐶 = 𝐶1 ∪ ⋯∪ 𝐶ln (4𝑛)

33

Analyse

Lemma 1 Die Wahrscheinlichkeit, dass 𝐶 kein gültiges Set Cover ist, ist höchstens

1

4.

Beweisidee

• Betrachte eine Cover 𝐶𝑗: – Element 𝑢 in 𝑡 Mengen in relaxierter Lösung. Im

schlimmsten Fall: W’keit, dass alle abgerundet werden

1 −1

𝑡

𝑡≤

1

𝑒

• Das es bei allen Covern passiert: ≤1

𝑒

ln(4𝑛)≤

1

4𝑛

34

Analyse Lemma 2 Das erwartete Gewicht 𝔼[𝑤 𝐶 ] des Covers C ist höchstens ln(4𝑛) ⋅ 𝑂𝑃𝑇frac. Beweis

• Jedes einzelne Cover 𝐶𝑖 kostet 𝑂𝑃𝑇frac in Erwartung. Also kostet die Vereinigung von ln(4𝑛) vielen höchstens ln(4𝑛) ⋅ 𝑂𝑃𝑇frac

Lemma 3 Pr[𝑤 𝐶 ≥ 4 ln 4𝑛 ⋅ 𝑂𝑃𝑇frac] ≤ 1/4

Beweis 𝑡 = 4 ln 4𝑛 𝑂𝑃𝑇frac

Markov Ungleichung Sei 𝑋 eine Zufallsvariable die keine negativen Werte animmt. Dann gilt für jedes positive t

Pr 𝑋 ≥ 𝑡 ≤ 𝔼[𝑋]/𝑡 35

Ergebnis Theorem

Mit Wahrscheinlichkeit 1/2 berechnet Algorithmus 3 ein Set Cover das eine 4 ln(4𝑛)-Approximation ist.

Beweis:

a) Mit W’keit ¾ ein gültiges Set Cover (Lemma 1)

b) Mit W’keit ¾ Kosten ≤ 4 ln(4𝑛)OPT (Lemma 3)

Wahrscheinlichkeit für a) und b) gleichzeitig mindestens ½ .

36

8. Branch & Bound und Heuristiken

1. Branch & Bound – Exaktes Verfahren, Optimalität der Lösung ist

garantiert. – Schlechte Laufzeit im ungünstigen Fällen

2. Heuristiken und Suchverfahren – Können zu beliebigen Zeitpunkten gestoppt werden. – Lösungen sind möglicherweise nicht optimal

a) Lokale Suche b) Simulated Annealing c) Metropolis d) Evolutionäre Algorithmen

37

Branch and Bound Module

• Branching Modul: – Zerlegt Problem in zwei oder mehr Teilprobleme

• Lösungsmenge eines Teilproblem Teilmenge… • Selben Zielfunktionswert wie im Ursprungsproblem.

– Die Teilprobleme decken das Gesamtproblem ab. – Die beste Lösung aller Lösungen aller Teilprobleme ist optimale Lösung

des Gesamtproblems.

• Upper Bound Modul, Lower Bound Modul – Berechnen obere bzw. untere Schranken für den Zielfunktionswert

eines Teilproblems. – Z.B. mit Relaxierung (obere) bzw. Greedy (untere Schranke)

• Search Modul – Entscheidet welches Teilproblem als nächstes zerlegt werden soll

38

Heuristiken

• Lokale Suche, Nachbarschaft • Metropolis:

– Schlechtere neue Nachbarschaftslösung 𝑥′ wird akzeptiert mit W‘keit:

𝑒−𝑓 𝑥 −𝑓 𝑥′

𝑇 • Simulated Annealing: T wird im Verlauf kleiner • Evolutionäre Algorithmen

– Inspiriert durch biologische Evolution mit • Selektion (natürliche Auslese, ”survival of the fittest“), • Rekombination (Kreuzung) und • Mutation (kleine, zufällige Änderungen)

39

9. Selfish Flows, Spieltheorie&Optimierung

Das Verkehrsmodell von Wardrop • Graph 𝐺 = (𝑉, 𝐸) • Für jede Kante 𝑒 ∈ 𝐸 eine Latenzfunktion ℓ𝑒: ℝ → ℝ. • Demand: 𝑞𝑖 , 𝑠𝑖 , 𝑑𝑖 ∈ 𝑉 × 𝑉 × ℝ+

Fluss der Menge 𝑑𝑖 von 𝑞𝑖 nach 𝑠𝑖 • Jeder “Flusspartikel” wählt selbst seine Route. Fluss auf

einer Kante 𝑒: 𝑓𝑒 = ∑ 𝑓𝑝𝑃:𝑒∈𝑃 • Latenz, Verzögerung einer Kante: ℓ𝑒(𝑓𝑒) • Auf einem Pfad entsprechend:

ℓ𝑃 𝑓 = ℓ𝑒(𝑓𝑒)

𝑒∈P

40

Wardrop Gleichgewicht

Definition

Ein Fluss 𝑓 ist im Gleichgewicht, wenn für jedes Paar 𝑃1, 𝑃2 ∈ 𝒫𝑖 mit 𝑓𝑃1

> 0 gilt, dass ℓ𝑃1

𝑓 ≤ ℓ𝑃2(𝑓).

Existenzbeweis durch Existenz einer Lösung für:

• Minimiere Φ 𝑓 = ∑ ℓ𝑒 𝑡 𝑑𝑡𝑓𝑒0𝑒∈𝐸

• Unter den Nebenbedingungen, dass 𝑓 ein gültiger Fluss ist, der alle Demands erfüllt.

41

Preis der Anarchie

Definition Price of Anarchy (PoA)

Der Preis der Anarchie 𝜌 = max𝐶(𝑓)

𝐶(𝑓∗) wobei 𝑓 ein

Gleichgewichtsfluss und 𝑓∗ der optimale Fluss ist.

• Worst-Case-Ratio zwischen einem Gleichgewichts- und einem optimalen Fluss.

Theorem

Der Price der Anarchie von Instanzen mit linearen

Latenzfunktionen ist 4

3.

43

Braess Paradoxon

Ohne zusätzliche Kante: Gleichgewicht ist optimal: 1

2⋅ 1 +

1

2+

1

2⋅

1

2+ 1 = 1,5

Mit zusätzlicher Kante: Neues Gleichgewicht hat Kosten:

1 ⋅ 1 + 1 ⋅ 0 + 1 ⋅ 1 = 2

44

Congestion Games [Rosenthal 73]

Die diskrete oder auch atomare Version des Wardrop Modells.

• Menge von Spielern 𝒩 = {1,… , 𝑛} Fahrzeuge

• Graph G = V, E Straßennetz – Mit Latenzfunktionen ℓ𝑒: ℕ → ℕ

– Und einem Quelle/Senke Paar 𝑞𝑖 , 𝑠𝑖 für jeden Spieler 𝑖 ∈ 𝒩

• Latenzfunktion bildet die Anzahl der Spieler auf die Latenz der Kante ab.

45

Existenz von Gleichgewichten und Konvergenz der lokalen Suche

exakte Potentialfunktion:

Φ 𝑓 = ℓ𝑒(𝑖)

𝑓𝑒

𝑖=1𝑒∈𝐸

• Jedes (lokale) Minimum von Φ 𝑓 ist ein Gleichgewicht. • Lokale Nachbarschaft einer Lösung 𝑓: Die Menge der

Lösungen die sich von 𝑓 nur durch die Wahl eines Spielers unterscheiden.

• Verbessert sich ein Spieler um Δ, dann sinkt Φ um Δ. • Im (lokalen) Minimum kann es also einen solchen Spieler

nicht geben.

46

Klausur

• Datum: 10.02.2015 • Uhrzeit: 11:00 - 13:00 • Raum: O1 • Schriftliche Klausur • Erlaubte Hilfsmittel:

– Stift. – Ein einseitig, handschriftlich beschriebenes DIN A4

Blatt. Selbst geschrieben, nicht ausgedruckt oder kopiert.

• Studierendenausweis nicht vergessen.

47