next up previous contents
Next: Branch and Bound Up: Solving Integer Programs Previous: Solving Integer Programs

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:

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.


Michael A. Trick
Sun Jun 14 12:49:07 EDT 1998