LP Relaxations

• LP relaxation removes integrality constraint

  • If LP relaxation is infeasible, so is full model (both must share same solution space)

• A feasible integer LP relaxation gives a bound full model (lower for maximize, upper for minimize)

• A LP relaxation gives a bound on full model (upper bound for maximize, lower bound for minimize)

Previous slide

Next slide

Back to first slide

View graphic version