Kap. 3: Exakte Lösungsverfahren für NP- schwierige ...ls11- · 17.04.2007 3 Überblick Kap. 3 3.1 Einführung – Kombinatorische Optimierungsprobleme – Lineare Programmierung

VO Algorithm Engineering

Professor Dr. Petra Mutzel

Lehrstuhl fr Algorithm Engineering, LS11

4./5. VO 12./17. April 2007

Kap. 3: ExakteLsungsverfahren fr NP-

schwierige kombinatorischeOptimierungsprobleme

3.1 Einfhrung3.2 Komb. vs. Ganzzahlige Opt.3.3 Das Lineare Ordnungsproblem

17.04.2007 2

Literatur fr diese VO

Originalliteratur fr Interessierte: M. Grtschel, M. Jnger und G. Reinelt: A cutting plane algorithm forthe linear ordering problem. Operations Research 32, 1195-1220, 1984

Nachschlagewerk bei Interesse: M. Jnger und D. Naddef (Eds.): Computational CombinatorialOptimization, Optimal or Provably Near-OptimalSolutions, LNCS 2241, Springer, 2001, i.e. 157-223

P.Mutzel: Skript-Teil: NP-schwierige kombinatorische Optimierungsprobleme (s. Web)

17.04.2007 3

berblick Kap. 33.1 Einfhrung

Kombinatorische Optimierungsprobleme Lineare Programmierung (Kurzeinfhrung) Polyedertheorie (Kurzeinfhrung)

3.2 Kombinatorische vs. Ganzzahlige Optimierung

3.4 Exakte Verfahren fr Ganzzahlige Optimierung Schnittebenenverfahren Branch-and-Cut

3.3 Bsp: Das Lineare Ordnungsproblem

- Bsp: Das Handlungsreisendenproblem

17.04.2007 4

Kombinatorische Optimierungsprobleme

Gegeben sind:

endliche Menge E (Grundmenge)

Teilmenge I der Potenzmenge 2E von E (zul. Mengen)

Kostenfunktion c: EK

Definition Kombinatorisches Optimierungsproblem

17.04.2007 5

Beispiele Kombinatorische Optimierungsprobleme

Handlungsreisendenproblem (TSP)

Minimum der Funktion: f(x)=3x2+2, xR

Minimaler Spannender Baum (MST)

17.04.2007 6

Beispiele Kombinatorische Optimierungsprobleme

Rucksackproblem: Geg. n versch. Gterarten in

unbegrenzter Menge mit Gewicht ai>0und Wert ci; Kapazitt des Rucksacks: b

Gesucht: Kostbarste Rucksackpackung

0/1-Rucksackproblem: Geg. n versch. Gter mit Gewicht ai>0

und Wert ci; Kapazitt des Rucksacks: b Gesucht: Kostbarste Rucksackpackung

ILP-Modellierung

17.04.2007 7

Lineare Optimierungsprobleme

Das Problem, einen Vektor zu finden, der unter allen Vektoren, die die Bedingungen Ax

17.04.2007 8

Beispiel lraffinerie

Ziele: mindestens 3S, 5M, 4L herstellen (Lieferbedingungen)

mglichst billig herstellen

2 Crackverfahren fr Rohl mit folgender Ausbeute und Kosten: Crackproze 1: 2S, 2M, 1L, Kosten 3 EUR Crackproze 2: 1S, 2M, 4L, Kosten 5 EUR

17.04.2007 9

Beispiel lraffinerie

Zielfunktion

Restriktionen

subject to

definieren denLsungsraum

Matrixschreibweise: (Tafel)

17.04.2007 10

Geometrische Interpretation

Maximiere 0.90 x + 0.73 ysubject To

NB1: 0.42 x + 0.07 y

17.04.2007 11

Lineares Programm

Max 3x1 + 2x2 + 2x3Subject to x1 + x3 8

x1 + x2 7x1 + 2x2 12

x1, x2, x3 0

Simplex-Algorithmus

17.04.2007 12x1

x2

x3

(0,0,8) (0,6,8)

(2,5,6)

(0,6,0)

(2,5,0)(7,0,1)

(7,0,0)

Max z = 3x1 + 2x2 + 2x3

z = 0

z = 21

z = 23

Optimal!

z = 28

Simplex-Algorithmus

17.04.2007 13


max oder min cTx: Axb

min cTx: Axb und x0

min cTx: Ax=b und x0

Lineare Optimierungsprobleme tauchen in verschiedenen Formulierungen auf und knnen alle ineinander bergefhrt werden:

17.04.2007 14


LP in seiner allgemeinsten Form:

17.04.2007 15

Ganzzahlige Lineare Optimierungsprobleme

Lineare Optimierungsprobleme mit Ganzzahligkeitsforderungen: GLP (ILP, IP)

Lineare Optimierungsprobleme mit teilweise Ganzzahligkeitsforderungen: GGLP (MIP)

Lineare Optimierungsprobleme mit 0/1-Bedingungen: 0/1-IP, Binres LP, BLP

17.04.2007 16

Polyedertheorie (Kurzeinfhrung)

17.04.2007 17


17.04.2007 18


17.04.2007 19

Geometrische Interpretation

Maximiere 0.90 x + 0.73 ysubject To

NB1: 0.42 x + 0.07 y

