Model Building in Mathematical Programming published in fifth edition
- Author: H.P. Williams
- Date: 04 Apr 2013
- Copyright: Photograph appears courtesy of Professor Williams. Professor Williams in his home county of Cornwall and his current project of walking around the coast of Britain-in stages.
A fifth edition of the widely read Model Building in Mathematical Programming has just been published. The first edition was published in 1978. In this article, H.P. Williams explains his original motivation and objectives in writing the book, how it has been modified and updated over the years, what is new in this edition and why it has maintained its relevance and popularity over the years.
This book has mirrored many of the developments in Mathematical Programming (Linear and Discrete Optimisation, usually known as Linear and Integer Programming) over more than three decades. I first met the subject in the late 1960s, during a vacation job, when I was a student. I was asked to formulate a model for a production/marketing problem in an engineering factory in my native Cornwall. This was a very satisfying (although slow) way to learn about the subject, but it forced me to face many of the practical issues of Operational Research (inaccuracy, unavailability and incompatibility data and redefining the ‘real’ problem in the light of critical examination of the first solution). I also realised that a major aspect of the problem required integer programming IP. At that time rudimentary software was available for linear programming (LP) but not IP. Also the preparation of the input required representation in terms of a large matrix of coefficients (MPS format) on punched cards. However the project was a ‘success’ in the sense that it revealed aspects of the organisation that had become obscured in organisational detail. Subsequently I realised that many aspects of the ‘solution’ were predictable without LP, suggesting the subsequent development of ‘Reduce/Presolve’ procedures.
In some ways learning 'on the job' gave me a deeper understanding than that which could have been gained from formal courses.
Later, on joining IBM, I worked on the development of the MPSX package. This was a massive package running on large mainframe computers. Models of a few hundred constraints and variables could take hours to solve. There was ‘big money’ involved as the major oil companies were heavily into LP and would spend large sums of money on the best hardware and package. During this time I developed a REDUCE module for the package as well as getting deeply involved in algorithmic theory. I also got involved with customers in the UK, Europe and North America helping them build their models and interpreting their requirements for enhanced software. The rule of thumb, in IBM, was that 40% of first models, built by customers, were infeasible and 40% were unbounded. Many were inaccurate and obscure to understand.
All of this was valuable experience which I incorporated in the book, when I returned to academia. In some ways learning ‘on the job’ gave me a deeper understanding than that which would have been gained from formal courses.
What became (and still is) particularly challenging in the 1970s was the modelling and solution of IPs. I incorporated some of the new theory which I, and others, had developed on this topic in the book. A major part of the book is the (now 29) problems, based on real life experience as well as published material. In the new edition, I give some more information on the origins of some of the problems. Many of these have become benchmarks for researchers and foundations for commercial models in many industries. While many of the models were difficult to solve in the 1970s, many are now easy to solve on laptop computers. However their structures are still very informative. A number of the models (particularly those requiring IP) are still difficult, or impossible to solve unless built in an efficient manner. This is particularly true of the five new models in the fifth edition including two in the rapidly developing area of molecular biology. With IP, if a model is badly built it can be impossible to solve. What's more the incorporation of conditions requiring IP is sometimes far from straightforward. However, the potential areas of application are vast. These considerations and the systematisation of the modelling process are all covered in the book. I continue to find papers written on problems and areas, which I am not aware of, which quote the book.
In spite of the tremendous advances in computing power and ‘user-friendly’ software the thorough understanding of a problem and its mathematical modelling is the most important part of the practical application of Mathematical Programming and Operational Research, in general.
In the late 1970s and 1980s, I played a part in developing modelling languages which enabled users to focus their attention on the ‘problem’ and the model rather than the internal data structures in the optimisation package. This has been illustrated in the NEWMAGIC (an analogue of ‘New Labour’ !) language illustrated in the new edition.
The book (which has evolved considerably since the first edition) continues to be in demand and cited and used by many academics, researchers and practitioners. It has been translated into a number of different languages. In spite of the tremendous advances in computing power and ‘user-friendly’ software the thorough understanding of a problem and its mathematical modelling is the most important part of the practical application of Mathematical Programming and Operational Research, in general.