PhD thesis: ‘Easy searching with BnB’

If you’ve lost the combination of a combination lock, it can only be opened by going through all the possible combinations one by one. If the code has ten digits, there are ten billion possibilities to check. The so-called ‘NP-hard’ problems in Marcel Turkensteen’s PhD are comparable with the ‘combination lock problem’. With these problems too, the number of possibilities are unimaginably huge.

The trick is thus to explore the search space in an intelligent way. With the Branch and Bound (BnB) method, this is done by dividing up the search space into smaller sections. Turkensteen applied the BnB method to the travelling salesman problem, inter alia, whereby the shortest route through a collection of places has to be determined. The current BnB methods are improved in this PhD.

Curriculum Vitae
Marcel Turkensteen (Tolbert, 1979) studied Econometrics in Groningen. The research was conducted at the Marketing Department and the SOM research school. He will be awarded his PhD in Economics on 15 February 2007 (1.15 p.m.). His supervisor is Prof. G. Sierksma. His thesis is entitled ‘Advanced analysis of branch and bound algorithms’.