Model Building in Mathematical Programming, 5th Edition

Chapter 13

Formulation and discussion of problems

A suggested way of formulating each of the problems of Part II as a mathematical programming model is described. Each of these formulations is ‘good’ in the sense that it proved possible to solve the resultant model in a reasonable time on the computer system used. With some of the problems, other formulations were tried only to show that computation times were prohibitive. It must be emphasized that although the formulations presented here are the best known to the author, there are probably better formulations possible for some of the problems. Indeed, one of the purposes of the latter part of this book is to present concrete problems that may help advance the art of formulation.

All the models described here assume that a computer program is to be employed using one of the following algorithms:

1. The revised simplex algorithm for linear programming problems.

2. The branch and bound algorithm for integer programming problems.

3. The separable extension to the revised simplex algorithm for separable programming problems.

These are the three algorithms that are most widely incorporated into commercial package programs.

For some of the problems, more specialized algorithms might be more efficient. In practice, the employment of such algorithms is often made difficult by the absence of efficient computer packages for handling large models. Where there is, however, obvious advantage to be gained from a specialized algorithm, this ...