Model Building in Mathematical Programming, 5th Edition

Chapter 10

Building integer programming models II

10.1 Good and bad formulations

Most of the considerations of Section 3.4 concerning linear programming (LP) models will also apply to integer programming (IP) models and will not be reconsidered here. There are, however, some important additional considerations that must be taken into account when building IP models. The primary additional consideration is the much greater computational difficulty of solving IP models over LP models. It is fairly common to build an IP model only to find the cost of solving it prohibitive. Frequently, it is possible to reformulate the problem, giving another model that is easier to solve. Such reformulations must often be considered in conjunction with the solution strategy to be employed. It will be assumed throughout that the branch and bound method described in Section 8.3 is to be used.

In some respects, much greater flexibility is possible in building IP models than in building LP models. The flexibility results in a greater divergence between good and bad models of a practical problem. The purpose of this chapter is to suggest ways in which good models may be constructed.

It is convenient to consider variables and constraints separately. There is often the possibility of using many or few variables and many or few constraints in a model. The considerations governing this will be considered.

10.1.1 The number of variables in an IP model

We confine our attention here to the number of integer ...