1Technische Universität WienInstitut für Computergraphik und Algorithmen
Wie lösen wir ILPs exakt?
Branch-and-Bound
Schnittebenen-verfahren
Branch-and-Cut
AcyclicSubgraph
TSP
2Technische Universität WienInstitut für Computergraphik und Algorithmen
Zielfunktion
IP Optimum
Ganzzahliges Lineares Programm
Abrunden der optimalenLösung der LP-Relaxierung
ZulässigeLösungen
y
x
Optimum derLP Relaxierung
3Technische Universität WienInstitut für Computergraphik und Algorithmen
Branch-and-Bound
Zerlegung in Teilprobleme Berechnung oberer und unterer Schranken
Löse erste Relaxierung ! obere Schrankezulässig? ! optimal
Sonst: Partitioniere in Teilprobleme • Löse Relaxierung
! Lsg. (a) ganzzahlig oder (b) unzulässig oder (c) neue, evtl. schärfere, obere Schranke
• Fall (c) ! eventuell rekursive Aufteilung
4Technische Universität WienInstitut für Computergraphik und Algorithmen
Branch-and-Bound
Vernünftige Aufteilungsstrategie und endliche Lösungsmenge ! endliche Anzahl Schritte
Ergibt Branch-and-Bound-Baum• Knoten = Teilproblem• Söhne = Partitionierung des
Vaterproblems
Intelligente Enumeration Permanent Gütegarantie, bei
Termination beweisbar optimal
5Technische Universität WienInstitut für Computergraphik und Algorithmen
Branch-and-Bound
Betrachte das folgende ILP:
Max x + y + 2z
Subject to 7x + 2y + 3z 36
5x + 4y + 7z 42
2x + 3y + 5z 28
x, y, z 0, ganzzahlig
(IP0)
LP-Relaxierung
6Technische Universität WienInstitut für Computergraphik und Algorithmen
IP011
511obj
11
15
011
31
z
y
x
IP2 IP1
1x 2x
10obj
402
Bester IP-Wert
Beste IP-Lösung
4.11obj
2.501
402
10/
Integral
IP4 IP3
5z 6z
Unzulässig
3
111obj
53
11
11obj
501
0y 1y
IP6 IP5
/ 11
501
Integral
2.11obj
6.411
IP8 IP7
4z 55 zz
11obj
421
Obj. · bestem gefundenen Wert
11obj
510
Obj. · bestem gefundenem Wert
Branch-and-Bound für ILPs: Beispiel
Löse LP-Relaxierung
Max x + y + 2z
Subject to 7x + 2y + 3z 36
5x + 4y + 7z 42
2x + 3y + 5z 28
x, y, z 0, ganzzahlig
Garantie 87,3%
87,7%
88,2%
98,2%
100%
7Technische Universität WienInstitut für Computergraphik und Algorithmen
Branch-and-Bound
Eingabe: Gemischt-ganzzahliges lineares Programm (A, b, c, N1)
Ausgabe: Lösung von (MIP=) oder Beweis der Unlösbarkeit
8Technische Universität WienInstitut für Computergraphik und Algorithmen
P0 = {x j Ax = b, x ¸ 0, xi ganzzahlig 8 i 2 N1}
U = -1
K := {P0} (Liste der offenen Probleme)
x = NIL (beste Lösung)
ja
K = ;?
Löse Relaxierung von (MIPj
=)(Bounding)
x* ist Optimallö-sung mit Wert c*
c* · U?
U = c*, x = x*
ja
U = -1 ! MIP= hat keine Lösung
U ¸-1 ! x ist Optimallösung mit Wert U
ja
xi* 2 Z
8 i 2 N1?
nein
Wähle Pj 2 K,K = K – {Pj}(Branching)
nein
Wähle i 2 N1 mit x*i Z
K += (Pj Å {x j xi · bx*ic})
+ (Pj Å {x j xi ¸dx*ie})
nein
9Technische Universität WienInstitut für Computergraphik und Algorithmen
Branch-and-Bound
Analyse:• (LMIP=) unzulässig oder unbeschränkt !
B&B bricht ab mit korrektem Ergebnis
• (LMIP=) hat endliches Optimum und P0 ; ! endlich viele Schritte zur Optimallösung
• (LMIP=) hat endliches Optimum und P0 = ; ! Abbruch durch Zusatzrestriktionen
Praxis:• Beschränkung der Baumgröße meist
notwendig• ! Branch-and-Cut ! später