Beter zoeken met BnB
Datum: 15 februari 2007
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.
Marcel Turkensteen (Tolbert, 1979) studeerde econometrie in Groningen.
Het onderzoek werd uitgevoerd bij de afdeling Marketing van de
faculteit Economische Wetenschappen, onderzoekschool SOM.
Datum en tijd
15 februari 2007, 13.15 uur
Promovendus
M. Turkensteen
Proefschrift
Advanced analysis of branch and bound algorithms
Promotor
prof.dr. G. Sierksma
Faculteit
economische wetenschappen
Plaats
Aula Academiegebouw, Broerstraat 5, Groningen
Informatie
M. Turkensteen, tel. ( 050) 363 37 53 (werk) tel. 06 414 88984,
e-mail: mturkensteen@hotmail.com
Rijksuniversiteit Groningen