292. Branch and Bound

Integer Program

Linear Relaxation:

IP $⟶$ LP

Decompose an IP into mutltiple LPs

Definition 0: Linear Relaxation

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

Linear relaxation provides a bound

• ${𝑧}^{\ast }$: Optimal value of the Integer Program (IP)
• ${𝑧}^{\prime }$: Optimal value of the Linear Relaxation (LP)

1. Minimization

• 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

2. Maximization

• 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

• 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 ${𝑥}^{\prime }$ be an optimal solutions to the linear relaxation of an IP. If ${𝑥}^{\prime }$ is feasible to the IP, it is the optimal to the IP