9.2 The LP relaxation

Dropping the integrality requirements gives the LP relaxation. Its optimal value is a bound: for a maximisation, \(z_{\mathrm {IP}} \leq z_{\mathrm {LP}}\), since every integer solution is feasible for the LP. The bound may be weak, and rounding the LP solution may give a solution that is infeasible, or feasible but poor. For the inspectors of Section 1 the LP gave \(6.25\) Grade 1 inspectors and Rs. 430, rounding up gave Rs. 481.6, and the integer optimum, \(4\) and \(3\) inspectors, Rs. 479.2, is not near the rounded LP solution at all (Software 9.6.3). When the constraint matrix is totally unimodular, as in the last two sections, the relaxation is exact; in general the art of formulation is to find constraints whose relaxation is as close as possible to the convex hull of the integer points.

Questions on this section

Stuck on something here? Ask below and it stays attached to this topic.