0
$\begingroup$

In the context of linear integer programming, we have a branch and bound algorithm described here. This involves solving the non-integer constrained linear program and successively introducing additional constraints, thus getting a bunch of integer solutions. Then picking the best among those.

And then there is also a branch and bound described in Wikipedia that is more broadly applicable and involves successively building solutions in the form of a tree where the leaves are the complete solutions. To avoid exploring the entirity of the prohibitively expensive tree, they prune it by bounding the partial solutions and eliminating branches when they are not likely to result in good solutions.

Are these two flavors of branch and bound connected? They seem to share a name, but I can't see how the first one is connected to the second one.

$\endgroup$

1 Answer 1

2
$\begingroup$

The first two sentences of the document you linked says it all:

The branch and bound method is not a solution technique specifically limited to integer programming problems. It is a solution approach that can be applied to a number of different types of problems.

In short, branch and bound, as utilized in solving ILP problems, is just a special case of branch and bound generally. The specific way of obtaining bounds by solving LP relaxations of the problem is specific to ILP, though.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.