Diskrete Optimierung

Diskrete Optimierung
Vorlesungsskript SS 2010, TU München
Prof. Dr. Raymond Hemmecke
Version vom 11. Juli 2010
Inhaltsverzeichnis
1 Komplexitätstheorie
1
1.1
Was ist ein Problem? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
Was ist ein Algorithmus? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.3
Was ist Effizienz? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.4
Kodierungsschema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.5
Rechnermodell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.6
Die Klasse P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.7
Die Klasse N P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.8
Die Klasse N P-vollständig . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.9
Komplexität von Optimierungsproblemen . . . . . . . . . . . . . . . . . . . . . . .
8
2 Ganzzahlige Optimierung
2.1
9
n
Lineare diophantische Gleichungssysteme Ax = b, x ∈ Z
. . . . . . . . . . . . . .
9
2.1.1
Gitter und Gitterbasen
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.1.2
Lineare diophantische Gleichungen . . . . . . . . . . . . . . . . . . . . . . .
10
2.1.3
Unimodulare Matrizen und Transformationen . . . . . . . . . . . . . . . . .
11
2.1.4
Hermite Normalform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
2.1.5
Ganzzahlige Lösung von Az = 0 . . . . . . . . . . . . . . . . . . . . . . . .
13
2.1.6
Ganzzahlige Lösung von Az = b . . . . . . . . . . . . . . . . . . . . . . . .
14
2.1.7
Ganzzahliges Farkas-Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
2.2
Ganzzahlige Hülle und ganzzahlige Polyeder . . . . . . . . . . . . . . . . . . . . . .
15
2.3
Hilbertbasen rationaler polyedrischer Kegel, TDI-Systeme und Chvátal-GomoryAbschluss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
2.3.1
Hilbertbasen rationaler polyedrischer Kegel . . . . . . . . . . . . . . . . . .
26
2.3.2
TDI-Systeme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
i
INHALTSVERZEICHNIS
2.3.3
ii
Chvátal-Gomory-Abschluss . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
2.4
Schnittebenen-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
2.5
Gomory-Schnitte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
2.6
Branch-and-Bound Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
2.7
Branch-and-Cut Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
Kapitel 1
Komplexitätstheorie
Wiederholung: Notation
Wir setzen N = Z+ = {0, 1, 2, . . .}. Desweiteren sei g : N → R eine Funktion. Dann definieren wir:
O(g)
= {f : N → R|∃c > 0, n ∈ N mit |f (n)| ≤ c · |g(n)| für alle n ≥ n0 }
Ω(g)
= {f : N → R|∃C > 0, n ∈ N mit |f (n)| ≥ c · |g(n)| für alle n ≥ n0 }
Θ(g)
= {f : N → R|∃c, C > 0, n ∈ N mit c · |g(n)| ≤ |f (n)| ≤ C · |g(n)| für alle n ≥ n0 }
Beispiel. f (n) = ak nk + . . . + a1 n + a0 ∈ O(nk )
1.1
Was ist ein Problem?
Definition 1.1.1 Ein Problem ist eine allgemeine Fragestellung, bei der mehrere Parameter
offen gelassen sind und für die eine Lösung oder Antwort gesucht wird.
Ein Problem ist dadurch definiert, dass alle seine Parameter beschrieben werden und dass genau
angegeben wird, welche Eigenschaften eine Antwort (Lösung) haben soll.
Sind alle Parameter eines Problems mit expliziten Daten belegt, dann sprechen wir von einem
Problembeispiel (Instanz).
Beispiel. “Finde in einem gewichteten Graphen G einen kürzesten Hamiltonischen Kreis.”
Offene Parameter: Graph G, Kantengewichte (Entfernungen)
1
1.2. Was ist ein Algorithmus?
1.2
2
Was ist ein Algorithmus?
Definition 1.2.1 Ein Algorithmus ist eine Anleitung zur schrittweisen Lösung eines Problems.
Wir sagen, ein Algorithmus Problem Π löst, wenn er für jedes Problembeispiel I ∈ Π eine Lösung
in einer endlichen Anzahl an Schritten findet. Ein Schritt ist eine elementare Opteration, z.B.
Addieren, Subtrahieren, Vergleichen, Multiplikation, Division.
Die Laufzeit eines Algorithmus ist die Anzahl der Schritte, die notwendig sind zur Lösung des
Problembeispiels.
Forschungsschwerpunkte:
• Entwurf von Algorithmen
• Berechenbarkeit: Was kann durch Algorithmen berechnet werden?
• Komplexität von Algorithmen
• Korrektheit von Algorithmen
1.3
Was ist Effizienz?
• Inhalt der Komplexitätstheorie
• Speicher- und Laufzeitkomplexität
Bemerkung.
• Laufzeit eines Algorithmus hängt von der “Größe” der Eingabedaten ab.
• Laufzeitanalyse erfordert eine Beschreibung, wie Problembeispiele dargestellt werden (Kodierungsschema).
• Notwendigkeit exakter Definitionen → geeignetes Rechnermodell → Turing-Maschine
1.4
Kodierungsschema
Ganze Zahlen
Ganze Zahlen werden binär dargestellt, d.h. wir schreiben
n=±
k
X
xi · 2 i ,
i=0
mit xi ∈ {0, 1} und k = blog2 (|n|)c.
D.h. die Kodierungslänge hni einer ganzen Zahl n ist gegeben durch die Formel
hni = (k + 1) + 1 = blog2 (|n|)c + 2.
Kapitel 1. Komplexitätstheorie
3
Rationale Zahlen
Sei r ∈ Q. Dann existieren p ∈ Z und q ∈ Z, teilerfremd, mit r = pq .
hri = hpi + hqi
Vektoren und Matrizen
Für A ∈ Qm×n ist
m X
n
X
hAi =
haij i.
i=1 j=1
1.5
Rechnermodell
Nach Festlegung der Kodierungsvorschrift muss ein Rechnermodell entworfen werden, auf dem unsere Speicher- und Laufzeitberechnungen durchgeführt werden. In der Komplexitätstheorie: TuringMaschine (ein ganz normaler Computer)
Ablauf eines Algorithmus auf der Turing-Maschine:
Algorithmus A soll Problembeispiel I des Problems Π lösen. Alle Problembeispiele liegen in kodierter Form vor. Die Anzahl der Speicherplätze, die nötig sind, um I vollständig anzugeben, heißt
Inputlänge, hIi. Der Algorithmus liest die Daten und beginnt dann, Operationen auszuführen,
d.h. Zahlen zu berechnen, zu speichern, zu löschen.
Die Anzahl der Speicherplätze, die während der Ausführung des Algorithmus mindestens einmal
benutzt werden, nennen wir Speicherbedarf von A zur Lösung von I. Die Laufzeit von A zur
Lösung von I ist die Anzahl elementarer Operationen. Dazu zählen +, −, ∗, /, Vergleich, Löschen,
Schreiben, Lesen von rationalen Zahlen.
Dies ist jedoch zu unpräzise! Zur Darstellung der entsprechenden Zahlen werden mehrere Bits
benötigt. → Für jede Operation müssen wir mehrere Bits zählen.
Definition 1.5.1 Laufzeit von A zur Lösung von I ist definiert durch die Anzahl elementarer
Operationen, die A ausgeführt hat, um I zu lösen, multipliziert mit der größten Kodierungslänge
der während der Berechnung aufgetretenen ganzen oder rationalen Zahl.
Definition 1.5.2 (“worst-case Laufzeit”)
(a) Sei A ein Algorithmus zur Lösung eines Problems Π. Die Funktion fA : N → N,
fA (n) = max{Laufzeit von A zur Lösung von I : I ∈ Π, hIi ≤ n}
heißt Laufzeitfunktion von A.
1.6. Die Klasse P
4
(b) Die Funktion sA : N → N definiert durch
sA (n) = max{Speicherbedarf von A zur Lösung von I : I ∈ Π, hIi ≤ n}
heißt Speicherplatzfunktion von A.
(c) Der Algorithmus A hat eine polynomiale Laufzeit (kurz: A ist ein polynomialer Algorithmus), wenn es ein Polynom p : N → N gibt mit
fA (n) ≤ p(n) für alle n ∈ N.
Wir sagen fA ist von der Ordnung höchstens nk (geschrieben fA = O(nk )), falls das Polynom p den Grad k hat.
(d) Der Algorithmus A hat polynomialen Speicherbedarf, falls es ein Polynom q : N → N gibt mit
sA (n) ≤ q(n) für alle n ∈ N.
Bemerkung.
• fA (n) ist in Praxis kaum exakt berechenbar (zu aufwendig).
• fA (n) ist maschinenabhängig.
• Man kann aber a priori ein g bestimmen mit f ∈ O(g). → Man finde möglichst kleinstes
solches g.
1.6
Die Klasse P
Ein Entscheidungsproblem ist ein Problem, das nur zwei mögliche Antworten besitzt, “ja” oder
“nein”.
Beispiel. “Ist n eine Primzahl?”
Klasse P: Klasse aller Entscheidungsprobleme, für die ein polynomialer Lösungsalgorithmus existiert
Diese Definition ist informell: Gegeben ein Kodierungsschema E und ein Rechnermodell M . Π sei
ein Entscheidungsproblem, wobei jede Instanz aus Π durch Kodierungsschema E kodierbar sei. Π
gehört zur Klasse P (bzgl. E und M ), wenn es einen auf M implementierbaren Algorithmus zur
Lösung aller Problembeispiele aus Π gibt, dessen Laufzeitfunktion auf M polynomial ist.
1.7
Die Klasse N P
Motivation.
• Enthält G einen Kreis? → “einfach” → P
• Enthält G einen hamiltonischen Kreis? → “schwieriger” → N P
Kapitel 1. Komplexitätstheorie
5
Klasse NP
Definition 1.7.1 Ein Entscheidungsproblem Π gehört zu N P, wenn es die folgende Eigenschaften
hat:
(a) Für jedes Problembeispiel I ∈ Π, für das die Antwort “ja” lautet, gibt es mindestens ein
Objekt Q, mit dessen Hilfe die Korrektheit der “ja”-Antwort überprüft werden kann.
(b) Es gibt einen Algorithmus, der Problembeispiele I ∈ Π und Zusatzobjekte Q als Input akzeptiert und der in einer Laufzeit, die Polynomial in hIi ist, überprüft, ob Q ein Objekt ist,
aufgrund dessen Existenz ein “ja”-Antwort für I gegeben werden muss.
Beispiel. “Hat gegebenes System Ax = b, x ≥ 0 eine Lösung?”
Zusatzobjekt Q: z.B. eine Lösung x0
Überprüfungsalgorithmus: Teste, ob Ax0 = b, x0 ≥ 0.
“Ja.”: Die “ja”-Antwort für I ist bestätigt.
“Nein.”: Q ist ungeeignetes Objekt. Die Antwort für I bleibt offen.
1.7. Die Klasse N P
6
Bemerkung.
• Es wird keine Aussage über die Berechenbarkeit eines geeigneten Q gemacht. → Q kann
geraten werden. → Nondeterministic Polynomial time
• Laufzeit des Algorithmus in (b) ist polynomial in hIi. Da der Algorithmus Q lesen muss, ist
hQi polynomial in hIi.
• Auf die Frage “Hat die Gleichung x2 + y 2 = n eine Lösung in ganzen Zahlen?” ist x = y =
√
n 0.5 kein geeignetes Zusatzobjekt.
• Definition ist unsymmetrisch in “ja” und “nein”. N P impliziert nicht, dass auf die “nein”Antwort ein polynomialer Algorithmus zur Überprüfung der Korrektheit dieser Aussage existiert.
• Probleme, die Negationen von Problemen aus N P sind, gehören zur Klasse coN P. Zum
Beispiel: “Hat G keinen Kreis?”, “Ist n ∈ N eine Primzahl?” Man weiß, dass beide Probleme
zur Klasse N P∩ coN P gehören. Vom Problem “Hat G keinen hamiltonischen Kreis?” weiß
man nicht, ob es zu N P gehört.
• P ⊆ N P: Es ist kein Objekt Q nötig, um die “ja”-Antwort in polynomiller Zeit zu überprüfen.
• Offene Fragen:
P
NP
P
= N P ∩ coN P
=
coN P
6= N P
Beispiele. Die Probleme “Hat ein Graph G einen Kreis?”, “Hat ein Graph G einen hamiltonischen
Kreis?” sind somit in N P. Hat nämlich G einen Kreis oder hamiltonischen Kreis, so wählen wir
diesen als Objekt Q. Dann entwerfen wir einen polynomialen Algorithmus, der für einen Graphen
G und eine zusätzliche Kantenmenge Q entscheidet, ob Q ein Kreis oder hamiltonischer Kreis von
G ist.
Auch die Frage “Ist n ∈ N eine zusammengesetzte Zahl?” ist in N P, denn liefern wir als “Objekt”
zwei Zahlen 6= 1, deren Produkt n ist, so ist n keine Primzahl. Die Überprüfung der Korrektheit
besteht somit in diesem Fall aus einer einzigen Multiplikation.
Kapitel 1. Komplexitätstheorie
1.8
7
Die Klasse N P-vollständig
Nächster Schritt: Charakterisierung besonders schwieriger Probleme in N P.
Polynomiale Transformation von Problemen
Definition 1.8.1 Gegeben seien zwei Entscheidungsprobleme Π und Π0 . Eine polynomiale Transformation von Π in Π0 ist ein polynomialer Algorithmus, der, gegeben ein (kodiertes) Problembeispiel I ∈ Π, ein (kodiertes) Problembeispiel I 0 ∈ Π0 produziert, so dass folgendes gilt:
Die Antwort auf I ist genau dann “ja”, wenn die Antwort auf I 0 “ja” ist.
Wenn Π in Π0 polynomiell transformierbar ist und es einen polynomialen Algorithmus zur Lösung
von Π0 gibt, dann kann jede Instanz von Π auch polynomial gelöst werden.
Klasse N P-vollständig
Definition 1.8.2 Ein Entscheidungsproblem Π heipt N P-vollständig, falls Π ∈ N P und falls
jedes andere Problem aus N P polynomial in Π transformiert werden kann.
Jedes N P-vollständige Entscheidungsproblem hat also folgende Eigenschaft. Falls Π in polynomialer Zeit gelöst werden kann, dann kann auch jedes andere Problem aus N P in polynomialer Zeit
gelöst werden. Diese Eigenschaft zeigt, dass–bzgl. polynomialer Lösbarkeit–kein Problem in N P
schwieriger ist als ein N P-vollständiges.
Existieren N P-vollständige Probleme? Ja.
Beispiele:
• 3-SAT: “(x1 ∨ x̄2 ∨ x3 ) ∧ (. . .) ∧ . . . = TRUE?”
m 3er-Klauseln über n bollschen Variablen
• “Hat Graph G einen Hamilton-Kreis?”
• “Hat gewichteter Graph G einen Hamilton-Kreis mit Länge ≤ B?”
• “Ist n ∈ N prim?”
∈ P?
∈ N P∩ coN P?
N P-vollständig?
Diese Fragen wurden 2003 von drei Indern geklärt. “Ist n ∈ N prim?” ist in P.
1.9. Komplexität von Optimierungsproblemen
1.9
8
Komplexität von Optimierungsproblemen
Definition 1.9.1 Ein Problem P heißt N P-schwer, falls alle Π ∈ N P polynomiall reduzierbar
(= transformierbar) auf bzw. in P sind.
Beispiel. Das Problem, in einem gewichteten Graphen einen kürzesten Hamilton-Kreis zu finden
(= Traveling Salesman Problem (= TSP)) is N P-schwer.
Beispiel. max{c| x : Ax = b, x ≥ 0, x ∈ Zn } ist N P-schwer.
Kapitel 2
Ganzzahlige Optimierung
In diesem Kapitel werden wir uns mit dem Problem
max{c| x : Ax = b, x ≥ 0, x ∈ Zn } bzw.
max{c| x : Ax ≤ b, x ∈ Zn }
beschäftigen. Zuerst machen wir uns mit der diskreten Natur der Menge {x : Ax = b, x ∈ Zn }
vertraut.
Lineare diophantische Gleichungssysteme Ax = b, x ∈ Zn
2.1
Unser Ziel wird es sein, eine Darstellung
(
n
{x : Ax = b, x ∈ Z } =
v0 +
k
X
)
λi vi : λ1 , . . . , λk ∈ Z
i=1
zu finden. Man vergleiche dies mit der allgemeinen Lösungsdarstellung für Ax = b, x ∈ Rn .
2.1.1
Gitter und Gitterbasen
Definition 2.1.1 Sei L ⊆ Rn .
(a) L heißt Gitter des Rn , wenn es eine Basis {v1 , . . . , vn } des Rn gibt, mit
( n
)
X
L=
λi vi : λ1 , . . . , λn ∈ Z .
i=1
{v1 , . . . , vn } heißt dann Basis des Gitters.
(b) Zn heißt Standardgitter des Rn .
9
2.1. Lineare diophantische Gleichungssysteme Ax = b, x ∈ Zn
10
(c) Seien L ein Gitter und S ⊆ L. S heißt Teilgitter oder Untergitter, wenn S = {0} ist,
oder wenn es ein k ∈ N und linear unabhängige Vektoren s1 , . . . , sk ∈ L gibt mit
( k
)
X
S=
λi si : λ1 , . . . , λk ∈ Z .
i=1
In diesem Fall heißen S durch s1 , . . . , sk (ganzzahlig) erzeugt und s1 , . . . , sk Basis des
Untergitters S.
erzeugte Gitter ist n
das Standardgitter
Z2 . Das durch 21 , 12
o
√ 2
√1
erzeugte Gitter enthält wie alle
erzeugte Gitter ist ein Teilgitter von Z2 . Das durch
2
1 ,
Beispiel. Das durch
1
0
,
0
1
Gitter den Nullpunkt 0, sonst aber keinen einzigen weiteren ganzzahligen Punkt des R2 .
Beispiel. Seien v1 =
(β1 , β2 ) ∈ Z2 :
3
1
und v2 =
(β1 − 2β2 )
2
1
. Offenbar sind v1 , v2 linear unabhängig und es gilt für
3
2
β1
+ (−β1 + 3β2 )
=
.
1
1
β2
Somit lässt sich jeder Gitterpunkt (β1 , β2 ) ∈ Z2 als ganzzahlige Linearkombination von v1 , v2
darstellen. Also bilden v1 , v2 eine Basis von Z2 .
2.1.2
Lineare diophantische Gleichungen
Sei A ∈ Zd×n und b ∈ Zd . Dann heißt Ax = b, x ∈ Zn lineares diophantisches Gleichungssystem. Für b = 0 heißt das Gleichungssystem homogen, andernfalls inhomogen.
Lemma 2.1.2 Seien a1 , . . . , an , β ∈ Z und g = ggT(a1 , . . . , an ). Die lineare diophantische Gleichung
a1 x1 + . . . + an xn = β
ist genau dann über Z lösbar, wenn g ein Teiler von β ist.
Beweis. Da g ein Teiler von a1 x1 + . . . + an xn ist, muss g auch β teilen, damit eine Lösung
existiert. Sei nun g ein Teiler von β. Da g = ggT(a1 , . . . , an ), existiert eine Linearkombination
g = y1 a1 + . . . + yn an mit y1 , . . . , yn ∈ Z. Setzen wir jetzt xi = βg yi ∈ Z, i = 1, . . . , n, so erhalten
wir
β
a1 x1 + . . . + an xn = (y1 a1 + . . . + yn an ) = β.
g
Damit haben wir also eine Lösung für unsere lineare diophantische Gleichung gefunden.
Bemerkung. Sei n ≥ 3 und a1 , . . . , an ∈ Z. Dann gilt
ggT(a1 , . . . , an ) = ggT(ggT(a1 , a2 ), a3 , . . . , an ).
Lemma 2.1.3 In polynomieller Zeit kann entschieden werden, ob eine lineare diophantische Gleichung lösbar ist.
Kapitel 2. Ganzzahlige Optimierung
11
Beweis. O.B.d.A. können wir annehmen, dass a1 , . . . , an ∈ Z>0 . (Warum?) Wir wenden den
Euklidschen Algorithmus zunnächst auf a1 , a2 an und erhalten g2 = ggT(a1 , a2 ) in polynomieller
Zeit (in ha1 , a2 i). (Übungsaufgabe!) Nach obiger Bemerkung gilt
ggT(a1 , . . . , an ) = ggT(g2 , a3 , . . . , an )
und wir wenden den Euklidschen Algorithmus nun auf g2 und a3 an. Analog ist nun nach k Schritten
gk+1 = ggT(a1 , . . . , ak+1 ) ≤ max{a1 , . . . , ak+1 }
bestimmt. Da die binäre Größe der auftretenden Komponenten nicht zunimmt, bleibt die Laufzeit
polynomiell (in ha1 , . . . , an i). Nach n − 1 Schritten ist somit g = ggT(a1 , . . . , an ) berechnet. Ein
einfacher Teilbarkeitstest von β durch g entscheidet nun nach Lemma 2.1.2, ob die lineare diophantische Gleichung lösbar ist oder nicht.
2.1.3
Unimodulare Matrizen und Transformationen
Definition 2.1.4 Sei C ∈ Zn×n mit | det(C)| = 1. Dann heißt C unimodular. Die mittels C
durch ψ(x) = Cx gegebene Abbildung ψ : Rn → Rn heißt unimodulare Transformation des Rn .
Lemma 2.1.5 Sei C ∈ Zn×n regulär. Dann sind die folgenden Aussagen äquivalent:
(a) C ist unimodular.
(b) Für jedes b ∈ Zn gilt C −1 b ∈ Zn .
(c) Für jedes b ∈ Zn ist das lineare diophantische Gleichungssystem Cx = b lösbar.
(d) C −1 ∈ Zn×n
Beweis.
(a)→(b): Als Folgerung aus dem Entwicklungssatz von Laplace (s. Lineare Algebra) gilt
C −1 =
1
adj(C).
det(C)
Somit gilt wegen | det(C)| = 1:
C −1 b =
1
adj(C)b ∈ Zn .
det(C)
(b)→(c): (c) ist nur eine Unformulierung von (b).
(c)→(d): Für i = 1, . . . , n ist C −1 ei der i-te Spaltenvektor von C −1 , und nach Voraussetzung
gilt C −1 ei ∈ Zn . Also ist C −1 ganzzahlig.
2.1. Lineare diophantische Gleichungssysteme Ax = b, x ∈ Zn
12
(d)→(a): Mit det(C), det(C −1 ) ∈ Z folgt det(C −1 ) =
1
det(C)
∈ {−1, 1}.
Bemerkungen.
• Sei C ∈ Rn×n und die Abbildung ψ : Zn → Rn sei definiert durch
Zn 3
x 7→ ψ(x) := Cx.
ψ ist genau dann ein Gruppenautomorphismus von (Zn , +), wenn C unimodular ist.
• Bzgl. der Matrixmultiplikation bilden die unimodularen Matrizen des Rn eine Gruppe.
2.1.4
Hermite Normalform
Definition 2.1.6 Sei A ∈ Zd×n mit rang(A) = d. A heißt in Hermite Normalform, wenn für
i = 1, . . . , d, j = 1, . . . , n, die folgenden Bedingungen erfüllt sind:
(a) aij ≥ 0,
(b) aij = 0 falls j > i,
(c) aij < aii für j < i.
Beispiel.

