Branch and Bound

Branch and bound defines a variant of [[111.99_algo_backtracking|backtracking]] that can be used for optimization problems.

At each node in the tree we ask questions ::

Is the branch feasible?
If yes, can it contain solutions that are better than our current ones ?

Description ::

Branch describes fundamentally a technique that helps speeding up optizimiation problems.

The general procedure would be :

Assume we want to minimize a certain quantity. Branch and bound consists of two main ingredients:

==Branching==:: A set of solutions can be partitioned into mutually exclusive sets. In this way we can build a tree of the solution space where each vertex corresponds to a certain subset of solutions.

==Bounding==:: we need to be able to compute lower bounds on the cost of all solutions in certain subsets of solutions, and we need to be able to compare this lower bound to the current solution.

Example with Traveling salesman

Once again we have a tree where each branch is indicating which city to take. At each vertex, we require to find a lower bound on the cost of any tour that might complete that path. If that lower bound is higher than a solution we already have, then we can prune the whole branch >> why ? if the new path is already larger than a previous solution, why would we want to continue and waste space and computation if its gonna be larger all the time - until we have negative weights, which we are excluding most of the time. An additional path to our solution that is increasing it so much that we could instead use another solution that had less weight, then we can skip this path and prune its branching, because we will never use it again.

![[Pasted image 20230116143934.png]] At any given time we have a set of found paths that is set and was decided to be the best option. Now we have another set of unconnected - yet to be visited vertices - that we have to find a connection. To accomplish that, we

create the MST of this subset >> its easy to compute and guarantees the easiest connection between the paths! -
look at the cheapest connection between the discovered path and our newly calculated MST This is the estimation for the lower bound that we would come up with >> the minimal size that we would be able to create with this structure.

Application of principle ::

![[Pasted image 20230116144452.png]] Starting and goal would be A:: ![[Pasted image 20230116144511.png]] Structure of tree presenting our solution-tree.

each value next to a node represents the calculated lower-bound of taking this path.

Procedure to solve this problem : we walk through the tree from left to right::

in the beginning, we dont have any initial solution
we proceed along the left most branch in the tree, until we reach a leaf.
At each vertex we also compute the lower bound for this decision. ![[Pasted image 20230116144928.png]] Once that its done:
We walk the tree further to the right. To this end, we move up from the current leaf until we hit a vertex whose lower bound is smaller than the current solution - vetex D in this case .
We proceed to the right child of D, compute its lower bound and in this case found that it is infinity - no spanning tree possible
This concludes that we can prune that branch completely – will never result with solution for TSM.

To continue:

The next branch would be : A - B- C - H
- lower bound is 14
better solution already available, we can prune that branch We repeat that procedure until we are done and reduced the size of our tree to the minimum containing all solutions.
At some point there is a branch on which we cannot prune at all and in this case it happens that we discover a new - better - solution with value 8
We replace our initial solution of 11 with the newer one 8

Generic approach of branch and bound


Start with some problem P 0  
Let S = {P 0 }, the set of active subproblems  
bestsofar = ∞  
Repeat while S is nonempty:  
	choose a subproblem (partial solution) P ∈ S and remove it from S  
	expand it into smaller subproblems P 1 , P2 , . . . , P k  
	For each P i :  
		If Pi is a complete solution: update bestsofar  
		else if lowerbound(P i ) < bestsofar: add P i to S  

return bestsofar

General ingredients ::

==Branching== often, there are several ways in which this can be done, soe might lead to better solutions than others.

==Bounding==:: often there are many different ways to come up with lower bounds. In general there is a ==trade-off==::

The tighter the lower bounds are , the higher our ability to cut off branches of the tree.
But we need to compute lower bounds all the time, so we cannot afford a procedure that is too costly here either.

Often ==bounding== involves other algorithmic principles like approximation algorithms, relaxations to linear programming and more.

==Initial solution==: In the initial step of the algorithm, we often use any initial solution to compute the first upper bound on the solution. The better this bound the more we can cut it.

Performance ::

Branch and bound does not reduce the worst case complexity of an algorithm. Its more about finding more clever, heuristic ways to compute less in overall. Because of this uncertainty of reduction - or not - we cannot reduce the overall complexity but ought to find out through testing and finding optimal parameters for bounding and branching.

It can help to get better average cas performance. This might not be ease to prove but we might be happy if it runs fast in practice, without having any proof.

Final Remarks:

Designing good branch and bound algorithms is often not so easy.
It all depends on the quality of lower bounds
But good branch-and-bound algorithms are very valuable and help many applications that would otherwise awfully slow to compute – almost impossible without reduction of comutations required.

scattered-lenity