Advanced analysis of branch and bound algorithms

Marcel Turkensteen

    Research output: ThesisThesis fully internal (DIV)

    1427 Downloads (Pure)

    Abstract

    Als de code van een cijferslot zoek is, kan het alleen geopend worden door alle cijfercom­binaties 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.
    Original languageEnglish
    QualificationDoctor of Philosophy
    Awarding Institution
    • University of Groningen
    Supervisors/Advisors
    • Sierksma, G., Supervisor, External person
    • Goldengorin, B., Co-supervisor, External person
    • Ghosh, D., Co-supervisor, External person
    Award date15-Feb-2007
    Publisher
    Print ISBNs978-90-5335-110-9
    Publication statusPublished - 2007

    Fingerprint

    Dive into the research topics of 'Advanced analysis of branch and bound algorithms'. Together they form a unique fingerprint.

    Cite this