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

Bachelor thesis (2021)

Authors

J. de Jong Electrical Engineering, Mathematics and Computer Science

Contributors

FM de Oliviera Filho (supervisor 1)
J.L.A. Dubbeldam Mathematical Physics - EEMCS (supervisor 2)
Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright: © 2021 Jelle de Jong
Branch and Bound 0-1 Knapsack Time estimation
More Info
expand_more

Published Date

2021

Language

English

Reuse Rights

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.

Faculty

Electrical Engineering, Mathematics and Computer Science

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.