Proefschrift: 'Beter zoeken met BnB'
Als de code van een cijferslot zoek is, kan het alleen geopend worden door alle cijfercombinaties langs te gaan. In het slechtste geval is de laatste combinatie de juiste. Echter, als de code uit tien cijfers bestaat, moeten tien miljard mogelijkheden bekeken worden. De zogenaamde 'NP-lastige' problemen in het proefschrift van Marcel Turkensteen zijn vergelijkbaar met het 'cijferslotprobleem'. Ook bij deze problemen is het aantal mogelijkheden buitensporig groot.
De kunst is derhalve om de zoekruimte op een slimme manier af te tasten. Bij de Branch and Bound (BnB) methode wordt dit gedaan door de zoekruimte op te splitsen in kleinere deelgebieden. Turkensteen past de BnB methode onder andere toe bij het handelsreizigersprobleem, waarbij een kortste route door een verzameling plaatsen bepaald moet worden. Dit probleem is in algemene vorm nog steeds niet opgelost. De economische gevolgen kunnen groot zijn: zo staat nog steeds niet vast of bijvoorbeeld een routeplanner vrachtwagens optimaal laat rondrijden. De huidige BnB-methoden worden in dit proefschrift met name verbeterd door niet naar de kosten van een verbinding te kijken, maar naar de kostentoename als een verbinding niet gebruikt wordt: de boventolerantie.
Curriculum vitae
Marcel Turkensteen (Tolbert, 1979) studeerde econometrie in Groningen. Het onderzoek werd uitgevoerd bij de afdeling Marketing en SOM. Turkensteen promoveert op 15 februari 2007 (13.15 uur) tot doctor economische wetenschappen in de bij prof.dr. G. Sierksma. De titel van het proefschrift is:
Advanced analysis of branch and bound algorithms.
Laatst gewijzigd: | 31 januari 2018 11:51 |
Meer nieuws
-
02 mei 2024
Johan Remkes te gast in podcast Leiderschap in Onzekere Tijden Live
Oud-minister en oud-informateur Johan Remkes is op 15 mei te gast in de Podcast Leiderschap In Onzekere Tijden. In de liveopname van de podcastaflevering gaat hij met FEB-hoogleraren Janka Stoker en Harry Garretsen in gesprek over de huidige...
-
29 april 2024
Nieuwe dataset belicht oorsprong van moderne economische groei
In een nieuwe update van de gerenommeerde Maddison Project Database werpen economisch historici een nieuw licht op de oorsprong van moderne economische groei.
-
29 april 2024
Guido Berends and Hylke Dijkstra win FEB Research Awards 2023
The awards for best PhD thesis and best graduate of the research master were presented at the annual PhD conference held on April 18. Guido Berends won the Best PhD Thesis Award 2023 and Hylke Dijkstra won the Research Master Graduate Award 2023.