Branch-And-Bound (B&B) Algorithm

From LinkedAUB Collab
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