ABSTRACT
Integer programs (IPs) are LPs with the additional constraint that some or all of the variables must be integer. In practice, IPs are the most useful form of hard problem in optimization, for two main reasons: conversion of problems into IPs is usually much simpler than conversion into other forms and software for solving IPs is far more advanced than for any other NP-hard problem except the TSP. This chapter is a brief introduction to IP. It focuses on two topics: first, modeling hard problems as IPs; second, applying LP theory and algorithms to help solve IPs. Integer programming is very different from linear programming. LPs can be solved in polynomial time, whereas solving an IP is NP-hard. Many other graph-theoretic and other combinatorial problems require some thought to be modeled as IPs. In general, permuting or sequencing is harder to model than partitioning.
