SAMENVATTING:
Les 1: Alloceren van beperkte middelen:
1.1: Knapzak probleem:
Voorbeeld:
Gegeven:
Je krijgt € 10.000 als je afstudeert.
Je moet kiezen waar je dat geld aan besteedt. (bv. reis, nieuwe wagen,...)
Ieder alternatief heeft een kost en een portie geluk dat erbij komt.
Je moet je geld zo verdelen, dat je geluk (binnen het budget) gemaximaliseerd is.
Formulering:
Gegeven:
n objecten, met voor ieder object i ∈ {1,...,n}:
-een positief nut (geluk) ui
-een positief gewicht (kost) wi
-een positieve capaciteit van b eenheden
Doel:
Maximaliseer geluk binnen de beschikbare capaciteit
Formulering:
NP-hard:
Een probleem is NP-hard als het minstens even
moeilijk is als de moeilijkste problemen in NP.
Het 0-1 knapzakprobleem is (NP-compleet, en dus
ook) NP-hard, omdat het zoeken naar de optimale
oplossing (maximale waarde binnen een beperking)
niet efficiënt op te lossen is met een algoritme in
polynomiale tijd.
Dat betekent dat, zolang P ≠ NP, er geen snel
algoritme bestaat dat altijd de beste oplossing vindt.
Exact oplossing van het 0-1 knapzak probleem:
→ Branch & Bound: time complexity = 2n
→ Dynamische programmering: time complexity = nb
! worst case rekentijd voor beide methoden: exponentieel in grootte van input
,
1.2: Afrondingsheuristiek gebaseerd op de LP relaxation:
LP relaxatie: Wat als objecten opdeelbaar zijn?:
= Wat als je delen van objecten (met het bijbehorende deel van het geluk) in de
knapzak kan meenemen door enkel dat deel van de kost te betalen?
=> Het is dus niet meer “all or nothing” per object.
=> De binaire beperking in de formulering wordt aangepast:
=> Dit geeft een LP relaxatie, wat de oplossingsverzameling groter kan maken.
=> Efficiënt oplosbaar: sorteer items van groot naar klein volgens ratio ui/wi.
=> Vul de knapzak in deze volgorde tot hij vol zit.i
=> Oplossing LP relaxatie:
=> alle BV = gehele getallen? Gelijk aan het originele optimum.
=> Minstens 1 BV = fractioneel? Bovengrens voor het originele optimum.
=> Feasible oplossing krijgen via bv. afrondingsheuristiek:
-items met x = 1 behouden
-items met x = 0 negeren
-items met 0 < x < 1 afronden naar beneden obv.
hun waarde en het resterende beschikbare gewicht
Voorbeeld LP-relaxatie:
Formulering: Tabel met ratio en oplossing:
=> Oplossing LP-relaxatie: X(LPR) = (3/4 ; 0 ; 1 ; 1 ; 1 ; 1), met Z(LPR) = 15
=> Afrondingsheuristiek: rond de waarde voor x1 af naar beneden
Oplossing: X(AFR) = (0 ; 0 ; 1 ; 1 ; 1 ; 1), met Z(AFR) = 12
⇔ Optimale oplossing: X(OPT) = (1 ; 0 ; 1 ; 1 ; 0 ; 1), met Z(OPT) = 14
Prestatie van heuristiek evalueren?
-Ofwel obv. vergelijking met andere heuristieken
-Ofwel door de DFW van de gevonden oplossing te vergelijken met een duale grens!
1.3: Relaxatie en duale grenzen:
Wat is een duale grens?:
Veel optimalisatiealgoritmes berekenen boven- en ondergrenzen op de optimale
waarde totdat deze grenzen voldoende convergeren.
Voor een maximalisatieprobleem:
=> ondergrens = primale grens, > toelaatbare (feasible) oplossing
=> bovengrens = duale grens, > oplossen van relaxatie
Voor een minimalisatieprobleem:
=> bovengrens = primale grens, > toelaatbare (feasible) oplossing
=> ondergrens = duale grens, > oplossen van relaxatie
,Relaxaties:
Visualisatie:
=> P geeft het originele probleem weer, R de relaxatie. Het
optimum van R ligt boven dat van P, want het is een maximalisatie.
=> Ideaal liggen g en f dicht bij elkaar, want dan: sterke grens!
=> MAAR trade-off tussen rekentijd en kwaliteit van grens!
2 voorwaarden:
1: De oplossingsruimte van de relaxatie is minstens
even groot: Alle oplossingen die bij het originele
probleem toelaatbaar zijn, zijn nog steeds toelaatbaar.
2: (Bij maximalisatie:) Iedere toelaatbare oplossing van
het originele probleem geeft bij de relaxatie een DFW
die minstens even groot is.
3 manieren om te relaxeren:
1) Maak een beperking “zwakker” door het RL aan te passen
2) Verwijder een beperking, maar integreer hem in de doelfunctie
3) Vervang de binaire beperking door “0 <= xi <= 1”
Voorbeeld
Relaxatie geeft steeds een duale grens:
!!! g(xᵖ) is niet per se gelijk aan zʳ:
xᵖ ligt ook in Y (want X ⊆ Y), dus je
mag xᵖ ook invullen in g(x). MAAR
misschien is er binnen Y een nog
betere oplossing voor g(x).
Relaxatie geeft soms ook bewijs van optimaliteit:
zie “waarom?” slide 20, idk
, 1.4: Prestatiegarantie van heuristieken:
Tekening en informatie uit de les:
Worst-case analyse: Wat is het verste dat we
(procentueel) kunnen afzitten van de ideale
oplossing bij het uitvoeren van het algoritme?
-Voor 1 probleem, meerdere algoritmes mogelijk
-Complexiteit van je probleem is niet per se gelijk
aan de complexiteit van je bijhorende algoritmen
--> bv het knapzak probleem is NP hard,
afrondingsheuristiek is O(n log n), B&B is 2^n,...
Prestatie van de afrondingsheuristiek:
De afrondingsheuristiek kan willekeurig slecht presteren. (zie voorbeeld dia 24)
= oneindige prestatiegarantie
=> Als je dus echt pech hebt, kan je er oneindig ver af zitten.
=> Gegeven een capaciteit k, kan de verhouding tussen het geheeltallige
optimum en en het optimum van de relaxatie onbegrensd groot worden:
Prestatie van de alternatieve heuristiek:
= greedy heuristiek, net zoals de afrondingsheuristiek: zo’n heuristiek kiest
in iedere iteratie voor de actie die het meeste onmiddellijke winst oplevert
De alternatieve heuristiek kan OOK willekeurig slecht presteren. (zie voorbeeld dia 26)
= oneindige prestatiegarantie
Prestatie van de Greedy 2.0 heuristiek:
De Greedy 2.0 heuristiek heeft een
prestatiegarantie van factor 2:
Voor iedere instantie van het
probleem is de optimale DFW
maximaal het dubbele van het nut
bekomen met de Greedy 2.0
heuristiek.
zie ook oefening dia 33
Les 1: Alloceren van beperkte middelen:
1.1: Knapzak probleem:
Voorbeeld:
Gegeven:
Je krijgt € 10.000 als je afstudeert.
Je moet kiezen waar je dat geld aan besteedt. (bv. reis, nieuwe wagen,...)
Ieder alternatief heeft een kost en een portie geluk dat erbij komt.
Je moet je geld zo verdelen, dat je geluk (binnen het budget) gemaximaliseerd is.
Formulering:
Gegeven:
n objecten, met voor ieder object i ∈ {1,...,n}:
-een positief nut (geluk) ui
-een positief gewicht (kost) wi
-een positieve capaciteit van b eenheden
Doel:
Maximaliseer geluk binnen de beschikbare capaciteit
Formulering:
NP-hard:
Een probleem is NP-hard als het minstens even
moeilijk is als de moeilijkste problemen in NP.
Het 0-1 knapzakprobleem is (NP-compleet, en dus
ook) NP-hard, omdat het zoeken naar de optimale
oplossing (maximale waarde binnen een beperking)
niet efficiënt op te lossen is met een algoritme in
polynomiale tijd.
Dat betekent dat, zolang P ≠ NP, er geen snel
algoritme bestaat dat altijd de beste oplossing vindt.
Exact oplossing van het 0-1 knapzak probleem:
→ Branch & Bound: time complexity = 2n
→ Dynamische programmering: time complexity = nb
! worst case rekentijd voor beide methoden: exponentieel in grootte van input
,
1.2: Afrondingsheuristiek gebaseerd op de LP relaxation:
LP relaxatie: Wat als objecten opdeelbaar zijn?:
= Wat als je delen van objecten (met het bijbehorende deel van het geluk) in de
knapzak kan meenemen door enkel dat deel van de kost te betalen?
=> Het is dus niet meer “all or nothing” per object.
=> De binaire beperking in de formulering wordt aangepast:
=> Dit geeft een LP relaxatie, wat de oplossingsverzameling groter kan maken.
=> Efficiënt oplosbaar: sorteer items van groot naar klein volgens ratio ui/wi.
=> Vul de knapzak in deze volgorde tot hij vol zit.i
=> Oplossing LP relaxatie:
=> alle BV = gehele getallen? Gelijk aan het originele optimum.
=> Minstens 1 BV = fractioneel? Bovengrens voor het originele optimum.
=> Feasible oplossing krijgen via bv. afrondingsheuristiek:
-items met x = 1 behouden
-items met x = 0 negeren
-items met 0 < x < 1 afronden naar beneden obv.
hun waarde en het resterende beschikbare gewicht
Voorbeeld LP-relaxatie:
Formulering: Tabel met ratio en oplossing:
=> Oplossing LP-relaxatie: X(LPR) = (3/4 ; 0 ; 1 ; 1 ; 1 ; 1), met Z(LPR) = 15
=> Afrondingsheuristiek: rond de waarde voor x1 af naar beneden
Oplossing: X(AFR) = (0 ; 0 ; 1 ; 1 ; 1 ; 1), met Z(AFR) = 12
⇔ Optimale oplossing: X(OPT) = (1 ; 0 ; 1 ; 1 ; 0 ; 1), met Z(OPT) = 14
Prestatie van heuristiek evalueren?
-Ofwel obv. vergelijking met andere heuristieken
-Ofwel door de DFW van de gevonden oplossing te vergelijken met een duale grens!
1.3: Relaxatie en duale grenzen:
Wat is een duale grens?:
Veel optimalisatiealgoritmes berekenen boven- en ondergrenzen op de optimale
waarde totdat deze grenzen voldoende convergeren.
Voor een maximalisatieprobleem:
=> ondergrens = primale grens, > toelaatbare (feasible) oplossing
=> bovengrens = duale grens, > oplossen van relaxatie
Voor een minimalisatieprobleem:
=> bovengrens = primale grens, > toelaatbare (feasible) oplossing
=> ondergrens = duale grens, > oplossen van relaxatie
,Relaxaties:
Visualisatie:
=> P geeft het originele probleem weer, R de relaxatie. Het
optimum van R ligt boven dat van P, want het is een maximalisatie.
=> Ideaal liggen g en f dicht bij elkaar, want dan: sterke grens!
=> MAAR trade-off tussen rekentijd en kwaliteit van grens!
2 voorwaarden:
1: De oplossingsruimte van de relaxatie is minstens
even groot: Alle oplossingen die bij het originele
probleem toelaatbaar zijn, zijn nog steeds toelaatbaar.
2: (Bij maximalisatie:) Iedere toelaatbare oplossing van
het originele probleem geeft bij de relaxatie een DFW
die minstens even groot is.
3 manieren om te relaxeren:
1) Maak een beperking “zwakker” door het RL aan te passen
2) Verwijder een beperking, maar integreer hem in de doelfunctie
3) Vervang de binaire beperking door “0 <= xi <= 1”
Voorbeeld
Relaxatie geeft steeds een duale grens:
!!! g(xᵖ) is niet per se gelijk aan zʳ:
xᵖ ligt ook in Y (want X ⊆ Y), dus je
mag xᵖ ook invullen in g(x). MAAR
misschien is er binnen Y een nog
betere oplossing voor g(x).
Relaxatie geeft soms ook bewijs van optimaliteit:
zie “waarom?” slide 20, idk
, 1.4: Prestatiegarantie van heuristieken:
Tekening en informatie uit de les:
Worst-case analyse: Wat is het verste dat we
(procentueel) kunnen afzitten van de ideale
oplossing bij het uitvoeren van het algoritme?
-Voor 1 probleem, meerdere algoritmes mogelijk
-Complexiteit van je probleem is niet per se gelijk
aan de complexiteit van je bijhorende algoritmen
--> bv het knapzak probleem is NP hard,
afrondingsheuristiek is O(n log n), B&B is 2^n,...
Prestatie van de afrondingsheuristiek:
De afrondingsheuristiek kan willekeurig slecht presteren. (zie voorbeeld dia 24)
= oneindige prestatiegarantie
=> Als je dus echt pech hebt, kan je er oneindig ver af zitten.
=> Gegeven een capaciteit k, kan de verhouding tussen het geheeltallige
optimum en en het optimum van de relaxatie onbegrensd groot worden:
Prestatie van de alternatieve heuristiek:
= greedy heuristiek, net zoals de afrondingsheuristiek: zo’n heuristiek kiest
in iedere iteratie voor de actie die het meeste onmiddellijke winst oplevert
De alternatieve heuristiek kan OOK willekeurig slecht presteren. (zie voorbeeld dia 26)
= oneindige prestatiegarantie
Prestatie van de Greedy 2.0 heuristiek:
De Greedy 2.0 heuristiek heeft een
prestatiegarantie van factor 2:
Voor iedere instantie van het
probleem is de optimale DFW
maximaal het dubbele van het nut
bekomen met de Greedy 2.0
heuristiek.
zie ook oefening dia 33