2

A= 0
1
0
4
2
0
0
9
0
0
0

0

0 
0
Falls A ∈ Zd×n nicht in Hermite Normalform ist, kann man versuchen, A durch gewisse Spaltenoperationen in Hermite Normalform zu bringen. Die folgenden Operationen heißen elementare
(unimodulare) Spaltenoperationen:
(a) Vertauschung von zwei Spalten von A,
(b) Multiplikation einer Spalte von A mit −1,
(c) Addition eines ganzzahligen Vielfachen einer Spalte von A zu einer anderen.
Bemerkung.
• Jede ganzzahlige Matrix A kann durch unimodulare Spaltenoperationen in Hermite Normalform HNF(A) überführt werden. HNF(A) wird auch Hermite Normalform von A
genannt.
• Die Hermite Normalform HNF(A) von A ist eindeutig bestimmt.
Kapitel 2. Ganzzahlige Optimierung
13
• HNF(A) kann in polynomieller Zeit (in hAi) berechnet werden.
• Ebenso kann eine (unimodulare) Transformationsmatrix U mit HNF(A) = AU in polynomieller Zeit (in hAi) berechnet werden. Dazu beachte man, dass sich jede unimodulare
Spaltenoperation auf A als Multiplikation von A mit einer unimodularen Matrix U schreiben
lässt. Damit ist HNF(A) = AU1 U2 . . . Uk =: AU für eine geeignete unimodulare Matrix U .
1 1 ) durch elementare Spaltenoperationen in Hermite
Beispiel. Wir bringen die Matrix A = ( 11 15 10
25
Normalform HNF(A) = (D|0).
1 1 ) → (1 0 0 0 ) → (1 0 0 0) →
( 11 15 10
25
1 4 9 24
1410
( 11 01 04 00 ) →
( 10 01 00 00 )
Demnach ist
HNF(A) =
1
0
0
1
0
0
0
0
!
.
Bemerkung. Man beachte, dass HNF(A) = AU1 . . . Us mit unimodularen n × n Matrizen Ui ,
die die einzelnen Spaltenoperationen kodieren, die wir auf A angewendet haben. Wir erhalten die
Matrix U := In U1 . . . Us , indem wir die gleichen Spaltenoperationen auf die Einheitsmatrix In
anwenden.
Beispiel fortgesetzt. Berechnen wir nun die Transformationsmatrix U mit HNF(A) = AU für
obiges Beispiel. Wenn wir die gleichen Spaltenoperationen auf I4 (und nicht auf A) anwenden,
erhalten wir


0
1 −5
5
 2 −2
9 −6 


U =
.
 −1
1 −4
0 
0
0
0
1
Die Hermite Normalform von A ermöglicht es uns nun, die allgemeine Lösung von Ax = b zu
finden. Zuerst finden wir eine Basis des homogenen Gleichungssystems Ax = 0.
2.1.5
Ganzzahlige Lösung von Az = 0
Im folgenden sei A ∈ Zd×n mit rang(A) = d.
Lemma 2.1.7 Seien HNF(A) = AU und u1 , . . . , un die Spalten von U . Dann bilden die letzten
n − d Spalten von U , ud+1 , . . . , un , eine Basis des Gitters kerZn (A) = {z ∈ Zn : Az = 0}.
Beweis. Aus AU = HNF(A) = (D|0) schlussfolgern wir bereits, dass Aui = 0 für i = d + 1, . . . , n,
und damit ud+1 , . . . , un ∈ kerZn (A).
2.1. Lineare diophantische Gleichungssysteme Ax = b, x ∈ Zn
14
Sei nun z ∈ kerZn (A). Wir betrachten die Gleichung
0 = Az = (AU )(U −1 z) = HNF(A)y = (D|0)y
mit y = U −1 z. Nach Konstruktion von U ist | det(U )| = 1, und nach Lemma 2.1.5 ist damit U −1
ganzzahlig. Demnach ist y ∈ kerZn (HNF(A)). Wegen der speziellen Struktur von HNF(A) (die
Spalten von D sind linear unabhängig), ist das Gitter kerZn (HNF(A)) erzeugt durch die Basis
ed+1 , . . . , en . Demnach ist z = U y eine ganzzahlige Linearkombination der Spalten ud+1 , . . . , un
von U .
Beispiel fortgesetzt. Extrahieren wir nun aus U eine Gitterbasis von kerZ4 (A). Die letzten zwei
Spalten von HNF(A) sind Nullspalten. Also bilden die letzten zwei Spalten von U ,
{(−5, 9, −4, 0)| , (5, −6, 0, 1)| },
eine Gitterbasis von kerZ4 (A).
2.1.6
Ganzzahlige Lösung von Az = b
Bestimmen wir nun eine ganzzahlige Lösung von Az = b. Aus
b = Az = (AU )(U −1 z) = HNF(A)y = (D|0)y, y = U −1 z,
bestimmen wir zuerst eine Lösung y0 von HNF(A)y = b. Solch eine Lösung y0 kann man schnell
finden, da D eine triangulare Matrix ist. Desweiteren, da D triangular (und insbesondere invertierbar) ist, unterscheiden sich je zwei Lösungenvon HNF(A)y = b nur in ihren letzten n − d
Komponenten durch eine ganzzahlige Linearkombination von ed+1 , . . . , en . Demnach existiert eine
ganzzahlige Lösung z von Az = b genau dann wenn eine ganzzahlige Lösung y0 = U −1 z0 von
HNF(A)y = b existiert. (Beachte, das U −1 eine ganzzahlige Matrix ist!) Sobald wir eine ganzzahlige Lösung y0 mit HNF(A)y0 = b gefunden haben, können wir sofort eine ganzzahlige Lösung
z0 = U y0 von Az = b finden.
!
10
Beispiel fortgesetzt. Um eine ganzzahlige Lösung von Az =
zu finden, lösen wir
110
!
10
zuerst HNF(A)y =
, was uns zum Beispiel y0 = (10, 110, 0, 0)| als ganzzahlige Lösung
110
!
10
gibt. Danach berechnen wir z0 = U y0 = (110, −200, 100, 0)| . Tatsächlich ist Az0 =
. 110
Die allgemeine Lösung von Ax = b ergibt sich nun aus der Summe einer speziellen Lösung von
Ax = b und einer ganzzahligen Linearkombination einer Gitterbasis von kerZn (A).
Kapitel 2. Ganzzahlige Optimierung
15
Beispiel fortgesetzt. Die allgemeine Lösung von Az =
10
110





z=

110
−200
100
0






 + α1 


−5
9
−4
0




 + α2 


!
ist
5
−6
0
1



,

mit α1 , α2 ∈ Z.
Zusammenfassend erhalten wir folgende wichtige Aussage.
Satz 2.1.8 Das lineare diophantische System Ax = b, x ∈ Zn kann in polynomieller Zeit gelöst
werden. Insbesondere kann zu jedem zulässigen System in polynomieller Zeit ein k ∈ N, eine
spezielle Lösung v0 und linear unabhängige Vektoren v1 , . . . , vk bestimmen, so dass
(
)
k
X
n
{x : Ax = b, x ∈ Z } = v0 +
λi vi : λ1 , . . . , λk ∈ Z .
i=1
2.1.7
Ganzzahliges Farkas-Lemma
Abschließend beweisen wir noch einen Satz, der ähnlich wie das Farkas-Lemma für lineare Gleichungsund Ungleichungssysteme die (Un-)Lösbarkeit von Ax = b, x ∈ Zn durch ein Zertifikat beschreibt.
Satz 2.1.9 (Ganzzahliges Farkas-Lemma)
Sei A ∈ Zd×n , b ∈ Zd und F = {x : Ax = b, x ∈ Zn }. Es gilt F = ∅ genau dann, wenn ein y ∈ Qd
mit y| A ∈ Zn und y| b 6∈ Z existiert.
Beweis. Sei F 6= ∅. Falls ein y ∈ Qd existieren würde mit y| A ∈ Zn und y| b 6∈ Z, dann wäre
y| Ax = y| b mit y| Ax ∈ Z und y| b 6∈ Z.
Andererseits, falls F = ∅, dann ist u = D−1 b 6∈ Zd (für HNF(A) = (D|0)). Das heißt, es existiert
ein i, so dass ui 6∈ Z. Wählt man nun y := (D−1 )i. (i-te Zeile von D−1 ), dann ist y| A ∈ Zn , aber
y| b = ui 6∈ Z.
Um y| A ∈ Zn einzusehen, beachte man, dass y| A ∈ Zn genau dann gilt, wenn y| AU ∈ Zn mit
HNF(A) = (D|0) = AU . (U ist unimodular!) Es ist aber y| AU = (D−1 )|i. (D|0) = ei ∈ Zn .
2.2
Ganzzahlige Hülle und ganzzahlige Polyeder
Durch I := (d, n, A, b, c) sei die ILP-Aufgabe max{c| x : Ax ≤ b, x ∈ Zn } spezifiziert.
Die LP-Aufgabe max{c| x : Ax ≤ b, x ∈ Rn } heißt LP-Relaxation von I.
Das Polyeder P = {x ∈ Rn : Ax ≤ b} wird das zu I zugehörige Polyeder genannt.
2.2. Ganzzahlige Hülle und ganzzahlige Polyeder
16
Bemerkung. Seien P ein Polyeder des Rn und c ∈ Rn . Dann gilt
sup c| x =
x∈P ∩Zn
c| x.
sup
x∈conv(P ∩Zn )
Dies folgt direkt aus der Definition der konvexen Hülle.
Definition 2.2.1 Sei P ein Polyeder des Rn . Dann heißt PI := conv(P ∩ Zn ) die ganzzahlige
Hülle von P .
Beispiel. Sei P das durch die Ungleichungen
x1
7x1
−
x2
+ 3x2
x2
≤
≥
≤
3
2
21
2
7
2
gegebene Polytop. Es gilt
1
1
2
2
2
3
3
4
,
,
,
,
,
,
.
P ∩Z =
,
2
3
1
2
3
2
3
3
2
Links im Bild sind P und PI zu sehen. Es sind jeweils die Maximalpunkte bzgl. der Zielfunktion
c| x = x1 + x2 zu sehen. Rechts im Bild sieht man ein anderes Polyeder Q mit QI = PI , das man
durch geeignetes Auf- bzw. Abrunden der rechten Seite im Ungleichungssystem von P erhält. Es
gilt also PI = QI ( Q ( P . Desweiteren stimmen die Optima von Q und QI überein, obwohl
Q 6= QI gilt.
PI besitzt die (irredundante) H-Darstellung
x1
x1
x1
− x2
+ x2
x2
≤ 1
≥ 3
≥ 1
≤ 3,
ist also ein Polytop. Man beachte, dass der Optimalpunkt
4
3
bzgl. PI bereits optimal bzgl. Q ist.
Kapitel 2. Ganzzahlige Optimierung
17
Beispiel. Gegeben seien die beiden ILP-Aufgaben
max
3x2
4x2
x1 , x2
x1
≤
≥
∈
4
1
Z
√
− 2x1
√
2x1
x1 ,
max
+
−
x1
x2
x2
x2
≤ 0
≤ 0
∈ Z
Die zugehörigen Polyeder seien P bzw. Q.
P ist ein horizontaler Streifen. Die Zielfunktion ist über P unbeschränkt. Da P ∩ Z2 = ∅ gilt, ist
das ILP nicht zulässig.
√
Q ist eine Gerade mit irrationaler Steigung 2. Ihr einziger Gitterpunkt ist 0. Die ILP-Aufgabe
hat das Optimum 0, während die zugehörige LP-Relaxation beliebig große Funktionswerte enthält.
Bemerkungen.
• Sei P ein Polytop im Rn . Dann ist auch PI ein Polytop.
• Sei P ein Polyeder im Rn . Dann ist PI nicht notwendigerweise wieder ein Polyeder. → Übungsaufgabe
• Falls P ein rationales Polyeder ist, so ist PI wieder ein Polyeder.
Wiederholung.
• P = {x ∈ Rn : Ax ≤ b} heißt H-Darstellung und P = conv(V ) + cone(E) + span(S) heißt
V-Darstellung von P .
• Der Kegel cone(E) + span(S) ist der Rezessionskegel, rec(P ), von P .
• Mit ls(P ) meinen wir span(S), wenn eine V-Darstellung von P nicht explizit angegeben ist.
• Oft wird cone(E) + span(S) einfach nur als cone(E, S, −S) = cone(E 0 ) geschrieben, wenn
nur die Kegeleigenschaft von cone(E) + span(S) benötigt wird.
Definition 2.2.2 Eine H-Darstellung bzw. eine V-Darstellung von eines Polyeders P heißt rational bzw. ganzzahlig, falls alle Komponenten von A und b bzw. alle Vektoren aus V , E und S
rational bzw. ganzzahlig sind.
Bemerkung. Sei P ein Polyeder mit rationaler H-Darstellung. Gilt PI 6= ∅, so folgt rec(P ) =
rec(PI ) und ls(P ) = ls(PI ).
Satz 2.2.3 Sei P ⊆ Rn . P besitzt genau dann eine rationale H-Darstellung, wenn P eine rationale
V-Darstellung besitzt.
2.2. Ganzzahlige Hülle und ganzzahlige Polyeder
18
Definition 2.2.4 Ein Polyeder P heißt rational, falls P eine rationale H-Darstellung (bzw. VDarstellung) besitzt. Ein Polyeder P heißt ganzzahlig, falls P eine ganzzahlige V-Darstellung
besitzt.
Lemma 2.2.5 Sei P = conv(V ) + cone(E) + span(S) eine irredundante V-Darstellung von P . Ist
P 6= ∅, so sind die eigentlichen Seiten von P kleinster Dimension genau die Polyeder v + span(S)
für v ∈ V .
Satz 2.2.6 Sei P ein rationales Polyeder. P ist genau dann ganzzahlig, wenn P = PI gilt.
Beweis.
=⇒ Seien V, E endliche Teilmengen von Zn mit P = conv(V ) + cone(E). Dann gilt
P = conv(V ) + conv([0, ∞)E) = conv(V + [0, ∞)E) = conv(V + Z+ E) = PI .
⇐= Sei P = conv(V ) + cone(E) + span(S) eine irredundante rationale V-Darstellung von P .
O.B.d.A. seien P 6= ∅ und E, S ⊆ Zn . Sei v ∈ V . Nach Lemma 2.2.5 ist v + span(S)
eine Seite von P . Da nach Voraussetzung P = PI ist, gibt es einen ganzzahligen Punkt
v0 ∈ v + span(S). Natürlich gilt v + span(S) = v0 + span(S). Insgesamt erhält man eine
Menge V 0 ⊆ Zn mit P = conv(V 0 ) + cone(E) + span(S), d.h., eine ganzzahlige V-Darstellung
von P .
Damit reicht es für spitze Polyeder P zu klären, wann alle Ecken von P ganzzahlig sind. Eine
Antwort darauf ist of schwierig zu erzielen und wir werden später einige hinreichende Bedingungen
für die Ganzzahligkeit von Polyedern kennenlernen.
Satz 2.2.7 Sei P ⊆ Rn ein rationales Polyeder. Dann sind folgende Aussagen äquivalent.
(a) P ist ein ganzzahliges Polyeder.
(b) Jede eigentliche Seite von P minimaler Dimension ist ein ganzzahliges Polyeder.
(c) Jede Stützhyperebene an P enthält einen Gitterpunkt.
(d) Für jeden Vektor c ∈ Rn , für den max{c| x : x ∈ P } existiert, gibt es einen Maximalpunkt
x∗ ∈ Zn .
(e) Für jeden Vektor c ∈ Rn , für den max{c| x : x ∈ P } existiert, ist der Maximalwert in Z.
Beweis. Die Aussagen (a) ⇒ (b) ⇒ (c) ⇒ (e) und (b) ⇒ (d) ⇒ (c) sind klar, und es reicht
(b) ⇒ (a) und (e) ⇒ (b) zu beweisen. Letztere Implikation ist der eigentliche Kern der Aussage.
(b) ⇒ (a). Sei P = conv(V ) + cone(E) + span(S) eine irredundante V-Darstellung von P mit
E, S ∈ Zn . Nach Lemma 2.2.5 sind v + span(S) genau die Seiten von P kleinster Dimension. Sei
Kapitel 2. Ganzzahlige Optimierung
19
wv ∈ {v + span(S)} ∩ Zn . Dann gilt v + span(S) = wv + span(S) und wir erhalten als ganzzahlige
V-Darstellung P = conv({wv : v ∈ V ) + cone(E) + span(S).
(e) ⇒ (b). Sei P = {x ∈ Rn : Ax ≤ b} eine ganzzahlige H-Darstellung von P , F eine eigentliche
Seite von P kleinster Dimension und I die Menge der Indizes der in F aktiven Nebenbedingungen.
Dann gilt
F = aff(F ) = {x ∈ Rn : AI x = bI }.
Angenommen, F enthält keinen ganzzahligen Punkt. Dann existiert nach dem Ganzzahligen FarkasLemma, Lemma 2.1.9, ein y ∈ R|I| mit
A|I y ∈ Zn und b|I y 6∈ Z.
Da AI und bI ganzzahlig sind, besitzt auch jeder Vektor y + α1 mit α ∈ Z diese Eigenschaft, so
dass wir o.B.d.A. annehmen können, dass y > 0 gilt. Seien nun
c| := y| AI und γ := y| bI .
Dann gilt
c ∈ relint(NP (F )) ∩ Zn und F = P ∩ {x ∈ Rn : c| x = γ}.
Dabei ist NP (F ) der Normalenkegel von F an P (= Normalen der Stützhyperebenen von F ). Das
Optimum von max{c| x : x ∈ P } wird damit genau in allen Punkten von F angenommen. Damit
ist also
max{c| x : x ∈ P } = max{c| x : x ∈ F } = γ ∈ Z,
im Widerspruch zu γ 6∈ Z. Also gilt F ∩ Zn 6= ∅, und insgesamt folgt die Behauptung (da jetzt
F = w + span(S) für ein w ∈ F ∩ Zn gilt).
Bemerkung. Das Problem, für ein gegebenes Polyeder P in H-Darstellung zu entscheiden, ob
P = PI gilt, ist N P-vollständig.
Bezeichnung. Für A ∈ Rd×n und b ∈ Rd sei P (A, b) := {x ∈ Rn : Ax ≤ b}.
Satz 2.2.8 Seien A ∈ Zd×n und k = rang(A). Dann sind die folgenden Aussagen äquivalent.
(a) Für jede Teilmenge I ⊆ {1, . . . , d} mit rang(AI ) = k und jedes bI ∈ Zk besitzt AI x = bI
eine ganzzahlige Lösung.
(b) Für jedes b ∈ Zd ist P (A, b) ganzzahlig.
Beweis.
(a) ⇒ (b). Seien b ∈ Zd und c ∈ Zn \ {0}, so dass max{c| x : x ∈ P (A, b)} existiert. Dann ist
F = argmax{c| x : x ∈ P (A, b)}
eine Seite von P (A, b). Sei I die Menge der Indizes aller für F aktiven Nebenbedingungen. Dann
gilt
aff(F ) = {x ∈ Rn : AI x = bI }.
2.2. Ganzzahlige Hülle und ganzzahlige Polyeder
20
Nach Voraussetzung enthält aff(F ) ganzzahlige Punkte. Nach Satz 2.2.7 ist P (A, b) somit ganzzahlig.
(b) ⇒ (a). Seien I ⊆ {1, . . . , d} mit |I| = k und rang(AI ) = k sowie bI ∈ Zk . Wir nehmen o.B.d.A.
an, dass I = {1, . . . , k} ist und setzen J := {1, . . . , d} \ I. Das Gleichungssystem AI x = bI ist über
R (oder Q) lösbar. Seien
bI
x∗ ∈ Rn , AI x∗ = bI , w := bAJ x∗ c, b :=
.
w+1
(Dabei ist bAJ x∗ c natürlich wieder komponentenweise gemeint.) Dann ist b ganzzahlig und es gilt
AI x∗ = bI und AJ x∗ < w + 1.
D.h., x∗ ∈ P (A, b) und für die Seite F (x∗ ) von x∗ in P (A, b) gilt F (x∗ ) = x∗ + ls(P (A, b)).
Somit ist x∗ + ls(P (A, b)) eine eigentliche Seite minimaler Dimension von P (A, b) und da P (A, b)
ganzzahlig ist, enthält sie einen Punkt v ∈ Zn . Es folgt AI v = bI und damit die Behauptung. Definition 2.2.9 Sei A ∈ Zd×n mit rang(A) = n. Die Matrix A heißt unimodular, wenn für
jede Teilmenge B ⊆ {1, . . . , d} mit |B| = n gilt det(AB ) ∈ {−1, 0, 1}.
1 0 Beispiel. Die Matrix 1 −1 ist unimodular, denn die drei 2 × 2 Teilmatrizen haben Determi−2 1
nanten −1, 1, bzw. −1.
Folgerung 2.2.10 Sei A ∈ Zd×n mit rang(A) = n. Dann sind die folgenden beiden Aussagen
äquivalent.
(a) A ist unimodular.
(b) Für jedes b ∈ Zd ist jede Ecke von P (A, b) ganzzahlig.
Beweis. Die Aussage folgt direkt aus Satz 2.2.8.
Definition 2.2.11 Eine Matrix A ∈ Zd×n heißt total unimodular, wenn für jede quadratische
Teilmatrix C von A gilt: det(C) ∈ {−1, 0, 1}.
Lemma 2.2.12 Sei A ∈ Zd×n total unimodular. Dann gilt A ∈ {−1, 0, 1}d×n . Ferner ist jede
Matrix A0 , die aus A durch Streichen von (bis zu d − 1) Zeilen und (bis zu n − 1) Spalten entsteht,
total unimodular.
Beweis. Die erste Aussage folgt direkt aus der Definition angewandt auf die 1 × 1-Teilmatrizen
von A. Die zweite Aussage folgt aus der Tatsache, dass jede Teilmatrix von A0 auch Teilmatrix von
A ist.
1 0 1 −1
Beispiel. Die Matrix
ist zwar unimodular aber nicht total unimodular, da nicht alle
−2 1
Einträge aus {−1, 0, 1} sind.
Kapitel 2. Ganzzahlige Optimierung
Satz 2.2.13 Die Matrix A ∈ Zd×n ist genau dann total unimodular, wenn
(In ist hierbei die n × n-Einheitsmatrix.)
21
A
In
unimodular ist.
Beweis.
=⇒ Sei C eine reguläre n × n-Teilmatrix von IAn . Durch Entwicklung der Determinante nach
den zur Einheitsmatrix gehörenden Zeilen folgt | det(C)| = 1.
⇐= Sei A0 eine reguläre quadratische Teilmatrix von A. Dann lässt sich A0 durch Hinzufügen von
Zeilen aus In und Spalten aus IAn zu einer regulären n × n-Teilmatrix C von IAn erweitern.
Nach Voraussetzung ist | det(C)| = 1. Wenn man nun die Determinante von C nach den
Teilen in In entwickelt, sieht man, dass auch | det(A0 )| = 1 gelten muss.
Folgerung 2.2.14 Die Matrix A ∈ Zd×n ist genau dann total unimodular, wenn für jeden Vektor
b ∈ Zd alle Ecken von
A
b
P
,
= {x ∈ Rn : Ax ≤ b, x ≥ 0}
−In
0
ganzzahlig sind.
Beweis.
=⇒ Nach Satz 2.2.13 und Folgerung 2.2.10 ist A genau dann total unimodular, wenn für alle
b ∈ Zd und c ∈ Zn alle Ecken von
A
b
P
,
= {x ∈ Rn : Ax ≤ b, x ≥ c}
−In
−c
ganzzahlig sind.
⇐= Wir zeigen noch, dass aus der Ganzzahligkeit der Ecken von
A
b
P
,
= {x ∈ Rn : Ax ≤ b, x ≥ 0}
−In
0
für alle b ∈ Zd die Ganzzahligkeit der Ecken von
A
b
P
,
= {x ∈ Rn : Ax ≤ b, x ≥ c}
−In
−c
für alle b ∈ Zd und c ∈ Zn folgt. Es gilt natürlich
A
b
A
b − Ac
x≤
⇐⇒
(x − c) ≤
.
−In
−c
−In
0
Da die Ganzzahligkeit der Ecken eines Polyeders invariant unter Translation um einen ganzzahligen Vektor ist, folgt die Behauptung.
2.2. Ganzzahlige Hülle und ganzzahlige Polyeder
22
Lemma 2.2.15 Sei A ∈ Zd×n und sei A0 eine der folgenden Matrizen:
A
A
A| , −A, (A|Im ),
,
.
In
−A
Dann ist A genau dann total unimodular, wenn A0 total unimodular ist.
Beweis.
=⇒ Diese Richtung ergibt sich direkt aus der Definition von A0 und aus der Definition einer total
unimodularen Matrix.
⇐= Der nichttriviale Teil der Behauptung folgt mit Hilfe von Lemma 2.2.12.
|
Satz 2.2.16 Sei A = (a1 |a2 | . . . |am ) ∈ {−1, 0, 1}d×n . Die Matrix A ist genau dann total unimodular, wenn es für jede nichtleere Indexmenge I ⊆ {1, . . . , m} eine Partition (I1 , I2 ) von I gibt
mit
X
X
ai −
ai ∈ {−1, 0, 1}n .
i∈I1
i∈I2
Beweis.
=⇒ Sei I ⊆ {1, . . . , d}, I 6= ∅ gegeben. Da wir zeigen wollen, dass für die gesuchte Partition
P
P
(I1 , I2 ) von I die beiden Summen i∈I1 ai und i∈I2 ai fast übereinstimmen, setzen wir
1 |
1 |
|
|I|
A 1 ≤ AI y ≤
A 1 ,0 ≤ y ≤ 1 .
Q := y ∈ R :
2 I
2 I
Nach Lemma 2.2.12 und Lemma 2.2.15 ist mit A auch die Matrix


A|I
 −A| 

I 


 In 
−In
total unimodular und nach Folgerung 2.2.14 ist Q ganzzahlig. Da der Vektor 12 1 in Q enthalten
ist, gilt Q 6= ∅. Damit ist Q konvexe Hülle seiner Ecken. Sei v = (v1 , . . . , v|I| )| eine Ecke von
Q. Dann gilt v ∈ {0, 1}|I| und wir setzen I1 := {i ∈ I : vi = 0} und I2 = I \ I1 . Dann gilt
nach Voraussetzung
X
1 |
1 |
|
A 1 ≤
ai = AI v ≤
A 1 .
2 I
2 I
i∈I2
Wegen
X
ai −
i∈I1
X
i∈I2
ai =
X
i∈I
ai − 2
X
ai = A|I 1 − 2A|I v
i∈I2
folgt somit
X
X
1 |
1 |
|
− 2 AI 1 ≤
ai −
ai ≤ AI 1 − 2 AI 1
2
2
i∈I1
i∈I2
P
P
und daher i∈I1 ai − i∈I2 ai ∈ {−1, 0, 1}n .
A|I 1
Kapitel 2. Ganzzahlige Optimierung
23
⇐= Wir zeigen die Determinantenbedingung für jede k × k-Teilmatrix mittels vollständiger Induktion nach k. Durch Anwendung der Partitionsbedingung auf alle Indexmengen I der
Kardinalität 1 folgt A ∈ {−1, 0, 1}d×n . Also gilt die Aussage für alle 1 × 1-Teilmatrizen. Seien nun k ≥ 2 und C eine beliebige k × k-Teilmatrix von A. Ist C singulär, so ist det(C) = 0.
Sei daher im folgenden C regulär. O.B.d.A. setzen wir voraus, dass C = (aij )i,j∈[k] gilt.
Wir zeigen nun, dass C −1 ganzzahlig ist. Sei l ∈ [k] beliebig und c| = (c1 , . . . , ck ) die l-te
Zeile von C −1 . Es gilt
1
c| = e|l C −1 =
e| adj(C).
det(C) l
und da nach Induktionsvoraussetzung alle Komponenten von adj(C) aus {−1, 0, 1} sind, folgt
det(C) · c ∈ {−1, 0, 1}k .
Seien nun I := {i ∈ [k] : ci 6= 0} und (I1 , I2 ) eine Partition von I mit
X
X
ai −
ai ∈ {−1, 0, 1}n .
i∈I1
i∈I2
Nun gilt für j ∈ [k] \ {l} natürlich
(det(C)) · c| Cej = 0.
Da alle Einträge von det(C) · c und C aus {−1, 0, 1} sind und c| C = el gilt, folgt
|{i ∈ I : aij 6= 0}| ≡ 0
(mod 2).
Somit gilt für jedes j ∈ [k] \ {l}
X
aij −
i∈I1
X
aij = 0.
i∈I2
Da C regulär ist, gilt insbesondere
X
X ail −
ail = 1.
i∈I1
i∈I2
Sei nun b = (b1 , . . . , bk )| definiert durch


 1
bi :=
−1


0
für i ∈ I1 ,
für i ∈ I2 ,
sonst,
für alle i ∈ [k]. Dann folgt b| C ∈ {−el , el }, also
b ∈ {−c, c}.
Somit ist c ∈ {−1, 0, 1}k , und da l ∈ [k] beliebig war, folgt insbesondere C −1 ∈ Zk×k , also
auch | det(C)| = 1.
2.2. Ganzzahlige Hülle und ganzzahlige Polyeder
24
Folgerung 2.2.17 Sei A ∈ {−1, 0, 1}d×n und jede Spalte von A enthalte höchstens zwei von 0
verschiedene Einträge. Die Matrix A ist genau dann total unimodular, wenn es eine Partition
(I1 , I2 ) von [d] gibt, so dass für alle i1 , i2 ∈ [d] mit i1 6= i2 und j ∈ [d] mit Ai1 ,j , Ai2 ,j 6= 0 gilt
sign(Ai1 ,j ) 6= sign(Ai2 ,j ) ⇐⇒ {i1 , i2 } ∈ I1 ∨ {i1 , i2 } ∈ I2 .
Beweis.
=⇒ Ist A total unimodular, so gibt es nach Satz 2.2.16 eine Partition (I1 , I2 ) von [d] mit
X
ai −
i∈I1
X
ai ∈ {−1, 0, 1}n .
i∈I2
Für jede Spalte mit genau zwei von 0 verschiedenen Einträgen können bei gleichem Vorzeichen die zu diesen gehörigen Zeilenindizes nicht in derselben Partitionsmenge und bei
verschiedenen Vorzeichen nicht in verschiedenen Partitionsmengen liegen. (I1 , I2 ) erfüllt also
die behauptete Bedingung.
⇐= Sind (I1 , I2 ) eine entsprechende Partition von [d] und I ⊆ [d] mit I 6= ∅, so gilt
X
i∈I1 ∩I
ai −
X
ai ∈ {−1, 0, 1}n .
i∈I2 ∩I
Nach Satz 2.2.16 ist A somit total unimodular.
Satz 2.2.18 Sei G = (V, A) ein Digraph. Dann ist seine (Knoten-Kanten-) Inzidenzmatrix SG
total unimodular.
Beweis. Jede Spalte von SG enthält genau zwei von 0 verschiedene Einträge. Da diese verschiedenes
Vorzeichen haben, setzen wir I1 := {1, 2, . . . , |V |} und I2 := ∅. Dann erfüllt (I1 , I2 ) das Kriterium
aus Folgerung 2.2.17 und SG ist somit total unimodular.
Bemerkung. Dass Problem, für gegebene Matrix A ∈ Zd×n zu entscheiden, ob A total unimodular
ist, kann in polynomieller Zeit gelöst werden.
Bemerkung. Seien G = (V, E, c) ein gewichteter Graph, V := {v1 , . . . , vn }, E := {e1 , . . . , em }
und c := (c(e1 ), . . . , c(em ))| . Dann ist jeder zulässige Punkt des ILPs
max{c| x : SG x ≤ 1, x ≥ 0, x ∈ Zm }
Inzidenzvektor eines Matchings in G und umgekehrt, und die Zielfunktionswerte stimmen überein.
Satz 2.2.19 Sei G = (V, E) ein ungerichteter Graph. Die Inzidenzmatrix SG von G ist genau
dann total unimodular, wenn G bipartit ist.
Kapitel 2. Ganzzahlige Optimierung
25
Beispiel. Gegeben sei der vollständige Graph K3 mit 3 Knoten. Gesucht ist ein kardinalitätsmaximales Matching. Da K3 nur genau 4 verschiedene Matchings enthält, nämlich
M0 := ∅,
M1 := {e1 },
M2 := {e2 },
M3 := {e3 },
ist die Aufgabe natürlich leicht zu lösen: M1 , M2 , M3 sind kardinalitätsmaximal.
Bei geeigneter Nummerierung der Knoten und Kanten ist

1

 0
1
1
1
0

0

1 
1
die Inzidenzmatrix von K3 . Ihre Determinante hat den Wert 2; die Matrix ist also nicht total
unimodular. Tatsächlich ist die (in diesem Fall eindeutig bestimmte) optimale Lösung x∗ der
zugehörigen LP-Aufgabe
max{x1 + x2 + x3 : x1 + x2 ≤ 1, x1 + x3 ≤ 1, x2 + x3 ≤ 1, x1 , x2 , x3 ≥ 0}
auch nicht ganzzahlig; es gilt


1/2


x∗ =  1/2  .
1/2
Das zugehörige Polyeder ist also nicht ganzzahlig.
Folgerung 2.2.20 Seien G ein bipartiter Graph und b ∈ Zn+ . Die Ecken des durch
max{c| x : SG x ≤ 1, x ≥ 0, x ∈ Zm }
gegebenen Polytops sind ganzzahlig.
2.3
Hilbertbasen rationaler polyedrischer Kegel, TDI-Systeme
und Chvátal-Gomory-Abschluss
In diesem Abschnitt erarbeiten wir Grundlagen für Schnittebenenverfahren zur Lösung linearer
ganzzahliger Optimierungsprobleme.
2.3. Hilbertbasen rationaler polyedrischer Kegel, TDI-Systeme und Chvátal-Gomory-Abschluss
2.3.1
26
Hilbertbasen rationaler polyedrischer Kegel
Definition 2.3.1 Sei C = {x ∈ Rn : Ax ≤ 0} ein polyedrischer Kegel. Eine endliche Menge
H ⊆ C ∩ Zn heißt Hilbertbasis von C, falls sich jeder Punkt z ∈ C ∩ Zn darstellen lässt als
(nichtnegative ganzzahlige) Linearkombination
X
z=
λi hi , λi ∈ Z+ , hi ∈ H,
von Elementen aus H.
Lemma 2.3.2 Jeder rationale polyedrische Kegel C besitzt eine Hilbertbasis. Ist C zusätzlich spitz,
so existiert eine eindeutige inklusionsminimale Hilbertbasis von C.
Beweis. Sei C = cone(v1 , . . . , vk ) mit v1 , . . . , vk ∈ Zn . Sei weiterhin
( k
)
X
F :=
λi vi : 0 ≤ λi < 1, i = 1, . . . , k .
i=1
Klar: F ∩ Zn ist beschränkt und enthält somit nur endlich viele Gitterpunkte. Sei jetzt z ∈ C ∩ Zn .
k
P
Dann gilt insbesondere z =
λi vi , λ1 , . . . , λk ≥ 0. Damit ist
i=1
z=
k
k
X
X
(bλi c − λi )vi ,
bλi cvi +
i=1
i=1
|
{z
∈F
}
also lässt sich ein beliebiges z ∈ C ∩ Zn darstellen als nichtnegative ganzzahlige Linearkombination
von Elementen aus H := {v1 , . . . , vk } ∪ F . H ist also eine Hilbertbasis von C.
Sei C nun zusätzlich spitz. Es existiert also ein c ∈ Rn , so dass C ⊆ {x ∈ Rn : c| x ≥ 0} und
C ∩ {x ∈ Rn : c| x = 0} = {0}. Sei weiterhin
R := {x ∈ C ∩ Zn \ {0} :6 ∃ y, z ∈ C ∩ Zn \ {0} mit x = y + z}
die Menge aller nicht-zerlegbaren Gitterpunkte in C. Da sich kein Punkt aus R auf nichttriviale
Weise als Summe zweier Gitterpunkte aus C darstellen lässt, muss R in jeder Hilbertbasis von C
enthalten sein. Insbesondere gilt also R ⊆ {v1 , . . . , vk } ∪ F . R ist also eine endliche Menge. Es
bleibt zu zeigen, dass R selbst schon Hilbertbasis von C ist.
Angenommen, nicht alle Gitterpunkte aus C ließen sich als nichtnegative ganzzahlige Linearkombination von Elementen aus R darstellen. Sei x ∈ C ∩ Zn ein solcher Punkt mit minimalem Wert
Kapitel 2. Ganzzahlige Optimierung
27
c| x > 0. Da x 6∈ R, lässt sich x schreiben als x = y + z mit y, z ∈ C ∩ Zn \ {0}. Es folgt
c| y, c| z < c| x. Damit sind y und z als nichtnegative ganzzahlige Linearkombinationen von Elementen aus R darstellbar und somit auch x = y + z. Widerspruch. Also ist R Hilbertbasis von C
und damit die eindeutige inklusionsminimale Hilbertbasis von C.
2.3.2
TDI-Systeme
Wir nutzen nun Hilbertbasen, um spezielle Darstellungen von Polyedern zu definieren, die sich
später als sehr nützlich herausstellen werden.
Definition 2.3.3 Sei A ∈ Zd×n , b ∈ Qd und P = {x ∈ Rn : Ax ≤ b}. Das System Ax ≤ b
heißt total dual integral oder kurz TDI, falls für jede Seite F = {x ∈ P : AI x = bI } von P die
Menge der Zeilenvektoren {Ai. : i ∈ I} eine Hilbertbasis des rationalen Kegels cone({Ai. : i ∈ I})
ist.
Bemerkung. Die Hauptidee hinter diesem Begriff ist der folgende. Sei c ein ganzzahliger Vektor,
der in dem Kegel liegt, der von den Zeilen von A erzeugt wird, so dass das Problem
min{b| y : y| A = c| , y ≥ 0}
beschränkt ist. Betrachte nun das Problem
max{c| x : x ∈ P = P (A, b)}.
Wenn c| x maximal auf einer Seite F = {x ∈ P : AI x = bI } von P ist, dann ist
c| ∈ C = cone(Ai. : i ∈ I).
Die Bedingung, dass H = {Ai. : i ∈ I} eine Hilbertbasis von C ist, ist äquivalent dazu, dass c|
P
geschrieben werden kann als c| = i∈I yi Ai. mit yi ∈ Z+ . Der Vektor y ist dann eine ganzzahlige
duale Lösung.
Satz 2.3.4 Seien A ∈ Zd×n und b ∈ Zd . Das System Ax ≤ b ist TDI genau dann, wenn das
Problem
min{b| y : y| A = c| , y ≥ 0}
für jeden Vektor c ∈ Zn , für den das Minimum angenommen wird, eine Optimallösung y ∈ Zn
besitzt.
Total unimodulare Integrität impliziert Ganzzahligkeit des primal zulässigen Bereichs.
Lemma 2.3.5 Seien A ∈ Zd×n und b ∈ Zd . Falls das System Ax ≤ b TDI ist, dann ist P (A, b)
ganzzahlig.
2.3. Hilbertbasen rationaler polyedrischer Kegel, TDI-Systeme und Chvátal-Gomory-Abschluss
28
Beweis. Sei c ∈ Zn , so dass max{c| x : Ax ≤ b} angenommen wird. Nach Dualitätssatz gilt nun
max{c| x : Ax ≤ b} = min{b| y : y| A = c| , y ≥ 0}.
Da Ax ≤ b TDI ist und b ∈ Zd gilt, ist das Minimum der rechten Seite ganzzahlig. Nach Satz
2.2.7 gilt somit P = PI .
Abschließend sei angemerkt, dass jedes rationale Polyeder P durch ein System linearer Ungleichungen beschrieben werden kann, das TDI ist. Um ein solches System zu finden, braucht man nur für
jede minimale Seite F = {x ∈ P : AI x = bI } von P eine Hilbertbasis des Kegels cone(Ai. : i ∈ I)
zu berechnen und die entsprechenden Ungleichungen der Hilbertbasis-Elemente aufzusammeln.
Satz 2.3.6 Jedes rationale Polyeder besitzt eine TDI-Beschreibung Ax ≤ b mit ganzzahliger Matrix A.
2.3.3
Chvátal-Gomory-Abschluss
Definition 2.3.7 Sei P ein Polyeder. Wir definieren
P0
=
P
P1
=
{x ∈ Rn : c| x ≤ bγc, für alle Stützhyperebenen {x ∈ Rn : c| x = γ} von P mit c ∈ Zn }.
P1 heißt der Chvátal-Gomory-Abschluss (engl.: Chvátal-Gomory closure) von P .
Klar ist zwar PI ⊆ P1 , aber es ist auf den ersten Blick nicht klar, ob P1 wieder ein Polyeder ist.
Satz 2.3.8 Sei P = {x ∈ Rn : Ax ≤ b} ein nichtleeres rationales Polyeder mit A ∈ Zd×n und
Ax ≤ b TDI. Dann ist
P1 = {x ∈ Rn : Ax ≤ bbc},
d.h., P1 ist ein Polyeder.
Beweis. Sei P 6= ∅. Da wir insbesondere {x ∈ Rn : Ai. x = bi } als Stützhyperebene nehmen
können, gilt
P1 ⊆ {x ∈ Rn : Ax ≤ bbc}.
Sei nun {x ∈ Rn : c| x = γ} eine Stützhyperebene von P mit P ⊆ {x ∈ Rn : c| x ≤ γ} und c ∈ Zn ,
γ ∈ Q. Dualität der linearen Optimierung ergibt
γ = max{c| x : Ax ≤ b, x ∈ Rn } = min{y| b : y| A = c| , y ≥ 0}.
Da Ax ≤ b TDI ist, existiert eine ganzzahlige optimale Lösung y∗ von
min{y| b : y| A = c| , y ≥ 0}.
Kapitel 2. Ganzzahlige Optimierung
29
Falls x das System Ax ≤ bbc erfüllt, dann gilt
c| x = ((y∗ )| A)x = (y∗ )| (Ax) ≤ (y∗ )| bbc ≤ b(y∗ )| bc = bγc.
Dies impliziert
{x ∈ Rn : Ax ≤ bbc} ⊆ {x ∈ Rn : c| x ≤ bγc}
und somit
{x ∈ Rn : Ax ≤ bbc} ⊆
\
{x ∈ Rn : c| x ≤ bγc} = P1 ,
c,γ
wobei der Durchschnitt über all jene Stützhyperebenen {x ∈ Rn : c| x = γ} gebildet, wird für die
c ∈ Zn und P ⊆ {x ∈ Rn : c| x ≤ γ} gilt.
Da P1 wieder ein Polyeder ist, können wir den Prozess iterieren.
Definition 2.3.9 Sei P ein rationales Polyeder. Für t ∈ Z+ , t ≥ 1, definieren wir
Pt+1 = (Pt )1 .
Es ist klar, dass
P = P0 ⊇ P1 ⊇ P2 ⊇ . . . ⊇ PI .
Aber existiert auch immer ein endliches t, so dass Pt = PI gilt?
Satz 2.3.10 Sei P ein rationales Polyeder. Dann existiert eine natürliche Zahl t ∈ Z+ , so dass
Pt = PI .
Diese endliche Zahl wird auch der Chvátal-Gomory-Rang von P genannt.
Zusammenfassend kann man für rationale Polyeder P das Auffinden einer linearen Ungleichungsbeschreibung für PI wie folgt beschreiben:
• Sei Ax ≤ b eine Ungleichungsbeschreibung für P .
• Berechne eine TDI-Beschreibung Dx ≤ d für P .
• Setze P1 = {Dx ≤ bdc} und iteriere, um P2 , P3 , . . . zu erhalten.
• Sobald Pt = Pt+1 gilt, haben wir PI = Pt gefunden.
2.4. Schnittebenen-Verfahren
2.4
30
Schnittebenen-Verfahren
Wir betrachten das ganzzahlige Optimierungsproblem
max{c| x : Ax ≤ b, x ∈ Zn }
mit A ∈ Zd×n , b ∈ Zd und c ∈ Zn . Es sei
P = {x ∈ Rn : Ax ≤ b} =
6 ∅.
Desweiteren nehmen wir an, dass P beschränkt ist und dass A Zeilenrang n hat. (P sei also ein
spitzes Polytop.)
Definition 2.4.1 Für x, y ∈ Rn ist x ≺lex y, falls ein j ∈ [n] existiert mit xi = yi , i = 1, . . . , j − 1
und xj < yj .
Schnittebenen-Algorithmus.
Input: Matrix A ∈ Zd×n mit Zeilenrang n, Vektoren b ∈ Zd und c ∈ Zn
Output: Eine optimale Lösung x∗ von max{c| x : Ax ≤ b, x ∈ Zn }
1. Sei t := 0, b0 := b, A0 := A, P0 := {x ∈ Rn : A0 x ≤ b0 }.
2. Löse lexmax{c| x : x ∈ Pt }.
(a) Falls Pt = ∅, dann ist das IP nicht lösbar. STOP.
(b) Sonst, sei xt die eindeutige optimale Lösung.
3. Falls xt ∈ Zn , return xt , STOP.
4. Sei I die Indexmenge der mit Gleichheit erfüllten Ungleichungen, a|i x∗ = bi , i ∈ I.
5. Sei Ht = {h1 , . . . , hk } eine Hilbertbasis des Normalenkegels
(
)
X
C := x ∈ Rn : x =
yi ai , yi ≥ 0, i ∈ I
i∈I
an xt . Sei Ht ∈ Zk×n eine Matrix, dessen Zeilen gerade die Vektoren hi , i = 1, . . . , k, sind.
6. Seien At+1 und bt+1 die Matrix und rechte Seite des folgenden Systems von linearen Ungleichungen:
"
#
"
#
At
bt
x≤
.
Ht
(bh|1 xt c, . . . , bh|k xt c)|
7. Setze t := t + 1 und gehe zu Schritt 2.
Kapitel 2. Ganzzahlige Optimierung
31
Beispiel. Wenden wir diesen Algorithmus auf das folgende IP an:
max{−x1 + 2x2 : −4x1 + 6x2 ≤ 9, x1 + x2 ≤ 4, x1 , x2 ∈ Z+ }.
Optimale Lösung der LP-Relaxierung ist x∗ = 15/10
. Die Ungleichungen −4x1 +6x2 ≤ 9, x1 +x2 ≤
25/10
4 sind mit Gleichheit erfüllt. Der Normalenkegel an x∗ ist
C
= {(d1 , d2 )| = (−4y1 + y2 , 6y1 + y2 )| , y1 , y2 ≥ 0}
= {(d1 , d2 )| : −d1 + d2 ≥ 0, 3d1 + 2d2 ≥ 0 ≥ 0}.
0 −1 −2 1
|
Die Hilbertbasis von C ist H =
1 , 2 , 3 , 1 . Die zugehörigen Ungleichungen h x ≤
| ∗
bh x c sind
x2 ≤ 2,
−x1 + 2x2 ≤ 3,
−2x1 + 3x2 ≤ 4,
x1 + x2 ≤ 4.
Fügen wir diese Ungleichungen zum Problem hinzu und lösen das neue LP, erhalten wir die optimale
IP-Lösung 12 .
Der Schnittebenen-Algorithmus erzeugt eine Familie von Polyedern Pt mit der Eigenschaft
P0 ⊃ P1 ⊃ P2 ⊃ . . . ⊃ P0 ∩ Zn .
Insbesondere ist P1 das im Schnittebenen-Algorithmus erzeugte Polyeder.
Satz 2.4.2 Der Schnittebenen-Algorithmus termininiert nach einer endlichen Anzahl an Schritten.
2.5
Gomory-Schnitte
Definition 2.5.1 Jede Ungleichung der Form
y| Ax ≤ by| bc
heißt (von y erzeugter) Rundungsschnitt oder kurz R-Schnitt. Ist y| b 6∈ Z, so heißt der RSchnitt eigentlich.
Notation. Für α ∈ R sei hαi := α − bαc ∈ [0, 1).
Satz 2.5.2 Seien x∗ eine Basislösung der LP-Aufgabe max{c| x : Ax ≤ b}, B eine zugehörige
Basis, N := [d] \ B und v ∈ Zn . Ferner seien
|
∗
∗
| ∗
y∗ ∈ Rd , y∗B := (A−1
B ) v , yN := 0, q := A y .
Dann gilt
|
n
q∗ = v − A|B (A−1
B ) v ∈ NP (B) ∩ Z .
Die Ungleichung
(q∗ )| x ≤ b(q∗ )| x∗ c
ist ein Rundungsschnitt und es gilt h(q∗ )| xi = hv| x∗ i. Ist v| x∗ 6∈ Z, so ist der R-Schnitt eigentlich.
2.5. Gomory-Schnitte
32
Beweis. Es gilt y∗ ≥ 0 sowie
∗ |
(q∗ )| x = (y∗ )| Ax, (q∗ )| x∗ = (q∗ )| A−1
B bB = (y ) b.
y erzeugt also den R-Schnitt
(q∗ )| x ≤ b(q∗ )| x∗ c.
Ferner ist q∗ = A| y∗ = A|B y∗B ∈ NP (B) sowie
j
|
| k
q∗ = A|B y∗B = A|B A−1
v − A−1
v = v − A|B A−1
v ∈ Zn .
B
B
B
Da v| A−1
bB ganzzahlig ist, gilt weiter
B
=
j
| k| ∗ E
v − A|B A−1
v
x
B
| ∗ | −1 v x − v AB AB x ∗
| ∗ | −1 v x − v AB bB
=
hv| x∗ i
h(q∗ )| x∗ i =
=
D
Der Schnitt erhält also den fraktionalen Anteil von v| x∗ und ist somit genau dann eigentlich, wenn
v| x∗ 6∈ Z gilt.
Definition 2.5.3 Seien A ∈ Zd×n , b ∈ Zd , c ∈ Zn , x∗ eine optimale Basislösung der LP-Aufgabe
max{c| x : Ax ≤ b}, B eine zugehörige optimale Basis, N := [d] \ B und v ∈ Zn mit v| x∗ 6∈ Z.
Ferner seien y∗ definiert durch
|
∗
y∗B := (A−1
B ) v , yN := 0
und q∗ := A| y∗ . Dann heißen
(q∗ )| x ≤ b(q∗ )| x∗ c bzw. (y∗ )| Ax ≤ b(y∗ )| Ax∗ c
Gomory-Schnitt und q∗ Gomory-Schnittvektor zu v. Sind i ∈ [n] und x∗i 6∈ Zn , so heißt der
Gomory-Schnitt zum Vektor v := ei auch Gomory-Schnitt zur i-ten Komponente. Ist c| x∗ 6∈
Z, so heißt der Gomory-Schnitt zum Vektor v := c auch Gomory-Schnitt zur Zielfunktion.
Bemerkung. Seien A ∈ Zd×n , b ∈ Zd , c ∈ Zn , P := {x : Ax ≤ b}, x∗ eine optimale Basislösung
der LP-Aufgabe max{c| x : Ax ≤ b}, B eine zugehörige optimale Basis, N := [d] \ B und v ∈ Zn
mit v| x∗ 6∈ Z. Der Gomory-Schnitt zu v hat die Form
∗
v| x ≤ bv| x∗ c − bv| A−1
B cAB (x − x).
Ist v = ei , so gilt insbesondere
xi − e|i A−1
AB x ≤ bxi c − ei A−1
bB .
B
B
Diese Aussage folgt direkt aus Satz 2.5.2.
Kapitel 2. Ganzzahlige Optimierung
33
Gomory-Schnittebenen-Algorithmus.
Input: A ∈ Zd×n , b ∈ Zd , c ∈ Zn , P := {x : Ax ≤ b}, optimale Basislösung x∗ mit zugehöriger
Basis B von lexmax{c| x : Ax ≤ b}
Output: Meldung “P ∩ Zn = ∅” oder eine optimale Lösung von max{c| x : x ∈ P ∩ Zn }
1. Ist x∗ ∈ Zn , gib x∗ als Optimallösung zurück. STOP.
2. Ist c| x∗ 6∈ Z, setze v := c. Ansonsten setze v := ei für ein minimales i ∈ [n] mit xi 6∈ Z.
3. q sei der Normalenvektor des Gomory-Schnittes zu u.
4. Setze
A :=
A
b
,
b
:=
.
q|
bq| x∗ c
5. P := {x : Ax ≤ b}
6. Ist P = ∅, melde “P ∩ Zn = ∅”. STOP.
7. Anonsten seien x∗ optimale Basislösung von lexmax{c| x : Ax ≤ b} und B zugehörige Basis.
8. Springe zu 1.
Satz 2.5.4 Seien A ∈ Zd×n , b ∈ Zd , c ∈ Zn und P := {x : Ax ≤ b} beschränkt. Dann löst der
Gomory-Schnittebenen-Algorithmus das Problem
max{c| x : Ax ≤ b, x ∈ Zn }
in endlich vielen Schritten.
2.6
Branch-and-Bound Algorithmus
Beginnen wir mit einem motivierenden Beispiel für die Lösung eines linearen ganzzahligen Optimierungsproblems mittels des Branch-and-Bound Algorithmus.
Beispiel. Wir möchten das Problem
c∗ = max{−x1 + 2x2 : −4x1 + 6x2 ≤ 9, x1 + x2 ≤ 4, x1 , x2 ∈ Z+ }
lösen. Die optimale Lösung der LP-Relaxierung ist x0 = 3/2
. Wir teilen nun unser Originalpro5/2
blem mittels der Ungleichungen x2 ≥ 3 und x2 ≤ 2 in zwei neue (disjunkte) Teilprobleme F1 und
F2 . Unsere gesuchte Optimallösung des Originalproblems ist nun die bessere der Optimallösungen
von F1 und F2 .
2.6. Branch-and-Bound Algorithmus
max c|
x0
34
max c|
x0
max c|
x0
Die lineare Relaxierung von F1 hat einen leeren Lösungsbereich. Wir können daher dieses Teilproblem verwerfen.
Die lineare Relaxierung von F2 hat als optimale Lösung x2 = 3/4
2 . Wir teilen daher F2 mittels
der Ungleichungen x1 ≥ 1 und x1 ≤ 0 weiter in zwei neue (disjunkte) Teilprobleme F3 und F4 .
Die optimale Lösung der LP-Relaxierung von F3 ist x3 = 12 ∈ Z2 . Damit haben wir eine obere
Schranke für unser originales Minimierungsproblem gefunden. Damit ist c∗ ≥ 3.
0
Die optimale Lösung der LP-Relaxierung von F4 ist x4 = 3/2
. Ihr Zielfunktionswert ist 3. Damit
hat eine optimale ganzzahlige Lösung von F4 auch höchstens den Zielfunktionswert 3. Da wir bereits
eine ganzzahlige Lösung mit Zielfunktionswert 3 kennen, brauchen wir F4 nicht weiter betrachten.
Die Liste der noch zu betrachtenden Teilprobleme ist nun leer. Unser IP hat als Optimallösung
x∗ = x3 = 12 .
Betrachten wir also das Problem
max{c| x : x ∈ F}
wobei wir annehmen, dass F = {x ∈ Zn : Ax ≤ b}. Wir unterteilen F̄ in eine Anzahl von
Teilmengen F̄1 , . . . , F̄k und lösen die Teilprobleme
max{c| x : x ∈ Fi }, i = 1, . . . , k,
und vergleichen die Optimallösungen, um die Optimallösung des Originalproblems zu finden. Wenn
nötig, werden die Teilprobleme iterativ weiter unterteilt. Zu jedem Zeitpunkt haben wir also eine
Liste aktiver Teilprobleme, die noch zu lösen sind.
Wir nehmen weiterhin an, dass wir für einen effizienten Algorithmus kennen, der für jedes Teilproblem Fi eine obere Schranke u(Fi ) für den optimalen Zielfunktionswert des Teilproblems Fi
Kapitel 2. Ganzzahlige Optimierung
35
berechnet, d.h.,
max{c| x : x ∈ Fi } ≤ u(Fi ).
Von Zeit zu Zeit werden in Teilproblemen zulässige Lösungen generiert, die uns eine untere Schranke
L für den gesuchten optimalen Zielfunktionswert liefern, d.h.,
max{c| x : x ∈ F} ≥ L.
Sollte für ein Teilproblem Fi gelten u(Fi ) ≤ L, so gilt
max{c| x : x ∈ Fi } ≤ u(Fi ) ≤ L ≤ max{c| x : x ∈ F},
und damit braucht dieses Teilproblem nicht weiter untersucht zu werden, da in diesem Teilproblem
keine bessere Lösung als die bisher beste bekannte Lösung gefunden werden kann.
Damit lässt sich der Branch-and-Bound Algorithmus wie folgt beschreiben. Am Anfang setzen wir
L = − inf.
Branch-and-Bound Algorithmus.
1. Wähle ein aktives Teilproblem Fi .
2. Falls das Teilproblem nicht lösbar ist, lösche es; ansonsten berechne u(Fi ).
3. Falls u(Fi ) ≤ L, lösche das Teilproblem.
4. Falls u(Fi ) < L, berechne entweder eine optimale Lösung des Teilproblems oder teile Fi in
weitere Teilprobleme, die zur Liste der aktiven Teilprobleme hinzugefügt werden.
Diese recht allgemeine Darstellung des Algorithmus enthält einige freie “Parameter”, deren beste
Wahl erfahrungs- und problemabhängig sind.
(a) Es gibt verschiedene Möglichkeiten, das nächste aktive Teilproblem auszuwählen. Zwei extremale Möglichkeiten sind “breadth-first search” und “depth-first search”.
(b) Neben der linearen Relaxierung gibt es weitere Wege, obere Schranken u(Fi ) zu finden.
(c) Es gibt diverse Wege, ein Problem in Teilprobleme zu zerlegen.
2.7
Branch-and-Cut Algorithmus
Eine Variante des Branch-and-Bound Algorithmus verwendet Schnitte, um Formulierungen und
damit die Schranken u(Fi ) in Teilproblemen zu verbessern. Wir verdeutlichen dies an obigem
Beispiel.
Beispiel. Wie oben zerlegen wir das Ausgangsproblem
max{−x1 + 2x2 : −4x1 + 6x2 ≤ 9, x1 + x2 ≤ 4, x1 , x2 ∈ Z+ }
2.7. Branch-and-Cut Algorithmus
36
in Teilprobleme F1 (mit x1 ≥ 3) und F2 (mit x1 ≤ 2) und verwerfen Teilproblem F1 als nicht lösbar.
Nun fügen wir zu F2 den Schnitt −x1 + x2 ≤ 1 hinzu. Die optimale Lösung der LP-Relaxierung
ist nun 12 ∈ Z2 und wir brauchen das Teilproblem F2 nicht weiter zu teilen.