What is integer programming?

Integer programming expresses the optimization of a linear function subject to a set of linear constraints over integer variables.

The statements presented in Linear programming: a production planning example are all linear programming models. However, linear programs with very large numbers of variables and constraints can be solved efficiently. Unfortunately, this is no longer true when the variables are required to take integer values. Integer programming is the class of problems that can be expressed as the optimization of a linear function subject to a set of linear constraints over integer variables. It is in fact NP-hard. More important, perhaps, is the fact that the integer programs that can be solved to provable optimality in reasonable time are much smaller in size than their linear programming counterparts. There are exceptions, of course, and this documentation describes several important classes of integer programs that can be solved efficiently, but users of OPL should be warned that discrete problems are in general much harder to solve than linear programs.