9 Integer Programming

When some variables must take whole values, a linear programme becomes an integer programme (IP), or a mixed-integer programme (MIP) if only some of them must. Integer variables model indivisible quantities, as with the inspectors of Section 1, and, much more importantly, yes-or-no decisions: whether to open a plant, whether to buy a machine, whether one job precedes another. That modelling power has a price: integer programming is NP-hard, and no algorithm is known that solves every instance quickly. Yet modern solvers, combining the LP relaxation with branching and cutting planes, routinely solve problems with thousands of integer variables. This section explains how.

Questions on this section

Stuck on something here? Ask below and it stays attached to this topic.