Samenvatting Optimalisatietechnieken

Samenvatting Optimalisatietechnieken Dumon Willem - Van Haute Tom 2009 - 2010

1

Terminologie • Feasible = ‘oplosbaar’, voldoen a alle harde beperkingen • Harde beperking = beperking wr e oplossing aan moet voldoen • Zachte beperking = beperking wr bij voorkeur a voldaan is (nt abs noodz om feasible opl te bekomen) • Evaluatiefunctie = doelftie = objectiefftie = kostftie : kwaliteit v/d opl hangt oa af v/d mate wrin a/d z8e beperkingen voldaan is P vb: waarde evaluatieftie = overtredingen z8e beperkingen • Deterministisch zoeken = zoekmethode (algoritme) die altijd opl vindt vr e probl ⇔ algoritmes die nt altijd zelfde opl vinden als zelfde randvwn • Optimalisatie = proces dat beste opl probeert te vinden uit alle beschikbre opln , daarvr moet probl gemodelleerd worden in termen v/e evaluatiefftie die kwaliteit v/d opl bep. Soms optim = vinden beste oplossing (als gn te grote zoekruimte) • Lokaal optimum = opl wrvoor alle ‘buuropln slechter zijn Globaal optimum = allerbeste oplossing • Exhaustief zoeken = alle mogelijke opln zoeken & beste selecteren (snel moeilijk als grote zoekruimte) • Complexiteit = moeilijkheidsgraad v/e optim-probl (vaak tijdscomplexiteit) → ‘big O’ notatie: g(x) is orde v f (x); notatie g(x) = O(f(x)) wnnr vr e cte waarde K g(x) ≤ Kf(x) voor alle waarden v x > K • Heuristiek = methode om kwaliteitsvolle opln te bekomen als exhaustief zoeken nt mog, dus zonder alle opln te doorlopen – Constructieve heuristieken: om e initi¨ele opl te construeren v/h begin – Lokale zoekmethoden: ‘buren’ beschouwd als potenti¨eele vervangers v/d huidige oplossing. Nieuwe oplossing uit die buurt aanvaarden = ‘move’ v/d huidige nr nieuwe → buren v die nieuwe oplossing bekijken – Hill climbing: 1voudigst mr vlugst vast in lokaal opt, huidige opl → 1 of alle opl i/d buurt, beste kiezen → er naartoe gn als evaluatieftie beter is, stoppen als gn betere i/d buurt – Metaheuristieken: F. Glover → strategie die andere heuristieken leidt & aanpast om betere oplossingen te genereren dan deze die met lokale zoektechnieken te bereiken zijn I. Osman → iteratief proces dat e onderliggende heuristiek leidt – Evolutiemethoden: vb genetische alges , onderdeel v metaheuristieken, onderhouden populatie v kandidaatopln die wedijveren om te overleven – Hyperheuristieken: heuristieken die heuristieken zoeken i/e zoekruimte v heuristieken

1

2

Klassieke Technieken

Wiskige techniekn vr oplossing v praktische problemen, ontstaan jaren ’50, oa dr WO2, toenemende industri¨ele wedloop & vooruitzicht op toegankelijke computerkr8 i/d toekomst, verder ge¨evolueerd, ng altijd gebruikt om (relatief 1voudige) problemen o/t lossen of als bouwblok in mr complexe algoritmen

2.1

Lineair Programmeren

‘Lineair programmeren’ probleem = wrrin doelfunctie (te optimaliseren uitdrukking) & beperkingen vr te stellen zijn i/d vorm v lineaire uitdrukkingen v/d beslissingsvariabelen • wnnr e probleem n variabelen heeft, defini¨eren de beperkingen e verzameling hypervlakken i/d n-dimensionale ruimte, deze vormen de grenzen v/h n-dimensionale gebied dat de verzameling ‘feasible’ oplossingen definieert • wiskundige formulering: doelftie & beperkingen opstellen, alle uitdrukkingen lineair • feasible gebied = convex: geen rechtlijnig pad tss 2 punten i/d ruimte mogelijk dat het pad buiten de ruimte gaat • wnnr variabelen ≥0, optimale opl o/e extreem punt v/d opln -ruimte • mogelijk om geometrisch o/t lossen als 2 variabelen: grafisch: – elke ongelijkheid definieert e half vlak wrin elke oplossing vr het lineaire programma zich moet bevinden – convexe omhulsel dat dr de constraints gevormd wordt = simplex – doelfunctie bekijken als lijn met gekende helling die verschoven wordt v oneindig tt ze de simplex raakt (altijd op een hoekpunt, evt e lijn) – als niet-lineaire functies bij betrokken zijn → moeilijker, wnnr ongelijkheden ook nietlinair zijn kunnen er complexe geometrische vormen ontstaan – ‘infeasible’ wnnr e probleem nt oplosbaar is (bv. als de halve vlakken gn overlapping hebben) – ‘redundantie’ wnnr de simplex al volledig i/h vlak ligt dat dr e nieuwe beperking bepaald wordt – ‘onbegrensd’ wnnr de simplex open is, toch mogelijke oplossing vr sommige doelfties mr heel moeilijk vr algoritmen om vrbij onbegrensd gebied te geraken – nt eenvoudig om dergelijke problemen vast te stellen als vl variabelen & ongelijkheden • Conversie naar algemene vorm: 1. maximalisatieprobl → minimalisatieprobl: teken v co¨eff veranderen 2. negatieve variabelen uitdrukken als verschil v 2 positieve 3. alle beperkingen (≥, ≤) als gelijkheden door α toe te voegen (x1 + x2 ≤ 3 → x1 + x2 + α = 3), α = ‘slack’-variabele 4. rechterlid altijd pos → alles × -1 5. beslissingsvariabele altijd positief ⇒ x’ = -x1 = ‘slack’-variabele, opl in x’ zoeken • Gevoeligheidsanalyse: op welke manier be¨ınvloeden de LP parameters de optimale oplossing? ⇒ nt altijd LP trug oplossen – cf voorbeeld ivm Giapetto probleem – Schaduwprijs vr i-de beperking = hoeveelheid toe/afname wnnr rechterlid v/d i-de beperking met 1 toeneemt, geldt enkel als de verandering gn invloed hft o/d huidige basis (= snijpunt max-lijn met simplex) 2

– Duale formulering • Oplossingsmethoden: 1. Simplex methode: zoekt nr uiterste punten i/h ‘feasible’ gebied v/h primaire of duale probleem tt het optimum gevonden is, gebaseerd op matrixbewerkingen, 1voudig te implementeren ↔ slechte worst case rekentijd garantie 2. Interior Point methoden: zoeken e pad v opln dr interne v/h feasible gebied, zodanig dat, wnnr buitenkant bereikt, de gevonden oplossing = optimaal

2.2

Simplex Methode

