Preface

Mathematical programmes are among the most widely used models in operational research and management science. In many cases their application has been so successful that their use has passed out of operational research departments to become an accepted routine planning tool. It is therefore rather surprising that comparatively little attention has been paid in the literature to the problems of formulating and building mathematical programming models or even deciding when such a model is applicable. Most published work has tended to be of two kinds. Firstly, case studies of particular applications have been described in the operational research journals and journals relating to specific industries. Secondly, research work on new algorithms for special classes of problems has provided much material for the more theoretical journals. This book attempts to fill the gap by, in Part I, discussing the general principles of model building in mathematical programming. In Part II, 29 practical problems are presented to which mathematical programming can be applied. By simplifying the problems, much of the tedious institutional detail of case studies is avoided. It is hoped, however, that the essence of the problems is preserved and easily understood. Finally, in Parts III and IV, suggested formulations and solutions to the problems are given together with some computational experience.

Many books already exist on mathematical programming or, in particular, linear programming. Most such books adopt the conventional approach of paying a great deal of attention to algorithms. Since the algorithmic side has been so well and fully covered by other texts, it is given much less attention in this book. The concentration here is more on the building and interpreting of models rather than on the solution process. Nevertheless, it is hoped that this book may spur the reader to delve more deeply into the often challenging algorithmic side of the subject as well. It is, however, the author's contention that the practical problems and model building aspect should come first. This may then provide a motivation for finding out how to solve such models. Although desirable, knowledge of algorithms is no longer necessary if practical use is to be made of mathematical programming. The solution of practical models is now largely automated by the use of commercial package programs that are discussed in Chapter 2.

For the reader with some prior knowledge of mathematical programming, parts of this book may seem trivial and can be skipped or read quickly. Other parts are, however, rather more advanced and present fairly new material. This is particularly true of the chapters on integer programming. Indeed, this book can be treated in a nonsequential manner. There is much cross-referencing to enable the reader to pass from one relevant section to another. This book is aimed at three types of readers:

It is also hoped that these problems will be of use to research students seeking new algorithms for solving mathematical programming problems. Very often they have to rely on trivial or randomly generated models to test their computational procedures. Such models are far from typical of those found in the real world. Moreover, they are one (or more) steps removed from practical situations. They therefore obscure the need for efficient formulations as well as algorithms.

Part I of this book describes the principles of building mathematical programming models and how they may arise in practice. In particular, linear programming, integer programming and separable programming models are described. A discussion of the practical aspects of solving such models and a very full discussion of the interpretation of their solutions is included.

Part II presents each of the 29 practical problems in sufficient detail to enable the reader to build a mathematical programming model using the numerical data. In some cases the origin of the problem is mentioned.

Part III discusses each problem in detail and presents a possible formulation as a mathematical programming model.

Part IV gives the optimal solutions obtained from the formulations presented in Part III. Some computational experience is also given in order to give the reader some feel of the computational difficulty of solving the particular type of model.

It is hoped that readers will attempt to formulate and possibly solve the problems for themselves before proceeding to Parts III and IV.

By presenting 29 problems from widely different contexts the power of the technique of mathematical programming in giving a method of tackling them all should be apparent. Some problems are intentionally “unusual” in the hope that they may suggest the application of mathematical programming in rather novel areas.

Many references are given at the end of the book. The list is not intended to provide a complete bibliography of the vast number of case studies published. Many excellent case studies have been ignored. The list should, however, provide a representative sample which can be used as a starting point for a deeper search into the literature.

Many people have both knowingly and unknowingly helped in the preparation of successive editions of this book with their suggestions and opinions. In particular I would like to thank Gautam Appa, Sheena and Robert Ashford, Martin Beale, Tony Brearley, Ian Buchanan, Colin Clayman, Lewis Corner, Martyn Jeffreys, Bob Jeroslow, Clifford Jones, Bernard Kemp, Ailsa Land, Adolfo Fonseca Manjarres, Kenneth McKinnon, Gautam Mitra, Heiner Müller-Merbach, Bjorn Nygreen, Pat Rivett, Richard Thomas, Steven Vajda and Will Watkins. I must express a great debt of gratitude to Robin Day of Edinburgh University, whose deep computing knowledge and programming ability helped me immensely in building the models for early editions of this book and implementing our design of the modelling system MAGIC. This has now been replaced by the system NEWMAGIC, which has been written by George Skondras. It is available with the optimizer EMSOL. All the models in the book have been built and solved in this system. The models, formulated in Part III, have been modelled in the NEWMAGIC language and are available on the website: www.wiley.com/go/model_building_mathematical_programming

Since the first edition was written, computational power has increased immensely. Solution times for the models are therefore, in most cases, of little relevance and are ignored. A few of the models are still difficult to solve. In these cases, some computational experience is given.

The fourth edition has been enhanced by new sections or models on Constraint Logic Programming, Data Envelopment Analysis, Hydro Electricity Generation, Milk Distribution and Yield Management in an airline together with state-of-the-art material and extra references on a number of topics and applications. I am very grateful to Kenneth McKinnon for advice and help with these models.

It is gratifying to know how well this book has been received together with the demand for a fourth edition.

Preface to the Fifth Edition

The fifth edition includes new sections on Stochastic Programming and Column Generation, a subsection on the Vehicle Routing problem and an enhanced section on Constraint Logic Programming. In addition, the subsection on modelling nonlinear functions and constraints, by integer variables, has been improved with a more versatile formulation. Many other small clarifications and improvements have also been included.

Five new problems have been added: a Car Rental and Return problem and an extension, an Airport Lost Baggage Distribution problem and two problems in Molecular Biology.

New references have been added, although it is recognized that it is impossible to mention all the excellent papers that have been written since earlier editions of this book. I apologize to the many authors of these papers who have not been cited.

A number of people have given me advice on improving and correcting the fourth edition to produce this fifth edition. In particular, I would like to mention Harvey Greenberg, John Hooker, Cormac Lucas, Andrew McGee and Ken McKinnon. They have all helped validate the new material. Also, a number of correspondents have pointed out small typos. I am grateful to them all.

PAUL WILLIAMS
Winchester, England