Figure 1: Integer Linear Programming Formulation To solve an ILP problem, a natural idea is to relax the integral constraints.
replacing (6), (7), and (8) with: If LPR returns an integer solution, then it is also the optimal solution to the ILP problem.