📕
Notes
Deel 1: Geheeltallige programmering (IP)
Preemptive Programming: Er bestaat een Hierarchie tijdens de objectieven.
Cutting-plane Algoritme:
Tailing off: Optiamle doelfunctie waarde zal afvlakken naarmate aantal toegevoegde sneden ∞ nadert; laatste x
iteraties geen significante verbetering in de LP-bound.
Branch-and-cut: combinatie branch and bound met cuts.
Snedes zijn sterker als ze meer van de LP-oplossingsruimte wegsnijden.
Gomory Snedes: bewaart alle geheeltallige oplossing.
Maak gomory-snede-equatie enkel van de equatie(s) met fractionele oplossing(en).
Voorbeeld: x1 − 14 s1 + 64 s3 = 3
4 ⇒ ⌊x1 ⌋ + ⌊− 14 s1 ⌋ + ⌊ 64 s3 ⌋ = ⌊ 34 ⌋ ⇒ x1 − s1 + s3 ≤ 0
Niet-nul snedes:
∑ xi ≥ 1 voor alle nonbasic variabelen.
DFJ-Formulering (Subtour Eliminatie): 2 formuleringen zijn even sterk (LP-relaxaties hebben zelfde
oplossingsruimte)
Sterker dan MTZ formulering:
Wordt sneller groter in rekentijd dan MTZ: 2n
∑ x{i,j} ≥ 2 met S ∈ N, 2 ≤ ∣S∣ < ∣N∣
De 2 subtours moeten verbonden zijn met elkaar met minstens 2 ‘links’.
∑ x{i,j} ≤ ∣S∣ − 1 met S ∈ N, 2 ≤ ∣S∣ < ∣N∣
Het aantal links/paden in een cluster moet kleiner zijn ∣S∣ − 1 met S het aantal knooppunten, om zo subtours
te vermijden.
Comb Inequality: Subgraaf met x{1,2} + x{1,3} + x{1,4} + x{2,3} + x{2,5} + x{3,6} ≤ 4
Met 4 het aantal bogen dat ge maximaal kunt gebruiken om een loop/lus te doorlopen.
Subgraaf lijkt op een kam, comb.
MTZ-Formulering: Voor asymmetrische TSP.
Zwakker dan DF J .
u3 ≥ u2 + 1 − M(1 − x23 )
u4 ≥ u3 + 1 − M(1 − x34 )
u2 ≥ u4 + 1 − M(1 − x42 )
Notes 1
, Als er een pijl is tussen 4 en 2 ⇒ x42 ; dan moet u2 groter zijn dan u4 +1
Als er geen pijl is tussen 4 en 2 ⇒ x42 ; dan is u2 vrij, (moet groter zijn dan −M ) met M groot.
Deel 2: Combinatorische Optimalisatie (Dynamische
Programmering)
Kortste pad vanuit één knooppunt naar alle andere:
Langste pad doorheen G(N, A) = Kritiekste pad:
Earliest Start (ES): Voorwaarste DP
Latest Start (LS): Achterwaartse DP
( )
ES
LS
DP-recursie: Als G acyclisch
Achterwaarts (DP recursie):
T ijdscomplexiteit : O(m)
f(i) = waardefunctie (afstand van node(i) tot node(9))
Initialisatie : f(9) = 0; f(8) = 7; f(7) = 4; f(6) = 5
f(5) = min(2 + f(8); 6 + f(7)) = min(9; 10) = 9
f(4) = min(4 + f(7); 1 + f(6)) = min(8; 6) = 6
f(2) = min(2 + f(5); 4 + f(4)) = min(11; 10) = 10
f(3) = 3 + f(5) = 12
f(1) = min(3 + f(3); 5 + f(2)) = min(15; 15) = 15
Voorwaarts (DP):
Notes 2
, f(i) = waardefunctie (afstand van node(i) tot node(1))
Initialisatie : f(1) = 0
f(2) = 5; f(3) = 3
f(5) = min{f(3) + 3; f(2) + 2}
...
Gevraagd : f(9) = min{f(8) + 7; f(7) + 4; f(6) + 5}
Dijkstra: wel cycli
Rekentijd/Tijdscomplexiteit: O(n²) :
O(n x n) : checken in elke iteratie of de getallen kleiner zijn.
+O(m) : Elk van de pijlen gaat maar 1x gebruikt worden
Iteratie 1 2 3 4 5 6
0 0* Infinity Infinity Infinity Infinity Infinity
1 0* 5 3* Infinity Infinity Infinity
2 0* 5* 3* Infinity 6 Infinity
3 0* 5* 3* 9 6* Infinity
4 0* 5* 3* 9 6* Infinity
5 0* 5* 3* 9* 6* Infinity
6 0* 5* 3* 9* 6* 10*
7 0* 5* 3* 9* 6* 10*
8 0* 5* 3* 9* 6* 10*
Met i∗ = permanent gemaakt.
Ge gaat altijd verder van de node die net permanent gemaakt is.
Als ge een waarde vind voor node(i) bij iteratie j die groter is dan bij iteratie j − 1, dan laat ge de kleinste
waarde staan.
Bellman-Ford: Opsporen negatieve Lus
Notes 3
Notes
Deel 1: Geheeltallige programmering (IP)
Preemptive Programming: Er bestaat een Hierarchie tijdens de objectieven.
Cutting-plane Algoritme:
Tailing off: Optiamle doelfunctie waarde zal afvlakken naarmate aantal toegevoegde sneden ∞ nadert; laatste x
iteraties geen significante verbetering in de LP-bound.
Branch-and-cut: combinatie branch and bound met cuts.
Snedes zijn sterker als ze meer van de LP-oplossingsruimte wegsnijden.
Gomory Snedes: bewaart alle geheeltallige oplossing.
Maak gomory-snede-equatie enkel van de equatie(s) met fractionele oplossing(en).
Voorbeeld: x1 − 14 s1 + 64 s3 = 3
4 ⇒ ⌊x1 ⌋ + ⌊− 14 s1 ⌋ + ⌊ 64 s3 ⌋ = ⌊ 34 ⌋ ⇒ x1 − s1 + s3 ≤ 0
Niet-nul snedes:
∑ xi ≥ 1 voor alle nonbasic variabelen.
DFJ-Formulering (Subtour Eliminatie): 2 formuleringen zijn even sterk (LP-relaxaties hebben zelfde
oplossingsruimte)
Sterker dan MTZ formulering:
Wordt sneller groter in rekentijd dan MTZ: 2n
∑ x{i,j} ≥ 2 met S ∈ N, 2 ≤ ∣S∣ < ∣N∣
De 2 subtours moeten verbonden zijn met elkaar met minstens 2 ‘links’.
∑ x{i,j} ≤ ∣S∣ − 1 met S ∈ N, 2 ≤ ∣S∣ < ∣N∣
Het aantal links/paden in een cluster moet kleiner zijn ∣S∣ − 1 met S het aantal knooppunten, om zo subtours
te vermijden.
Comb Inequality: Subgraaf met x{1,2} + x{1,3} + x{1,4} + x{2,3} + x{2,5} + x{3,6} ≤ 4
Met 4 het aantal bogen dat ge maximaal kunt gebruiken om een loop/lus te doorlopen.
Subgraaf lijkt op een kam, comb.
MTZ-Formulering: Voor asymmetrische TSP.
Zwakker dan DF J .
u3 ≥ u2 + 1 − M(1 − x23 )
u4 ≥ u3 + 1 − M(1 − x34 )
u2 ≥ u4 + 1 − M(1 − x42 )
Notes 1
, Als er een pijl is tussen 4 en 2 ⇒ x42 ; dan moet u2 groter zijn dan u4 +1
Als er geen pijl is tussen 4 en 2 ⇒ x42 ; dan is u2 vrij, (moet groter zijn dan −M ) met M groot.
Deel 2: Combinatorische Optimalisatie (Dynamische
Programmering)
Kortste pad vanuit één knooppunt naar alle andere:
Langste pad doorheen G(N, A) = Kritiekste pad:
Earliest Start (ES): Voorwaarste DP
Latest Start (LS): Achterwaartse DP
( )
ES
LS
DP-recursie: Als G acyclisch
Achterwaarts (DP recursie):
T ijdscomplexiteit : O(m)
f(i) = waardefunctie (afstand van node(i) tot node(9))
Initialisatie : f(9) = 0; f(8) = 7; f(7) = 4; f(6) = 5
f(5) = min(2 + f(8); 6 + f(7)) = min(9; 10) = 9
f(4) = min(4 + f(7); 1 + f(6)) = min(8; 6) = 6
f(2) = min(2 + f(5); 4 + f(4)) = min(11; 10) = 10
f(3) = 3 + f(5) = 12
f(1) = min(3 + f(3); 5 + f(2)) = min(15; 15) = 15
Voorwaarts (DP):
Notes 2
, f(i) = waardefunctie (afstand van node(i) tot node(1))
Initialisatie : f(1) = 0
f(2) = 5; f(3) = 3
f(5) = min{f(3) + 3; f(2) + 2}
...
Gevraagd : f(9) = min{f(8) + 7; f(7) + 4; f(6) + 5}
Dijkstra: wel cycli
Rekentijd/Tijdscomplexiteit: O(n²) :
O(n x n) : checken in elke iteratie of de getallen kleiner zijn.
+O(m) : Elk van de pijlen gaat maar 1x gebruikt worden
Iteratie 1 2 3 4 5 6
0 0* Infinity Infinity Infinity Infinity Infinity
1 0* 5 3* Infinity Infinity Infinity
2 0* 5* 3* Infinity 6 Infinity
3 0* 5* 3* 9 6* Infinity
4 0* 5* 3* 9 6* Infinity
5 0* 5* 3* 9* 6* Infinity
6 0* 5* 3* 9* 6* 10*
7 0* 5* 3* 9* 6* 10*
8 0* 5* 3* 9* 6* 10*
Met i∗ = permanent gemaakt.
Ge gaat altijd verder van de node die net permanent gemaakt is.
Als ge een waarde vind voor node(i) bij iteratie j die groter is dan bij iteratie j − 1, dan laat ge de kleinste
waarde staan.
Bellman-Ford: Opsporen negatieve Lus
Notes 3
