Operationeel Onderzoek Samenvatting (HIR) (D0H28A) (16/20)

📕
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