Estimating the duration of the Branch and Bound algorithm for 0-1 Knapsack problems

Estimating the duration of the Branch and Bound algorithm for 0-1 Knapsack problems

de Jong, Jelle (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Optimization)

de Oliviera Filho, FM (mentor)
Dubbeldam, J.L.A. (graduation committee)

Delft University of Technology

Applied Mathematics

2021

The Branch and Bound method is a very useful method for nding solutions to optimization problems. However it does come with some problems as the search tree used for the Branch and Bound algorithm can be very large in size and can result in very long processing times as well as a large memory use. There is currently no known way to exactly know how large this tree will be and how long the algorithm will take, therefore having more information on this algorithm can be of great interest.
This report will look into the method used in the article Early Estimates of the Size of Branch-and-Bound Trees by Gerard Cornuejols, Miroslav Karamanov and Yanjun Li [1]. In this report their method will be tested against a specic set of problems, the 0-1 Knapsack problems. Their time estimation method will be tested against a variety of 0-1 Knapsack problems and the estimation will be compared to the real time it takes to solve the problems. This will give an idea of how good the method works for the method works for the 0-1 Knapsack problems and show any issues it might run into.

Branch and Bound
0-1 Knapsack
Time estimation

http://resolver.tudelft.nl/uuid:2b7b7ae6-26d9-4e77-8f91-c82d333358de

Student theses

bachelor thesis

© 2021 Jelle de Jong