17.04.2007 20


17.04.2007 21


17.04.2007 22

Beispiel fr Minkowski/Weyl

1

1

00 x

y

17.04.2007 23


17.04.2007 24

3.2 Zusammenhang zu Kombinatorischer Optimierung

Jedes kom. OP kann als BLP formuliert werden und umgekehrt:

Ist E eine endliche Menge und FE, dann ist der charakteris-tische Vektor FRE fr F definiert als

Wir assoziieren zu jedem Element eE eine Komponente des Vektors F.

Umgekehrt, ist jeder 0/1-Vektor x{0,1}E charakteristischer Vektor einer Teilmenge Fx von E, und zwar gilt: Fx={eE | xe=1}.

Beispiel: MST

ENDE 4. VO

17.04.2007 25

Kombinatorische Optimierung vs. 0/1-IP

Gegeben ist 0/1-IP:

Assoziiertes kombinatorisches OP: Wir setzen:

17.04.2007 26

Kombinatorische Optimierung vs. 0/1-IPGegeben ist kombinatorisches OP: (E,I,c)

Assoziiertes 0/1-IP:

Jedes Polyeder hat Beschreibung durch Ungleichungen

Wir knnen also jedes komb. OP als LP formulieren

Probleme: Berechnung der LP-Darstellung nicht in pol.- Zeit mglich i.A. exponentiell viele Ungleichungen Ungleichungen besitzen Koeffizienten exponentieller Gre Beispiel: MST auf G=K3

17.04.2007 27

Beispiel: MST auf K3Gegeben: vollstndiger Graph G=(V,A) mit 3 Knoten

Einfhrung von 0/1-Variablen xe=1 g.d.w. Kante in Baum

1 2

3K3:

Bedingungen:

1

3

1 2

3

1 2

3

Zulssige Menge: Menge aller Spannbume in G

2

17.04.2007 28

Charakt. Vektor der gltigen Spannbume(1,1,0)(1,0,1)(0,1,1)

x1

x3

(0,0,0) (1,0,0)

(0,1,0)

(0,1,1) (1,1,1)

(1,0,1)

x1+x2+x3=2

Beispiel: MST auf K3

x2(0,0,1)

(1,1,0)

17.04.2007 29

3.3 Lineares Ordnungsproblem (LOP) Gegeben: ein vollstndiger gerichteter Graph G=(V,A) mit

Kantengewichten cuv fr alle Bgen (u,v) in A.

Gesucht: eine lineare Ordnung der Knoten, so dass die Summe der Gewichte aller Bgen, die dieser Ordnung entsprechen, maximiert wird.

1 2 3 4

Anwendungen: Triangulation von Input-Output Matrizen, Rangbestimmung in Turniersportarten, Graph Layout

17.04.2007 30

Graphen-Theoretische Formulierung

Gesucht: ein spannendes, azyklisches Turnier in Gmit grtem Gewicht

1 2 3 4

Turnier: TA: entweder (i,j)T oder (j,i)T aber nicht beide

Gegeben: ein vollstndiger gerichteter Graph G=(V,A) mit Kantengewichten cuv fr alle Bgen (u,v) in A.

17.04.2007 31

Spannendes Azyklisches TurnierVerbotene Strukturen in T:

u v

u w

v

u w

v

17.04.2007 32

ILP fr LOP

3-Kreis Ungleichungen

Triviale Ungleichungen

Gleichungen

Ausschluss der 3-er Kreise gengt

17.04.2007 33

Spannendes Azyklisches TurnierVerbotene Strukturen in T:

u v

u w

v

u w

v

17.04.2007 34

Projektion: xvu=1-xuv

3-Kreis Ungl.

Triviale Ungl.

ILP fr LOP

17.04.2007 36

Beispiel n=3: x12 x13 x23Permutation

charakt. Vektor(1,1,1)(0,1,1)(0,0,1)(1,1,0)(1,0,0)(0,0,0) x12

x13

x23x12+x23-x13=0

x12+x23-x13=11 3

2

1 3

2

Geometrische Interpretation LOP

17.04.2007 37

n=6: zustzliche Ungleichungen notwendig

LP-Relaxierung des IPs

17.04.2007 38

Beispiel: Moebius-Leiter Ungleichungen:

1 2k-1

2k23 4

Allgemein:k Kreise, k ungerade

Es ist notwendig, mindestens(k+1)/2 Bgen zu entfernen,um G azyklisch zu machen

Mbius-Ungleichungen beschreiben Facetten des LOP-Polytops

Foschungsgebiet: Polyedrische Kombinatorik

17.04.2007 39

Polyedrische Kombinatorik: LOPKonvexe Hlle aller charakteristischer Vektoren, die Permutationen von l Elementen beschreiben.

>488,602,996

82040

91087,472

345678

nl

For l=60 ist LOP exakt lsbar innerhalb 1 Sekundemittels Schnittebenenverfahren.

Anzahl der Facetten,d.h. die Anzahl der

theoretisch not-wendigen Linearen

Ungleichungen

Documents

Kap. 3: Exakte Lösungsverfahren für NP- schwierige ...ls11- · 17.04.2007 3 Überblick Kap. 3 3.1 Einführung – Kombinatorische Optimierungsprobleme – Lineare Programmierung