Branch and bound Flashcards
what is the general idea of branch and bound
Split the feasible region into smaller regions, and solve a relaxed (simplified) problem in each subproblem.
Why is branch and bound “good”?
By splitting the feasible region, the aim is to look at regions where it is more likely that a good solution lies, rather than spending time searching in a region that we either know, or are quite certain no optimal solution will be in. Therefore, it is better then brute force enumeration.
What is the “bound” in branch and bound?
Refers to an optimistic solution to the problem. We get it by solving the LP relaxation of the integer subproblem. The idea is that by doing this, we can quickly see that if we have a subproblem that actually has an optimistic bound lower than a value we currently have from a different subproblem (actual integer solution, not optmistic bound), then we can ELIMINATE this shitty subproblem from consideration, and therby reducing the problem complexity.
another term for branch and bound enumeration?
We may call it “implicit enumeration”. We dont brute force it, but we still sort of count all of them, but just in a smart way.
Consider the branching. How do we branch out from a problem, creating new subproblems?
We modify it by adding constraints that basically split the feasible region.
If we have a binary variable 01, we can split on it, saying that one subproblem corresponds to variable = 0, while the other is required to be 1.
What structure do we use with branch and bound?
We use a tree structure.
The nodes represent subproblems.
THe endges represent split, adding constraints.
In a 0/1 problem, how can each subproblem be defined?
Each subproblem can be defined by fixing a subset of the variables to either 0 or 1.
what do we mean by pessimistic bounds?
Each feasible solution to the itneger problem is a pessimistic bound. This just means that whatever this value is, we know that since it is feasible, the optimal value can never be worse than this.
if min problem: Pessimistic bound is an upper bound.
If max problem: Pessimistic bound is a lower bound
Why do we mean by optimistic bounds?
In order to find an optimistic bound, we need to relax the IP problem.’
How can we generate pessimistic bounds?
We need to generate feasible solutions. This is generally the only way
Name properties between the solution to a relaxation and the solution to the IP problem
1) Solution to relaxation is optimistic always
2) If the relaxed problem has no feasible solutions, then the IP problem has no feasible solutions
3) If the relaxation is a feasible solution to the IP problem (satisfying integer constraints etc), then the solution to the relaxation is equal to the optimal solution of the IP problem.
4) Each feasible solution that is found to IP, provides a pessimistic bound of the optimal value of IP.
