Relationship to Linear Programming

 

Given an integer program

there is an associated linear program called the linear relaxation formed by dropping the integrality restrictions:

Since (LR) is less constrained than (IP), the following are immediate:

• If (IP) is a minimization, the optimal objective value for (LR) is less than or equal to the optimal objective for (IP).
• If (IP) is a maximization, the optimal objective value for (LR) is greater than or equal to that of (IP).
• If (LR) is infeasible, then so is (IP).
• If (LR) is optimized by integer variables, then that solution is feasible and optimal for (IP).
• If the objective function coefficients are integer, then for minimization, the optimal objective for (IP) is greater than or equal to the ``round up'' of the optimal objective for (LR). For maximization, the optimal objective for (IP) is less than or equal to the ``round down'' of the optimal objective for (LR).

So solving (LR) does give some information: it gives a bound on the optimal value, and, if we are lucky, may give the optimal solution to IP. We saw, however, that rounding the solution of LR will not in general give the optimal solution of (IP). In fact, for some problems it is difficult to round and even get a feasible solution.