Branch-And-Bound (B&B) Algorithm
Jump to navigation
Jump to search
Description
The solution to the LP relaxation of an ILP is not guaranteed to produce an integer solution, and rounding the solution to the LP relaxation is not guaranteed to produce the optimal integer solution. The Branch-And-Bound algorithm is used for this purpose. This algorithm theoretically allows us to solve any ILP problem by solving a series of LP problems called candidate problems.
Concept Prerequisite
Wikipedia Reference
http://en.wikipedia.org/wiki/Branch and bound
Learning Material
Covered in Topic(s)
Integer Programming |