Branch and Bound

289. Branch and Bound

Integer Program

Linear Relaxation:

IP LP

Decompose an IP into mutltiple LPs

For a Given LP, its linear relaxation is the resulting LP after removing all integer constraints

Example

Integer Problem:

Linear Relaxation:

Example

Integer Program:

Linear Relaxation:

Linear relaxation provides a bound

For minimization IP, linear relaxation provides a lower bound
The feasible region of the LP contains all feasible solutions of the IP (i.e., superset)
Therefore, the LP can achieve a value that is at most as large as the IP
Conclusion:

So, linear relaxation provides a lower bound on the optimal value of the integer program

For maximization IP, linear relaxation provides a upper bound
The LP may find a solution with an objective value greater than or equal to that of any feasible integer solution.
Conclusion:

So, linear relaxation provides an upper bound on the optimal value of the integer program

Problem Type	Linear Relaxation Provides	Inequality Between LP and IP
Minimization IP	Lower Bound
Maximization IP	Upper Bound

If the linear relaxation is infeasible or unbounded then the IP is infeasible or unbounded
If an optimal solution to the linear relaxation is feasible,

Let be an optimal solutions to the linear relaxation of an IP. If is feasible to the IP, it is the optimal to the IP

Example