This article aims to serve two purposes:
What is Mathematical Programming? First a definition: Mathematical Programming (MP) is the use of mathematical models, particularly optimizing models, to assist in taking decisions. The term 'Programming' antedates computers and means 'preparing a schedule of activities'. It is still used, for instance, in oil refineries, where the refinery programmers prepare detailed schedules of how the various process units will be operated and the products blended. Mathematical Programming is, therefore, the use of mathematics to assist in these activities. Linear Programming One special case of Mathematical Programming which has been enormously successful is Linear Programming (LP). In an LP model all the relationships are linear, hence the name. LP has been so successful for two reasons:
However, Mathematical Programming is not just LP and its extensions, such as Integer Programming and Quadratic Programming. It also embraces heuristics and algorithms designed to tackle specific problems. The key characteristics of MP are shown in the diagram below.
MP Models The mathematical modeller abstracts from the real world a model of the system under investigation. The model comprises:
The definitions of all these components will change repeatedly during the building of the model. Although the process of MP involves finding optimum solutions, noby is suggesting that the solution is optimum to the real-world problem. If the model is reasonably faithful, then its optimum solution should be a good solution to the real-world problem. Whether it is or not, the process of building the model and analysing the solutions is a very powerful tool in analysing the real-world problem. Building an MP Model Optimization exercises a model in a far more rigorous way than other techniques, such as simulation. The optimum solution is, by definition, extreme. When building an MP model one is reminded of the proverb:
One builds the model and then turns it over to the optimization algorithm to find the best solution. If there is a fault in the model which can be exploited, the optimization algorithm will find it. The solution will be, at best, impracticable, at worst, nonsense. But through such mistakes one acquires greater understanding of the problem and moves towards solutions which are truly useful. Another aspect of optimization is its need for data. Some argue that this is a weakness, that you can only use the technique when all the data are available. But the requirement for data imposes a useful discipline. If the data do not exist to support some representation of the problem, there is no point using it. No conclusions will ever be able to be drawn. Instead, the representation of the problem must be changed to reflect the data which are available (or which can be estimated). The process of building an optimization model is therefore necessarily iterative. A first draft of the model will be sketched out and test data sought. Most probably some of the data will prove to be unobtainable. The model has to be altered before it can be run. The solutions are nonsense. Some constraint has been omitted. It is added. The solution is now plausible given the test data and the highly simplified representation. More detail is added to the model. Further data are sought. So the process goes on. As the model gets better, so the client's scepticism gives way to enthusiasm. The model starts to propose new ways of doing things. It is really beginning to add value. Ultimately the time comes when the model moves from being an experimental tool to a decision support aid. This is when the user interface becomes critical. Fortunately, MP software has moved forward a lot in the past few years and MP models can now be embedded straightforwardly in larger systems, taking their data from databases and spreadsheets and returning their results there. The MP Study Group What does this all mean for the MP Study Group? Two things:
The first meeting of the relaunched MP Study Group will be at 18.30 on Wednesday 5th October 1994 at Friends House, Euston Road, London (opposite Euston Station). Two talks will be presented. These illustrate different approaches to tackling practical problems which arose in agriculture but which are similar to many throughout the transport and distribution sector. Both involve working out patterns of collection for products where regular visits must be made to particular locations, in one case for eggs, and in the other for milk. Finally, if you have worked on any models which you think would be of wider interest and which you would like to present at a Study Group meeting, please get in touch. Related articles include How to Build a Mathematical Programming Model and A Comparative Survey of Mathematical Programming Software. To find other articles, refer to the MP in Action page. |
MP in Action > How to Use MP >