In Chapter 2, we have seen how to solve LPs using the simplex algorithm, an algorithm that is still widely used in practice. In Chapter 3, we discussed efficient algorithms to solve the special class of IPs describing the shortest path problem and the minimum cost perfect matching problem in bipartite graphs. In both these examples, it is sufficient to solve the LP relaxation of the problem.
Integer programming is widely believed to be a difficult problem (see Appendix A). Nonetheless, we will present algorithms that are guaranteed to solve IPs in finite time. The drawback of these algorithms is that the running time may be exponential in the worst case. However, they can be quite fast for many instances, and are capable of solving many large-scale, real-life problems.
These algorithms follow two general strategies. The first attempts to reduce IPs to LPs – this is known as the cutting plane approach and will be described in Section 6.2. The other strategy is a divide and conquer approach and is known as branch and bound and will be discussed in Section 6.3. In practice, both strategies are combined under the heading of branch and cut. This remains the preferred approach for all general purpose commercial codes.
In this chapter, in the interest of simplicity we will restrict our attention to pure IPs where all the variables are required to be integer. The theory developed here extends to mixed IPs where only some of the variables are required to be integer, but the material is beyond the scope of this book.
Review the options below to login to check your access.
Log in with your Cambridge Aspire website account to check access.
If you believe you should have access to this content, please contact your institutional librarian or consult our FAQ page for further information about accessing our content.