Estimating the duration of the Branch and Bound algorithm for 0-1 Knapsack problems
J. de Jong (TU Delft - Electrical Engineering, Mathematics and Computer Science)
FM de Oliviera Filho – Mentor
Johan Dubbeldam – Graduation committee member (TU Delft - Mathematical Physics)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
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.