• adhv matrixbewerkingen: pivoteren & methode v Gauss • alles gelijkheden behalve 1 die stelt dat alle variabelen ≥ 0 ⇒ ‘slack’-variabelen invoegen, als maar 1 variabele en negatief → vervangen door x’ = -x • N vgln , M variabelen & M > N ⇒ veel opl, optimale oplossing zoeken • triviale opl: als alles in rechterlid (RL) > 0 & alle slackvariabelen pos co¨eff <⇒ opl waarbij alles = 0 ∈ simplex (geldt in vele situaties) • alternatieve opl door pivoteren: – matrix (N+1)x(M+1), kolom M+1 = getallen v RL, 0de rij = co¨effn v/d doelftie met tegengesteld teken – variabelen die over1komen met e opl = basisvariabelen (= opl met in matrix op 1e rij 0), variabelen die op 0 gezet worden o/e opl te bekomen = niet-basisvarn – pivoteren: (zie vb in slides) 1. kies e element a[p,q] i/d matrix v/d co¨effici¨enten v/d vglen 2. vermenigvuldig de pde rij met een getal 3. tel het resultaat van 2) op bij alle andere rijen zodanig dat de qde kolom 0 wordt, op het element in rij q na, dat gelijkgesteld wordt aan 1 welke waarde nemen voor p & q: ∗ 0de rij toont met hoeveel doelftie zou toenemen als waarde v die variabele v 0 naar 1 zou gn ∗ kolom met negatief getal in rij 0 nemen → waarde v over1komstige variabele v 0 nr pos getal ⇒ doelftie ↑ ∗ pivoteren op rij met positief getal in die kolom ⇒ wrde doelftie ↑ +1] ⇒ waarde nemen waarvoor ratio van [M a[p,q] kleinst is ∗ probleem als gn pos getallen in q-de rij: neg wrde in 0de rij dus wel verhoging doelftie mr gn mogelijkheid → al1 als simplex onbegrensd ⇒ stoppen ∗ probleem als (M+1)e getal i/d rij met pos getal in kolom q = 0, rij wordt gekozen maar doelftie verhoogd met 0. Enkel probl als 2e zulke rij ⇒ lus ∗ lussen minder wss maken dr ad random mogelijke pivots te kiezen ∗ lussen vermijden: vaak versch neg getallen in rij 0: selectie: · grootste increment: selecteer kolom met kleinste waarde in 0de rij (= grootste in abs waarde). Nt altijd grootste toename i/d doelfunctie (afh v rij p), kolomselectie samen met rijselectie bij gelijke waardes (rij kiezen wrdr kolom met laagste index uit basis verwijdert wordt) ⇒ lussen nt mogelijk · steepest descent: doelftie vr elke kolom berekenen, grootste toename kiezen wnnr progr stopt bij q=M+1 → optimale opl in a[0][M+1] wnnr progr stopt bij p=N+1 → onbegrensde situatie

3

2.3

Dynamisch programmeren

• extreem ver doorgedreven recursie: om e groot probleem o/t lossen → opsplitsen in kleinere problemen die onafhankelijk v elkr opgelost kunnen worden • als nt precies weten welke kleinere problemen o/t lossen, allemaal berekenen & antwoorden bewaren vr later gebruik • ‘programmeren’ in de betekenis v ‘het proces v beperkingen formuleren zodanig dat de methode toepasbaar is’ • nt altijd mogelijk oplen vr kleinere problemen te combineren & tt e oplossing vr e groter probleem te komen • # o/t lossen kleine problemen kan onaanvaardbaar groot zijn • knapzak-probleem: zoek e combinatie v objecten die i/e ‘knapzak’ passen zodanig dat de waarde maximaal is – cost[i] = hoogste waarde die met knapzakcapaciteit i verkregen kan worden – best[i] is het laatst toegevoegde item om dat maximum te bekomen – tijd nodig vr oplossen knapzakprobleem met dyn. progr. ∼ NxM (N: soorten objecten, M: grootte knapzak) ⇒ probl 1voudig o/t lossen als M nt groot – als M, groottes of waarden v/d objecten re¨ele getallen ipv gehele werkt het niet (fundamenteel probleem) – voordeel: vroeger opgeloste deelproblemen moeten nt opnieuw bekeken worden – dynamisch programmeren vindt optimale oplossing • Matrix Chain Product: – klassieke toepassing: minimaliseren v/d hoeveelheid rekenwerk nodig om reeks matrices v verschillende grootte te vermenigvuldigen – 1e eigensch: de volgorde wrin matrices vermenigvuldigd worden bepaalt # bewerkingen – # mogelijkheden om N matrices te vermenigvuldigen = Catalaans getal ≈

4N −1 √ N πN

– opl met dyn. progr. is ‘bottom-up’: er is maar 1 manier om M1 te vermenigvuldigen met M2 & 1 manier om M2 met M3 te vermenigvuldigen; die kosten worden bewaard – algoritme: Stap 1: verdeel de sequentie v matrices in 2 subsequenties Stap 2: bereken de minimale kost om elke subsequentie uit te rekenen ⇒ subsequentie weer opsplitsen tt je enkel 2 matrices per subseq. over hebt (= maar 1 manier om deze te berekenen) Stap 3: tel deze kosten op, en tel de kost om de resultaten te vermenigvuldigen ook erbij Stap 4: herhaal dit voor elke mogelijke opsplitsing v/d originele matrixsequentie, en neem telkens de minimale kost ⇒ veel redundante berekeningen (AB berekenen, later ng eens voor andere opsplitsing → onthouden ⇒ top-down ipv bottom up, complexiteit v N3 nr N2 ) – manier om opeenvolgende triples te vermenigvuldigen w ook berekend adhv wat al berekend is – 2e eig: dyn. progr lost ‘matrix chain product’-probleem op in tijd evenredig met N3 en met geheugen evenredig met N2 .

4

• Optimale Binaire Zoekbomen: nr sommige sleutels wordt vl vaker gezocht, best vaakst gezochte bovenaan in zoekboom plaatsen, aan elke knoop v/d binaire boom kennen we e integer toe, ∼ zoekfrequentie – kost v/d boom berekenen dr frequentie v elke knoop te vermenigvuldigen met afstand tt de wortel & alles optellen (gewogen interne padlengte) – verschil met Huffman codering: wel belangrijk om volgorde te respecteren (alle knopen links v/d wortel kleiner) – algoritme: Stap 1: bereken de kost van elke mogelijkheid (n-1 sub-bomen) om 2 knopen in een boom (met die 2 elementen) te stoppen Stap 2: bewaar telkens de kleinste van de 2 en sla deze op, alsook welke v/d 2 de root is Stap 3: gebruik deze om de minimale kost om sub-bomen met 3 knopen te berekenen Stap 4: herhaal dit proces tot de kost & de root voor de optimale boom met n elementen is berekend – 3e eig: dyn. progr. methode om e optimale binaire boom te vinden gebeurt in tijd evenredig met N3 (N2 sub-boom kosten, n operaties om deze te bekomen) & gebruikt ruimte evenredig met N2 • Representatie: nt altijd 1voudig, bepaal toestanden & fasen, probleem afbeeldbaar op klassiek probleem (routering, knapzak,...)?, methode moet vl effici¨”enter zijn dan e opsomming v alle mogelijke oplossingen; de eerste toestand moet triviaal zijn & er moet e 1voudige recursieve methode bestaan om van een fase naar een andere te gaan • Performantie: kan vl tijd & geheugenruimte in beslag nemen & probeer # te evalueren toestanden te minimaliseren

2.4

Zoekstrategi¨ en

• voltooiing (garandeert strategie e opl te vinden als er 1 is?), tijdcomplexiteit (benadering v/d relatieve uitvoeringstijd v/h algoritme), geheugencomplexiteit (benadering v/h geheugengebruik), optimaal (vindt strategie beste oplossing als versch oplen ?) • terminologie: d = diepte 1e oplossing, b = ‘branching factor’ = gemiddeld # afstammelingen v/e oplossing 2.4.1

Breedte eerst

1. vorm e w8rij met wortelknooppunt 2. zolang w8rij nt leeg & doel nt bereikt → controleer of 1e knooppt uit w8rij gelijk aan doel • zoja: doe niets • zonee: verwijder 1e knooppt uit w8rij & voeg alle kinderen ervan toe 8raan de w8rij 3. doel gevonden → melden, anders falen v algoritme melden leidt nr minst diepe oplossing, nt altijd optimale → uniforme kost zoeken, altijd beste knoop 1st expanderen (met laagste kost) & breedte 1st = speciaal geval wrin kost = diepte v/d knoop 2.4.2

Diepte eerst

1. vorm w8rij met initieel enkel het wortelknooppunt (= root) 2. zolang wachtrij nt leeg en doel nt bereikt → ga na of 1e knooppunt in w8rij = doel • zoja: doe niets • zonee: verwijder dat knooppt uit w8rij & voeg kinderen ervan toe voorraan 5

3. doel gevonden → melden, anders falen v algoritme melden Zoeken met beperkte diepte → vermijden te lange rekentijd dr heel diepe subtak te doorzoeken Iteratief zoeken = zoekdiepte initieel 1 → herhalen: diepte 1st met gegeven diepte & diepte verhogen → tt opl gevonden of zoekdiepte > langste pad 2.4.3

Bidirectioneel zoeken

bep vwen : minstens 1 gekende eindtoestand & stappen om tt e opl te komen zn omkeerbr 1. start vanaf beginpunt met breedte eerst 2. start vanaf eindpunt met diepte eerst 3. ga door tot paden elkaar ontmoeten

2.5

Branch & Bound

eindige verz mogelijke oplen : alle oplen opnoemen & beste selecteren, behalve vr kleinste versies snel te rekenintensief, reduceert # oplen dr probleem voortdurend in deelproblemen o/t splitsen & op basis v lokale kennis de oplen die suboptimaal zijn te elimineren • 1voudige implementatie = constructief: opl opbouwen met 1 element per stap: veronderstel probleem wrvan oplen bestaan uit eindige vectoren van de vorm (x1 ,x2 ,...,xk ), k variabel v opl tt opl → verzameling v alle mogelijke oplen kan bekomen worden dr elke feasible waarde vr x1 te nemen, daarna vr elke x1 iedere compatibele x2 beschouwen, wrna vr elke parti¨le opl (x1 , x2 ,...) alle compatibele x3 bestuderen, enz. • volledige zoekboom doorzoeken nt geschikt vr grotere problemen → takken die zkr nt nr optim opl kunnen leiden worden gesnoeid dmv onder- & bovengrens: – bovengrens UB: opl moet minstens zo goed zijn (kost moet minstens kleiner zijn dan UB) – ondergrens i/e parti¨ele knoop i LBi = meest optimistische schatting v/d waarde die kan bereikt worden dr in knoop i verder te zoeken – knopen wrvoor LBi ≥ UB nt verder onderzoeken (beste vr subtak > UB = max kost) – wnnr gn enkele knoop nog verder onderzocht moet worden: UB = optim opl • onderschatting: L1 = kost v huidig pad, L2 = goedkoopste volgende stap, L3 = goedkoopste pad naar einde (F) v gelijk waar ⇒ LB = L1 +L2 +L3 , behalve als huidig punt nr F leidt LB = L1 +max(L2 ,L3 ) → meer afsnijden rightarrow vlugger tt oplossing • betere grenzen & vertakking: pad met kleinste kost eerst onderzoeken → ng meer afsnijden → ng vlugger • effici¨entere manieren om kortste pad te zoeken adhv dyn progr ism branch& bound 2.5.1

Grafen kleuren - voorbeeld!

• minimaliseer # kleuren nodig om knopen v/e graaf te kleuren zodanig dat buren nt zelfde kleur • grafen = interessant model vr timetabling- & schedulingproblen • algoritme v Brown, gebaseerd op branch & bound met eenvoudige grenzen: 1. definieer volgordes: knopen 1, 2, ... n, kleuren c1 , c2 , ... Γ− (i) = de buren v knoop i die aan i voorafgaan 2. zoek e initi¨ele kleuring in volgorde v/d laagst ge¨ındiceerde kleur 1st

6

3. bewaar de nieuwe oplossing, q = # gebruikte kleuren = bovengrens, bewaar huidige kleuring. identificatielijst J = lijst v backtrack knopen = knopen die je wil veranderen 4. Backtrack: (a) Zoek 1e knoop i∗ die overeenkomt met kleur van bovengrens = kleur q (b) Pas J en Γ− (i∗ ) aan verwijder alle j < i∗ uit J, stel J = J ∪ {i∗ } & wachtrij = ∪j∈J Γ− (j) (c) backtrack tt o/h niveau v/d 1e knoop i/d w8rij = i’ met kleur q’ als i’ = k en knopen 1, 2, ... k hebben kleuren c1 , c2 , ... ck ⇒ optimale oplossing, anders verwijder kleuren v alle i ≥ i’ 5. Branch (a) kleur i’ opnieuw i/d 1st toegelaten kleur (kleur 1,2 ... q-1), indien nt mog → i∗ = i & terug naar stap 3.2 (b) kleur overblijvende knopen (i’+1...n) met kleuren 1...q-1 dr 1st toegelaten kleur te gebruiken. Als knoop i kleur q nodig heeft, i∗ = i & terug naar stap 3.2, anders naar stap 2 ondergrenzen worden nt expliciet bijgehouden & 1e knoop met lokale ondergrens q = plaats wr kleur q vr 1st gebruikt

3

Lokaal Zoeken

lokaal zoeken wordt gebruikt om problemen o/t lossen wrvoor exacte algoritmen (1e deel) te traag werken (te groot # alternatieven te bestuderen). voordeel: i/e aanvaardbare rekentijd toch e oplossing ↔ nadeel: gn garantie dat oplossing optimaal • zoekruimte = verz v alle mogelijke oplossingen v/h probleem • ‘neighbourhood’ v/e oplossing = deelverz v/d zoekruimte met oplossingen bekomen dr 1voudige bewerkingen uit te voeren o/d huidige opl

3.1

Steepest descent

minimalisatieprobleem: steepest descent ↔ maximalisatieprobleem: hill climbing Oplossen van combinatorische of nt-lineaire problemen (nt-lineaire heel moeilijk op te lossen) • Kleine dimensies: – herstarten lokale optimalisatie vanuit 6= initi¨ele punten – deterministische globale optimalisatietechnieken • Grote dimensies: helemaal moeilijk (ook vr lineaire problemen) Werkwijze: 1. Kies een initi¨ele opl s in X stop := false HERHAAL: 2. Genereer een verz V∗ oplen in N(s) Selecteer de beste s’ in V∗ (zodanig dat f (s0 ) ≤ f (¯ s) voor elke s¯ in V∗ ) 0 if f (s ) ≥ f (¯ s) then stop:=true; else s := s’ tot STOP In tegenstelling tot alg vebetertechn w ¯ hier beste oplossing telkens uit V∗ gekozen 7

3. Neem volledige omgeving van s: V∗ = N(s) 4. Indien volledige omgeving te groot (tijdrovend) → deelverz V∗ ⊂ N(s) met |V ∗ |  |N (s)| 5. Extreem geval: |V ∗ | = 1 (elimineert vgl tss elementen; gebruikt in simulated annealing) 6. Afwegen v kwaliteit v/d opl en inspanning om een grotere omgeving te doorzoeken Zie voorbeeld personeelsplanning!

3.2

Metaheuristieken

• Moeilijke optimalisatieproblemen → zoektocht nr effici¨ente opl-methoden • Inspiratie gezocht in natuur; andere wetenschappen: materiaalkunde, biologie,... ⇒ Tabu search, Simulated annealing, Genetische algoritmen, Mierenalgoritmen, Scatter search, variabele neighbourhood search, GRASP, memetic algorithms,...

3.3

Tabu search

• Uitbreiding v ‘Zoeken in een omgeving’, zoeken in Al context • Eenvoudige implementatie - eenvoudig uit te breiden met nieuwe bepen , doelftie • Alg heuristsiche procedure • Goed afgestemde implementaties generen opl die soms nog nt ge¨evenaard zijn met andere technieken • Voorkomt vastlopen in lokaal optimum (⇔ hill climbing, steepest descent) • Probleem: eens in lokaal optimum zal elke stap in omgeving een slechtere waarde van de doelftie veroorzaken • Flexibel (adaptief) geheugen • Iteratieve techn die een verz opl voor een probleem (X) doorzoekt, door herhaaldelijk zetten (moves) uit te voeren van een opl s naar een opl s’ in de omgeving (neighbourhood) N(s) van s • De bedoeling met zetten op een effici¨ente manier tot een opl te komen die ‘goed’ is(in termen van een te max/mineren doelftie f(s)) • |V ∗ | ≥ 1 • Opl van een lokaal optimalisatieprobl om een s’ te vinden die overeenkomt met: min{f (s0 )|s0 ∈ V ∗ ⊆ N (s)} • lokale optimalisatie uitvoeren op een strategische manier (systematisch werken met het geheugen om ook kennis buiten de ftie f(s) en N(s) te gebruiken) • zonder sturing → beste geval tot lokaal optimum, waar het stopt • algoritme sturen → zet van s nr s’ (in V∗ ) kan uitvoeren, zelf als f(s’) f(s) • Probleem: gevaar om in lus terecht te komen (soms na interval v tussenliggende opl, omgeving is vaak al voldoende veranderd → weinig gevaar voor lussen) • Gebruikt geheugenstructuur → verbiedt zetten die leiden naar recent bezochte opl • De ‘omgeving’ afh v/d tijd (iteratie): beter N(s,k) dan N(s), k = iteratienummer • Opl v/d lokale optimalisatie w ¯ bewaard zodat ze niet verloren raakt 8

Werkwijze tabu search met aangepaste omgeving: 1. Kies een initi¨ele opl s in X s∗ := s en k:= 1 2. While stopvw niet bereikt do (a) k := k+1 (b) Genereer V ∗ ⊆ N (s, k) (c) Kies beste s’ in V∗ (d) s := s∗ (e) if f(s’) < f(s) then s∗ := s’ 3. end while Stopcondities: procedure stopt nt, ook als globaal optimum gevonden is → stopcriterium nodig! Mogelijke stopcondities: • optimale opl gevonden • N(s, k+1) =  (soms beter om toch een random zet uit te voeren) • k > max toegelaten # iteraties • # iteraties uitgevoerd sinds laatste verbetering > toegelaten # Geheugenstructuur: • gebaseerd op ‘recente’ opl tabulijst T die de |T | meest recent bezochte opl opslaat • voortdurend w ¯ lijst v/d laatste stappen aangepast, er w ¯ gecontroleerd of de volgende stap in die lijst staat (tabu is) • meer praktisch: N(s) defini¨eren in termen van zetten waarmee de opl s in andere toep k¯ omgezet w ¯ • voor elke s: verz M(s) van ‘legale’ zetten m die op s k¯ toegepast w ¯ om nieuwe opl s’ = s ⊕ m te bekomen dan wordt N (s) = {s0 |∃m ∈ M (s) met s’ = s ⊕ m} • Best een verz zetten gebruiken die omkeerbaar is: ∀m ∈ M (s), ∃m−1 ∃M (M (s)) zodanig dat (s ⊕ m) ⊕ m−1 = s • in dit geval kan T bestaan uit de laaste |T | omgekeerde zetten van de zetten die uitgevoerd zijn Aspiratiecriteria: • Wnnr de tabu-vw gebaseerd zijn op geselecteerde attributen va nzetten, is het mogelijk dat ook zetten naar nog nt eerder bezochte opl tabu zijn • Veronderstel een tabu-zet m die leidt naar een opl die beter is dan de beste tot nu toe gevonden → best om tabu status te negeren, en zet accepteren Tabu search algoritme: 1. Gegeven: opl x∗ met f(x∗ ) = z∗ 2. Start: stel x = x∗ met f(x) = z∗ 3. Iteratie: zolang niet voldaan is aan het stopcriterium:

9

(a) selecteer beste zet van x naar x’ met waarde f(x’) • Indien toegelaten: niet tabu • Inien een tabu zet x’ beter is dan z∗ , negeer de tabu-vw (b) onderhoud de tabulijst, bereken de zetten die tabu moeten zijn (c) voer de zet uit: x=x’, f(x)=f(x’) (d) als f(x) > z∗ dan z∗ = f(x), x∗ = x 4. Resultaat: x∗ is de beste gevonden opl met waarde v/d doelftie z∗ Zie terug voorbeeld personeelsplanning! • Intensificatie – Observeren of goede opl gemeenschappelijke kenmerken hebben – Intensificatie: op sommige momenten omgeving beperken tot oplen die goede kenmerken vertonen – Combinatie met ‘beam seading’ op een interessant punt • Diversificatie – Tegengewicht vr intensificiatie: zoeken nr oplen met vari¨erende kenmerken – Vb. overgaan naar oplen die ‘sterk’ verschillen van voorgaande oplen (en nt met eenvoudige zetten te bereiken) Tabu search alterneert best tussen intensificatie (veelbelovend gebied v/d oplossingsruimte) en diversificatie (om ook andere gebieden te bereiken) Verfijningen: • Variabele tabu lijstlengte: vb zolang verbetering → lengte laten afnemen, zolang gn verbetering → lengte laten toenemen • Variabele neighbourhood search • 6= (random) initi¨ ele oplen • Shifting penalty: vari¨eren v/d doelftie (overtredingen anders aanrekenen) om weg te geraken uit lokale optima • Strategic oscillation: afwisslend in feasable en in infeasable gebied zoeken

3.4

Simulated Annealing (Dr. Graham Kendall)

• Drempel algoritme • Gebaseerd op proces v koelen en kristallisatie: wnnr gesmolte materiaal gekoeld w ¯ → bewegingsvrijheid moleculen ↓. Structuur v resulterende vaste stof afh v snelh temp ↓. Snel koelen → vele kiemen in vaste stof, traag koelen (uitgloeien = ‘annealing’) → zo zuiver mogelijk kristal, minimum aan inwendige spanningen • Opeenvolgende oplen v/e combinatorisch optimalisatieprobl voorstellen op basis v/d overeenkomsten met een fysisch systeem met 6= deeltjes: – Oplen v/h optimalisatieprobl zijn equivalent aan toestanden v/h fysisch systeem – De kost v/e opl is equivalent aan de inwendige energie v/e toestand (= fitness, kwaliteit) • De temperatuur vormt een controleparamter • In simulated annealing neemt de wss-heid wrmee slechtere opln aanvaard w ¯ af met T& 10

• behoort tot de klasse van ‘drempel’ (threshold) algoritmen in local search • vrij succesvol voor breed spectrum v praktische problen • bevat stochastische component1 , die een theoretische analyse v/h asymptotische gedrag mogelijk maakt • slaagt erin te ‘ontsnappen’ uit het lokale optima • ‘stuurt’ door af en toe een opl s, een niet-verbeterende zet s’ uit te voeren, met een wssheid die afhangt van f(s), f(s’) en een parameter die afhangt van de T • (virtueel) alle zetten in een omgeving evalueren • aan beste zet de hoogste wssheid voor selectie toekennen, 2e beste → 2e 2 hoogste wssheid • wssheden nemen exponentieel af overeenkomstig de grootte v/d verbetering   −(Ej − Ei ) • pj ∼ exp kT – pj → wssheid om de zt van i nr j uit te voeren – Ei → waarde v/d doelftie voor toestand i (energieniveau) – Ej → waarde v/d doelftie voor toestand j (Ei ´en Ej ≥ 0) – k → normalisatiefactor (Boltzmann cte ) – T → controlefactor (temperatuur) Simulated Annealing algoritme: 1. Genereer initi¨ele oplossing s 2. s∗ = s (beste oplossing) 3. bepaal starttemperatuur T 4. while niet bevroren (a) while geen evenwicht voor T genereer random opl s’ i/d omgeving van s if f(s’) ≤ f(s) then s = s’ if f(s) < f(s∗ ) then s∗ = s else genereer random getal r uit [0,1] (uniform) if r < exp(-(f(s’)-f(s))/kT) then s = s’ (b) verlaag T return s∗ Parameters bepalen: (bij voorkeur door experimenteren) • Starttemperatuur: moet hoog genoeg zijn om elke opl i/d zoekruimte te kunnen bereiken 1 Stochastische variabele (of toevalsgrootheid of toevalsvariabele) is een begrip uit de kansrekening. In veel kansexperimenten, zoals steekproeftrekkingen, wordt uit een populatie door toeval een element, b.v. een willekeurige voorbijganger, aangewezen. We vragen deze voorbijganger naar zijn leeftijd, inkomen, e.d. Vooraf weten we niet wat we als antwoord zullen krijgen, achteraf wel, maar bij herhaling treffen we vermoedelijk een andere voorbijganger, met zeer waarschijnlijk andere antwoorden. Om in de theorie over ‘de leeftijd van een willekeurige voorbijganger’ te kunnen spreken is het begrip ‘stochastische variabele’ ingevoerd. Het toeval wijst een uitkomst aan - een of andere voorbijganger - en aan deze uitkomst wijzen we een getal toe - z’n leeftijd.

11

• Eindtemperatuur: toestand moet ‘bevroren’ zijn • Temperatuurafname: – Evenwicht bij elke temp ⇒ veel iteraties nodig – Compromis: temp-afname in stappen vb: ∗ Lineair ∗ Volgens T = αT met α < 1 – # iteraties op elke temp • Typisch starten met hoge T om heel intensief te zoeken (max verbetering), daarna geleidelijk T verlagen als zoeken moeilijker wordt (meer diversicatie) • Temperatuur dynamisch vari¨eren Verschil tss SA (Simulated Annealing) en TS (Tabu Search) • SA diversifieert door randomisatie • TS door nieuwe zetten te verplichten Praktijk: • Hoe temperatuur normaliseren? • Hoe temperatuur dynamisch aanpassen? ∞ traag koelen → optimale oplossing!

4

Multicriteria Optimalisatie • meeste re¨ele optimalisatieproblen w ¯ voorgesteld als nt-lineaire problen met 6= objectieven • w ¯ vaak geconverteerd naar enkelvoudige optimalisatietechnieken • probleem: fundamenteel verschil tss enkelvoudige en multicriteria optimalisatietechnieken • multicriteria oplossing → nt een optimale oplossing voor elk v/d criteria

4.1

Enkelvoudige ↔ Multicriteria optimalisatie

• meestal een verz v gelijkwaardige optimale oplen in plaats v/e enkelvoudige opl • 6= optimalisatiedoelen • verz vormt een front en wordt het Pareto front genoemd Doelstelling: • convergeren naar de Pareto optimale oplen • verz ‘maximaal verspreide’ oplen behouden 2 onafhankelijke doelstellingen → een optimalisatiealgoritme moet daarop inspelen • beslissingsvariabelen zelf vormen multidimensionale zoekruimte: S • criteria vormen samen een multidimensionale ruimte: criteria ruimte Z (verz met kwaliteit → waardes v oplen , max hier zoeken dan trug nr S om opl te vinden!)

12

• voor elke opl i/d verz beslissingsvariabelen → punt i/d criteria ruimte, voorgesteld: f (x) = z = (z1 , z2 , . . . , zm )T • er is een afbeelding v/e N-dimensionale opl-vector naar een M-dimensionale doelvector Criteria ruimte: • zoekproces v/e algoritme gebeurt i/d ruimte v/d beslissingsvariabelen • goede multicriteria algoritmen → info uit criteria ruimte gebruiken Kiezen uit gelijkwaardige oplossingen: • los v/d gekende criteria spelen soms andere belissingsmotieven een rol • vb v/d auto: hoeveel passagiers, welk verbruik, dagelijks af te leggen afstand, enz... • Werkwijze: Stap 1: zoek 6= gelijkwaardige optimale oplen i/e breed bereik v doelwaarden Stap 2: kies een opl uit die verz op basis v andere informatie (hogere orde) • Ideale mulicriteria procedure: (zie figuur 1)

Figuur 1: Ideale multicriteria procedure – hogere orde info plaatst de 6= criteria impliciet i/e bepaalde volgorde – indien volgorde gekend → eenvoudige manier voor optimaliseren – multicriteria → enkelvoudig criterium • Preferentie multicriteria procudure: (zie figuur 2)

13

Figuur 2: Preferentie multicriteria procedure – vormt samengesteld doel door gewogen som te nemen v/d 6= doelen (gewicht ⇔ voorkeur) – opl bekomen met dergelijke methode → subjectief – wijzigingen i/d preferentievolgorde zorgen (nrml gezien) voor een andere opl

4.2

Nt-gedomineerde oplen ↔ Pareto optimale oplen

Objectievere methodes: 4.2.1

Ideale doelvector

• voor elk v/d M conflicterende criteria bestaat er een andere optimale opl • ideale doelvector is geconstrueerd met die individuele optimale waarden • m-de component v/d ideale doelvector z∗ wordt bekomen door: ( Minimaliseer fm (x) s.t. x∈S • Ideale vector is dan: ∗ T z ∗ = f ∗ = (f1∗ , f2∗ , . . . , fM )

• komt meestal niet overeen met een bestaande opl – indien toch zou bestaan → de criteria conflicteren nt – al bestaat ideale opl nt → kwaliteit opl bepaald dr afstand tot ideale opl (kennis ondergrens wordt soms gebruikt voor normaliseren) 4.2.2

Utopische doelvector

• ideale doelvector → elke doelftie min 1 opl in feasable zoekruimte die dezelfde waarde heeft als overeenkomstig element i/d ideale opl • voor sommige algoritmen is een strikt betere doelwaarde nodig voor elke opl i/d zoekruimte • utopische doelvector z∗∗ is elk v/d componenten marginaal kleiner dan die v/d ideale doelvector: z ∗∗ = z ∗ − εi > 0 voor alle i = 1, 2, . . . , M • zowel ideale als utopische doelvector stellen een niet-bestaande opl voor

14

4.2.3

Nadir doelvector

• nadir doelvector znad stelt bovengrens voor van elk criterium i/d volledige Pareto optimale verz (en nt volledige zoekruimte) • ⇔ ideale doelvector die ondergrens van elk criterium voorstelt i/d volledige feasable zoekruimte • nt verwarren met een vector v objectieven die de slechtste feasable functiewaarden voorstelt fimax • kan bestaande of nt-bestaande opl voorstellen, afh v/d convexiteit en continu¨ıteit v/d Pareto optimale verz • kennis v/d nadir en ideale doelvectoren kan gebruikt worden om de criteria te normaliseren • Genormaliseerde doelvector: finorm =

fi − zi∗ nad zi − zi∗

Figuur 3: Verschillende vectors 4.2.4

Dominantie

• onderstel M criteria • operator
tss 2 oplen i en j : i
j = opl i is beter dan j voor bepaald criterium

• analoog: i  j = i is slechter dan j voor dat criterium

• operatoren laten toe mintie en maxtie criteria algemeen te behandelen • opl x1 domineert opl x2 als: – x1 niet slechter is dan x2 voor alle criteria: fj (x1 ) 7 fj (x2 ) voor alle j ∈ 1, 2, . . . , M – x1 beter is als x2 voor tenminste ´ e´ en criterium: fj 0 (x1 )
fj 0 (x2 ) voor ten minste ´e´en j 0 ∈ 1, 2, . . . , M Eigenschappen: • 3 mogelijke relaties tussen opl 1 en 2 1. opl 1 domineert opl 2 2. opl 2 domineert opl 1 3. de opl 1 en 2 zijn nt dominant t.o.v. elkaar • dominantie is: – nt reflextief: opl i kan zichzelf niet domineren 15

– nt symmetrisch: als i
j kan j opl i niet domineren – nt antisymmetrisch want niet symmetrisch – transitief: a
b & b
c ⇒ a
c

– als opl p opl q nt domineert betekent dat nt dat opl q opl p domineert • Niet gedomineerde verzameling – alle mogelijke paren opl bestuderen om na te gaan welk opl welke andere domineert, en welke opl nt gedomineerd zijn – vb → zie figuur: 3 en 5 zijn nt gedomineerd door een andere opl – i/e verz v oplen P, nt gedomineerde verz v oplen P’ = verz van oplen die nt gedomineerd zijn door een element v/d verz P • Pareto optimale verzameling – wanneer P = volledige zoekruimte (P=S) → nt gedomineerde verz = Pareto optimale verz – voor een zelfde zoekruimte hangt de Pareto optimale verz af v/d criteria (te minen of te maxen ) – bestaat altijd uit oplen die zich ad rand v/h feasible deel v/d zoekruimte bevinden – dominantieregels volstaan om met alle mogelijke soorten criteria om te gaan, vaak worden alle criteria omgevormd tot mintie criteria – Zoals bij enkelvoudig criterium → globale en lokale Pareto optimale verzen ∗ Globale Pareto Optimale Verzameling: nt gedomineerde verz v/d volledige feasible zoekruimte S ∗ Lokale Pareto Optimale Verzameling: wnnr voor elke x ∈ P er gn opl y bestaat (in de omgeving van x zodanig dat ||y − x||∞ ≤  met  een klein positief getal) die elk element v/d verz P domineert, → oplen v/d verz P behoren tot lokale Pareto optimale verzameling • Procedures: – Procedure 1: beste nt gedomineerde front zoeken Stap Stap Stap Stap

1: 2: 3: 4:

Initialiseer P’ = 1. Stel # opl i =2 Stel j =1 Controleer opl i en opl j uit P’ op dominantie Als i
j → verwijder het j de element uit P’ (P 0 = P 0 \{P 0(j) }), j ++ en ga naar Stap 3. Anders, ga naar Stap 5 Als j
i → i ++ en ga naar Stap 2 S Stap 5: Voeg i toe aan P’ (P 0 = P 0 i). Als i < N , incrementeer i met 1 en ga naar Stap 2. Anders, stop met P’ als de niet gedomineerde verz ∗ algoritme voert 1 + 2 + . . . + (N − 1) = N (N − 1)/2 dominantiecontroles uit ∗ in werkelijkheid → # berekeningen lager omdat meestal ook (gedomineerde) oplen uit P’ verdwijnen – Procedure 2: niet gedomineerde sorteerprocedure Stap 1: Voor elke i ∈ P, ni = 0, initialiseer Si = . ∀j 6= i en j ∈ P , voer Stap 2 uit en ga dan nr Stap 3 S Stap 2: Als i
j, aanpassen v Si = Si {j}. Anders als j
i, stel ni = ni + 1 Stap 3: Als ni = 0, behoud i i/h eerste nt gedomineerde front P1 (gelijk aan P 0 i/d vorige procedure) Stel front teller k = 1 Stap 4: Zolang Pk 6= , voer de volgende stappen uit 16

Stap 5: Initialiseer Q =  om de volgende nt gedomineerde oplen op te slaan. Voor elke i ∈ Pk en voor elke j ∈ Si : Stap 5a: Stel nj = nj − 1 S Stap 5b: Als nj = 0, behoud j in Q of stel Q = Q {j} Stap 6: Stel k = k + 1 en Pk = Q. Ga naar Stap 4 – dominantieteller ni : # oplen die opl i domineren – Si verz v oplen die door i gedomineerd worden – opl i wordt max N − 1 maal bezocht voor zijn dominantieteller 0 wordt

4.3 4.3.1

Oplossingsmethodes Klassieke methode: gewogen som

• eenvoudigste methode, vaakst toegepast • omzette v/e verz criteria i/e enkelvoudig criterium door elk criterium te vermenigvuldigen met gewicht (bep dr gebruiker) • probleem: welke gewichten? • Formule:   Minimaliseer: s.t.  

PM F (x) = m=1 wm fm (x) gj (s) ≥ 0 j = 1, 2, . . . , J hk (x) = 0 k = 1, 2, . . . , K

• wm (∈ [0,1] uniform) stelt het gewicht voor v/h m-de criterium PM • vaak kiest men de gewichten zodanig dat m=1 wm = 1 • door gewichten te vari¨eren → ander Pareto optimaal punt bekomen • Problemen: 1. Uniforme keuze gewichtsvectoren → nt noodzakelijk uniforme verz Pareto optimale oplen 2. procedure nt bruikbaar om Pareto optimale oplen te vinden die op nt-convexe deel v/h Pareto optimaal front liggen • figuur 4 links

Figuur 4: Oplossingmethodes: gewichten vs -constraint

17

4.3.2

-constraint methode

• bedoeling: problemen vermijden van gewogen som bij nt convexe zoekruimten • 1 v/d criteria behouden en andere beperken binnen ingestelde grenzen (gekozen door gebruiker) • Formule:  Minimaliseer:    s.t.    

fµ (x) fm (x) ≤ m gj (z) ≥ 0 hk (x) = 0

m = 1, 2, . . . , M en m 6= µ j = 1, 2, . . . , J k = 1, 2, . . . , K

• m stelt bovengrens voor v/d waarde fm • Probleem: 1. opl sterk afh v/d gekozen -vector 2. voor a1 (in fig 10 slides) → gn feasible opl, voor d1 zoekruimte volledig feasible • figuur 4 rechts 4.3.3

Evolutiemethode

Dit mag je eens lezen (voor de liefhebbers)

4.4

Voorbeeld

Voorbeeld ivm personeelsplanning → zie slides!

4.5

Conclusie

• Multicriteria benadering voor multicriteria probleem • Effici¨ent om beperkingen van 6= aard te modelleren • Gebruikers hebben controle over de compensaties v beperkingen • Uitdagingen: interactieve multicriteria optimalisatie, grote aantallen criteria, performantie metrieken, benchmarking,. . .

5

Geheeltallig programmeren (Integer programming)

= lineair programmeren + branch & bound

5.1

Inleiding

• Basis: lineair programmeren • Variabelen, beperkingen, functies • Beperkingen en doelfuncties moeten lineair zijn • Extra beperkingen: enkele (of alle) variabelen moeten geheeltallig zijn • Geheeltallige variabelen: voordeel: # aantal problemen dat kan gemodelleerd worden is veel groter, nadeel: veel moeilijker op te lossen dan zonder geheeltallige variabelen • Richtlijnen om problemen succesvol te modelleren & op te lossen: Formulering & Relaxatie Voorbeeld in slides: Lokaliseren van faciliteiten! 18

5.2

Lineaire Relaxatie

• Met geheeltallig programma (IP) komt lineair programma (LP) overeen: lineaire relaxatie (LR) • Gevormd door de geheeltallige beperkingen te laten vallen • Nieuw probleem = minder beperkt dan oorspronkelijke • Als IP een minimalisatieprobl is, dan optimale waarde vd doelftie v LR ≤ optimale waarde v IP • Als IP een maximalisatieprobl is,dan optimale waarde vd doelftie v LR ≥ optimale waarde v IP • Als LR = infeasible, dan IP ook • Als alle variabelen i/e optimale opling van LR = geheeltallig, dan die opling ook optimaal voor IP • Als coefen v/d doelftie gehele getallen zijn, dan: – vr mintie probl: optimale waarde v IP ≥ kleinste geheel getal > optimale waarde vr LR – vr maxtie probl: optimale waarde v IP ≤ grootst geheel getal < optimale waarde vr LR • Nut van LR ople, : levert grenzen vr de optimale waarde v IP, en levert (in beste geval) optimale opling vr IP (Zie terug voorbeeld!) → verder uitwerken met een intermediaire branch & bound boom! ,→ Stoppen met boom uitwerken als optimale gevonden is!! (Niet hele boom uitwerken!) • Nadelen: Branch & bound leidt niet altijd snel tot een opling , wnnr nergens bound mogelijk is → probl met n 0/1 variabelen → 2n probleem • Voordeel: IPs → veel meer toepassingsbereik dan LPs • Problemen op een creatieve manier formuleren → zo nadelen minder doorwegen

5.3

Creatieve Formulering

Bekijk zeker alle vb-en in de slides!!! 5.3.1

Geheeltallige hoeveelheden

Toegevoegde precisie v/e geheel getal niet altijd nodig! (Vb: tv toestellen, opling LP = 202.7 → niet de moeite voor B&B, gwn 202 of 203 nemen) Niet nodig om relaxatie toe te passen (wel voor kleine hoeveelheden!) 5.3.2

Binaire beslissingen

Kiezen uit projecten A, B, C, D om in te investeren (met gegeven kapitaal en opbrengst. Bij bep bedrag, welke projecten best investeren?) 5.3.3

Vaste kosten

In productieomgevingen nemen productiekosten evenredig toe met hoeveelh, behalve wnnr er niet geproduceerd wordt: • Niet uit te drukke met LP, wel mogelijk met extra 0/1 variabele y (1= productie, 0= gn productie) • x en y moeten aan elkaar gelinkt worden (anders is een mog resultaat: y = 0, x = 10) • variabelen linken dr bovengrens aan x te stellen: x ≤ M y, big M model 19

5.3.4

Logische beperkingen

Onmogelijk met LP: vb. binaire variabelen y1 , y2 , y3 , y4 , y5 die overeenkomen met beslissing om magazijn te openen op locatie 1, 2, 3, 4 & 5 5.3.5

Sequentieproblemen

Volgordes bepalen, planning: vb product i met bewerkingstijd pi op een machine die maar 1 product tgl kan bewerken

5.4

Formuleringen met sterke relaxatie

• 6= IP formuleringen mogelijke v/e probleem • goede formulering → bewezen optimale opling • best: formulering zoeken waarvan lineaire relaxatie ≈ overeenkomstig lineair probl • Zie voorbeeld raffinaderij • Niet eenvoudig om ‘snijvlakke’ te vinden → alg procedure: Gomory-Chvatal procedure Vb voor ≤ beperkingen met nt-negatieve variabelen: 1. Neem 1 of meedere beperkingen, x nt-negatieve constante (mag 6= zijn vr elke beperking), tel resulterende beperkingen op i/e enkelvoudige beperking 2. Rond elke coef i/h linkerlid v/d beperking af nr beneden 3. Rond rechterlid v/d beperking af nr beneden • Resultaat: beperking die gn enkele feasible 0/1 opling afsnijdt, nieuwe beperking kan snijvlak vormen als effect v/h rechterlid afronden > effect v/d afronding v/d coef. • Voorbeeld: zie slides! • De 3 stappen hebben een 6= effect: 1. Gn effect, voegt gn nieuwe feasible waarden toe en verwijderdt er gn 2. Verzwakking v/d beperking → mogelijk extra feasible breukwaarden 3. Versterking v/d beperking → ideaal tot de verwijding v alle breukwaarden • big M formuleringen meestal niet wenselijk • Lineaire relaxatie v dergelijke formuleringen → laat meestal 6= breukwaarden toe • vb: x1 + x2 + x3 ≤ 1000y (alle variabelen 0/1) • Bedoeling: uitdrukken dat x-en slechts 1 kunnen zijn als y dat ook is • Leidt tot heel slechte B&B-bomen • Beter: x1 + x2 + x3 ≤ 3y (maak de grote M zo klein mogelijk) • Nog beter: x1 ≤ y , x2 ≤ y , x3 ≤ y

20

5.5

Symmetrie vermijden

• Geheeltallig programmeren kan heel ineffici¨ent zijn vr modellen met veel symmetrie ( yj = 1, zj = 0, wj = 0 • Vb: raffinaderijen, per locatie 3 soorten yj , zj , wj : stel yj = 0, zj = 1, wj = 0 = hetzelfde, 1 soort gebouwd, voor B&B zijn er 6= oplen ! → gedraagd zich slecht door symmetrie • Vermijden door: beperkingen toevoegen, variabelen vastleggen, formulering aanpassen • Voor faciliteiten: probleem is eenvoudigst om beperkingen toe te voegen • yi ≥ zj ≥ wj voor alle j • zj kan nu pas 1 zijn als yj dat ook is, enz. → symmetrie gedeeltelijk doorbroken • Andere manier: variabelen herdefini¨eren: stel yj = # raffinaderijen op locatie j, verwijdert symmetrie maar de lineaire relaxatie is nt meer zo sterk als i/h geval met binaire variabelen • Variabelen vastleggen: voorbeeld grafen kleuren!! Zeker in slides bekijken

5.6

Formuleringen met veel beperkingen

• Betere formuleringen → verz beperkingen die te groot zijn vr i/d formulering op te nemen • vb. beperkingen met nt negatieve coef: a1 x1 + a2 x2 + a3 x3 + . . . P + an xn ≤ b met xi 0/1 variabelen, veronderstel een deelverz S v/d variabelen zodanig dat i∈S xi ≤ |S| − 1 vormt een geldig snijvlak, ze snijdt breukoplen af als S minimaal is: cover constraints • dergelijke beperkingen opnemen in formulering? • # kan heel groot zijn, niet aangewezen om mee te nemen in de formulering, enkel de beperkingen die nodig zijn! Voorbeeld slides!! • cover beperkingen niet altijd eenvoudig te zien • vb heuristiek: variabelen P ordenen volgens afnemende ai x∗i , dan toevoegen aan S tot i∈S ai > b deze heuristiek garandeerd niet dat optimale opling gevonden wordt maar ze zorgt wel voor een veel krachtiger formulering • Formaliseren: Branch & Cut methode – formulering heeft expliciete (Ax ≤ b) en impliciete (A0 x ≤ b0 ) beperkingen, maximaliseer doelftie cx, alle x zijn 0/1 variabelen – Algoritme: Stap 1 Los LP op: Max cx, s.t. Ax ≤ b op om de optimale relaxatie oplossing x∗ te bekomen Stap 2 Als x∗ geheeltallig is, stop, x∗ is optimaal Stap 3 Zoek beperking a0 x ≤ b0 uit impliciete beperkingen zodanig dat a0 x∗ > b0 . Gevonden? → toevoegen aan expliciete verz en naar Stap 1. Nt gevonden? → voer B&B uit op huidige formulering ⇒ wordt separation problem genoemd

21

5.7

Formuleringen met veel variabelen

• Variabelen toevoegen aan formulering → kan ook + effect hebben • Zeker goed bekijken in slides!! Vb Graph colouring • Extra variabelen generen: – Los formulering op met beperkt aantal variabelen – Los LR probleem op en bereken duale waarden π – Bepaal (mbv π) of er variabelen zijn die opling kunnen verbeteren door toe te voege aan formulering – Indien niet, LR opgelost. Indien wel, toevoegen aan formulering en herhaal – wnnr LR opgelost is en de opling = geheeltallig, ook = optimaal • Maximum weighed independent set (MWIS) maximum gewogen onafhankelijke verzameling probleem → moeilijk probl maar er bestaan methoden voor • Opletten bij de branch, mag gne ffect zijn o/h MWIS deelprobleem • wnnr vb op yi variabelen wordt vertakt (=0/1) , kan MWIS nt meer gebruikt worden • Als yi = 0, zoeken we verbeterde verz, maar Sj is nt verbeterend, dus moeten we 2e beste verz zoeken, enz.. • Variabelen genereren + geschikte branching regels + variabelen genereren vr de deelprob = branc & price

6

Complexiteit (Belangrijkste hoofdstuk!)

6.1

No free lunch

• Stelling: Geen enkel zoekalgoritme is beter dan een ander wanneer het gedrag beschouwd wordt voor alle mogelijke discrete fies . • Complexiteitstheorie: bestudeert de tijd en geheugencomplexiteit van algoritmen. • Enkel discrete functies beschouwen • random enumeratie: 1 vd minst intelligente algoritmen • steekproeven i/d oplen -ruimte (risico op herhaaldelijk bekijken v dezelfde opling ) • volgens no free lunch stelling is gn enkel algoritme beter dan random enumeratie • 6= tss stochastische en deterministische algoritmen – deterministisch alg: bereikt vanuit gegeven opl altijd dezelfde andere opl bv. steepest descent – stochastische alg: tijdens zoeken worden veel random beslissingen genomen bv. simulated annealing

22

6.2

Complexiteit, N, NP

• bekende complexiteitsklassen: P en NP • probleemklasse P (= Polynomiaal): verz problemen die in polynomiale tijd (O(nk ) k = integer) opgelost kunnen worden o/e deterministische Turing machine (theoretisch model) → alg: worden beschouwd als haalbare problemen • probleemklasse NP (niet-deterministisch polynomiaal (6= niet-polynomiaal)): verz problemen die in polynomiale tijd opgelost kunnen worden o/e niet-deterministische Turing machine • niet-deterministische Turing machine: keuzes maken zodat nt alle berekeningen nodig zijn, de berekening → zoekboom • probleem is in NP als zoekboom polynomiaal is in hoogte; het # knopen kan exp zijn • als alle zoekpaden in parallel doorlopen → in polynomiale tijd een opling bekomen • als deterministisch juiste pad i/d zoekboom bepaald kan worden voor elk probleem, → probleem behoort tot klasse P • alle problemen in P behoren ook tot NP • algoritmische kloof : indien de bewezen complexiteit v/e probl < complexiteit v/h beste algoritme tot nu toe gekend bv. de complexiteit van sorteren is O(NlogN) (bewezen), er bestaan algoritmen die sorteren in O(NlogN)→ gn algoritmische kloof als sorteeralgoritme sneller werkt dan O(NlogN), → speciaal ontworpen vr een bep deelverz van problemen • TSP: travelling salesman problem: bestaat wel algoritmische kloof • enige algoritme dat gegarandeerd nr een optimale opl leidt → enumeratie • best gekende methode: slechtste geval een complexiteit van O(N!) voor een probl met N steden • nog niet bewezen dat de complexiteit v/h TSP zodanig is dat het probl nt in polynomiale tijd kan opgelost worden • klasse NP compleet: – NP compleet ⊂ NP – probl R is NP compleet als R is NP-hard & R ∈ NP – R is NP-hard = minstens even moeilijk op te lossen is als elk ander probleem in NP – R is NP-hard = NP-compleet probl R0 bestaat → elk geval van R0 te herformuleren als een geval v R in deterministische polynomiale tijd – R moet even moeilijk zijn als R0 • vermits we niet weten hoe optimale opl te zoeken vr NP-hard probl, beperken tot benaderende opl, die wel in polynomiale tijd te berekenen zijn

6.3

Aanbevelingen

Zoekalgoritmen: • algemeen? specifiek? tijd-kost afwegingen maken • probl-specifieke info gebruiken indien mogelijk • groot verschil tss benchmark probl en re¨ele probl

23

6.4

Tijd- en geheugencomplexiteit

• Analyse van algoritmen: bepalen v/d hoeveelheid uitvoeringstijd en geheugenruimte • Een algoritme = gespecificeerde verz instructies die computer volgt bij oplossen v/e probl • Hoe de effici¨entie v algoritmen vergelijken? • Implementeren als programma’s: – uitvoeren op een set van inputs – meten hoeveel ‘resources’ elk gebruikt • nadeel: 2x implementeren, nt noodz allebei even goed geschreven, keuze testprobl kan 1 v/d 2 bevoordelen • betere techniek: asymptotische analyse (schattingstechniek) Tijdscomplexiteit: invloedsfactoren uitvoeringstijd: • hardware: snelheid CPU, bus, randapparatuur • competitie met andere gebruikers van de resources • programmeertaal en kwaliteit van de code • programmeervaardigheid • # stappen: # basisbew om een zekere grootte v input te verwerken • uitvoeringstijd mag nt afh zijn v/d specifieke waarden v/d operanden • inputgrootte: # inputgegevens dat verwerkt wordt • VOORBEELD: – sorteren van een aantal elementen (lengte van de lijst elementen) – bewerkingen op matrices (grootte van de matrix) Model geldt enkel voor sequenti¨ele verwerking • uitgaan v/e standrd instructieset, alle basisinstructies (+,*,=) nemen 1 tijdseenh in beslag • aannemen dat alle gehele getallen (int) een zelfde vast formaat hebben • onbeperkt RAM-geheugen Tekortkomingen basismodel: nt alle basisinstructies worden in exact dezelfde tijd uitgevoerd Functie c log(n) n n.log(n) n2 n3 2n

Benaming constant logaritmisch lineair n.log(n) kwadratisch kubisch exponentieel

Tabel 1: Functies in stijgende orde van toename • cn: met c = cte : lineaire orde v toename

24

• n2 : kwadratisch algoritme, ftie v/d uitvoeringstijd heeft dominante term n2 → in praktijk meestal onbruikbaar bij inputgrootte ¿¿ 1000 • n3 : kubisch algoritme: input v enkele 100-den → nt haalbaar • n · log(n): logaritmisch: dominante term is n · log2 (n) • 2n : exponentieel: onaanvaardbaar duur, zelfs vr kleine waarde v n Gemiddelde, beste en slechtste uitvoeringstijd: • bv. doorzoeken v/e array om de positie v/e geg waarde K te bepalen: – afh v/d plaats van K i/d array – Tb (n) best mogelijke: 1 – Ts (n) slechtst mogelijke: n – Tg (n) gemiddeld: n/2 • Nut v/d beste: als kan aangenomen worden dat best mogelijke het meest waarschijnlijk is • Nut v/d slechtste: belangrijk vr real-time toepen waarin bovengrens vr de uitvoeringstijd gekend moet zijn (bv. in luchtverkeersgeleidingscentrum) Asymotische analyse: • Constanten v/d lagere orde termen negeren als schatting gemaakt wordt v/d uitvoeringstijd • Bv. f (n) = 10n3 + n2 + 40n + 80 • Voor n = 1000 is f (n) = 10001040080 • Enkel de kubische term in rekening te brengen→ fout = 0,01% • Het in rekening brengen v/d leidende cte is nt zinvol omdat de exacte waarde v/d uitvoeringstijd toch afh v/d computer • Gedrag v/d ftie is nt zinvol vr kleine inputwaarden dus hier best het eenvoudigste algoritme gekozen • belangrijk: de orde v toename: O-notatie • Orde v toename v/e kwadratische ftie wordt voorgesteld door O(n2 ) • Gedrag van de uitvoeringstijd voor voldoende grote inputgroottes • Bovengrens vr de uitvoeringstijd geeft aan wat hoogste orde v toename is die een algoritme kan hebben (6= slechtst mogelijke uitvoeringstijd vr een gegeven inputgrootte n, wel bovengrens vr de orde v toename) • Zie voorbeelden in de slides! • Bovengrens en O-notatie ⇔ Ondergrens en Ω-notatie: analoog Notatie f (n) = O(g(n))

Relatieve oder van toename toename van f (n) is ≤ toename van g(n)

Tabel 2: Betekenis v/d asymptotische notatie

25

6.5

Besluit: tijd ↔ ruimte

tijd/ruimte tradeoff-principe: reductie in tijd alleen bekomen door ruimte op te offeren en vice versa • Voorbeeld: opslaan v 32 logische waarden • 32 int waarden gebruiken: 1 vr elk logische waarde → 128 bytes in Java • Een logische waarde kan slechts 2 waarden aannemen zodat de 32 bits v/e int kunnen volstaan om de waarden op te slaan • Probleem: vergt op de meeste pc’s meer tijd om 1 enkele bit uit een int waarde te wijzigen/op te vragen dan waarde van een byte of int variabele te wijzigen/op te vragen • Vereiste geheugenruimte voor elk v/d implementaties voor n logische waarden is O(n): verschil is enkel een cte factor Opzoektabel of lookup-table • Tabel stockeert de vooraf berekende waarde v/e ftie die anders telkens opnieuw moet berekend worden • Bv. 12! is grootste faculteit die nog i/e 32-bit int variabele kan gestockeerd worden • Als herhaaldelijk, in willekeurige volgorde, faculteiten berekend moeten worden → de moeite om waarden vooraf te berekenen en op te slaan Optimaliseren v/d code • Aanpassen v/h algoritme belangrijker dan optimaliseren v/d programmacode • Code optimalisatie = laatste stap • Kan leiden tot een reductie v/d uitvoeringstijd met factor 10 en v/h geheugengebruik met factor 2 of meer • Belangrijk om tijdstatisieken te verzamelen • Bv. met profilers die voor de meeste besturingsysten en compilers voor handen zijn

FUCKING SLIDES!!

26

Inhoudsopgave 1 Terminologie 2 Klassieke Technieken 2.1 Lineair Programmeren . . . . . . . 2.2 Simplex Methode . . . . . . . . . . 2.3 Dynamisch programmeren . . . . . 2.4 Zoekstrategi¨en . . . . . . . . . . . 2.4.1 Breedte eerst . . . . . . . . 2.4.2 Diepte eerst . . . . . . . . . 2.4.3 Bidirectioneel zoeken . . . . 2.5 Branch & Bound . . . . . . . . . . 2.5.1 Grafen kleuren - voorbeeld!

1

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

2 2 3 4 5 5 5 6 6 6

3 Lokaal Zoeken 3.1 Steepest descent . . . . . . . . . . . . . . . 3.2 Metaheuristieken . . . . . . . . . . . . . . . 3.3 Tabu search . . . . . . . . . . . . . . . . . . 3.4 Simulated Annealing (Dr. Graham Kendall)

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

7 7 8 8 10

4 Multicriteria Optimalisatie 4.1 Enkelvoudige ↔ Multicriteria optimalisatie . . . 4.2 Nt-gedomineerde oplen ↔ Pareto optimale oplen 4.2.1 Ideale doelvector . . . . . . . . . . . . . . 4.2.2 Utopische doelvector . . . . . . . . . . . . 4.2.3 Nadir doelvector . . . . . . . . . . . . . . 4.2.4 Dominantie . . . . . . . . . . . . . . . . . 4.3 Oplossingsmethodes . . . . . . . . . . . . . . . . 4.3.1 Klassieke methode: gewogen som . . . . . 4.3.2 -constraint methode . . . . . . . . . . . . 4.3.3 Evolutiemethode . . . . . . . . . . . . . . 4.4 Voorbeeld . . . . . . . . . . . . . . . . . . . . . . 4.5 Conclusie . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

12 12 14 14 14 15 15 17 17 18 18 18 18

5 Geheeltallig programmeren (Integer programming) 5.1 Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Lineaire Relaxatie . . . . . . . . . . . . . . . . . . . . 5.3 Creatieve Formulering . . . . . . . . . . . . . . . . . . 5.3.1 Geheeltallige hoeveelheden . . . . . . . . . . . 5.3.2 Binaire beslissingen . . . . . . . . . . . . . . . 5.3.3 Vaste kosten . . . . . . . . . . . . . . . . . . . 5.3.4 Logische beperkingen . . . . . . . . . . . . . . 5.3.5 Sequentieproblemen . . . . . . . . . . . . . . . 5.4 Formuleringen met sterke relaxatie . . . . . . . . . . . 5.5 Symmetrie vermijden . . . . . . . . . . . . . . . . . . . 5.6 Formuleringen met veel beperkingen . . . . . . . . . . 5.7 Formuleringen met veel variabelen . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

18 18 19 19 19 19 19 20 20 20 21 21 22

6 Complexiteit (Belangrijkste hoofdstuk!) 6.1 No free lunch . . . . . . . . . . . . . . . 6.2 Complexiteit, N, NP . . . . . . . . . . . 6.3 Aanbevelingen . . . . . . . . . . . . . . 6.4 Tijd- en geheugencomplexiteit . . . . . . 6.5 Besluit: tijd ↔ ruimte . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

22 22 23 23 24 26

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

27

. . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .