LP Training‎ > ‎

1. What is Mathematical Programming?

1. Introduction

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.

Mathematical Programming is one of a number of OR techniques. Its particular characteristic is that the best solution to a model is found automatically by optimization software. An MP model answers the question "What's best?" rather than "What happened?" (statistics), "What if?" (simulation), "What will happen?" (forecasting) or "What would an expert do and why?" (expert systems).

Being so ambitious does have its disadvantages. Mathematical Programming is more restrictive in what it can represent than other techniques. Nor should it be imagined that it really does find the best solution to the real-world problem. It finds the best solution to the problem as modelled. If the model has been built well, this solution should translate back into the real world as a good solution to the real-world problem. If it does not, analysis of why it is no good leads to greater understanding of the real-world problem.

The key characteristics of MP are shown in the diagram below.

2. What can Mathematical Programming Do?

The essential characteristics of a problem for Mathematical Programming to be applied are:

  • many potentially acceptable solutions
  • some means of assessing the quality of alternative solutions;
  • some interconnectedness between the variable elements of the system.

These are reflected in the essential components of an MP model:

  • the values of the decision variables, which describe the solutions;
  • the objective function, which measures the quality of solutions;
  • the relationships between decision variables, or constraints.

The definitions of all these components will change repeatedly during the building of the model. Although the process of MP involves finding optimum solutions, nobody 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.

Mathematical Programming is very suitable for problems involving blending, continuous flow processing, production and distribution, and strategic planning. It answers questions such as:

  • how much?
  • when?
  • where?

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:

  • there are robust 'black box' solvers which find the best solution to LP problems automatically;
  • many real-world phenomena can be approximated reasonably well by linear relationships.

Problems involving planning, blending, production and distribution are all capable of being solved using Linear Programming. The principles of MP also apply to problems involving logistics and scheduling but the processes of tackling such problems are more varied and a mixture of techniques is likely to be used, including MP, heuristics and special-purpose algorithms.

3. Building an MP Model

Much of the art of building an MP model revolves around deciding which aspects of a real-world problem should be included and which should not. In practice this is an iterative process. To start with, keep things simple. If in doubt, leave out. If the optimum solution from the resulting model is clearly wrong in the real world, add extra detail and try again.

When starting to formulate a model, it may be helpful to think in terms of the typical decision variables of an MP model. These are:

  • buying (or importing from outside the system being modelled);
  • making;
  • moving from place to place;
  • storing (or moving through time);
  • selling (or exporting to outside the system being modelled).

Typical constraints are:

  • availability (of materials, resources);
  • capacity (of processes);
  • quality (upper and lower limits);
  • demand;
  • material balance (within the system being modelled).

With these in mind, identify what data are available and construct the model to fit them. If there are some data which appear to be crucial but which are not available, consider how decisions are being made now. If judgements are being made based on estimates, try to obtain the estimates and use them. If estimates are not available, push ahead regardless and await the reaction to the results from your model. The supposed crucial factor may not matter very much, in which case you are better off without it. If the results of your model are nonsense, the explanation of why they are so should provide some guidance as to what to do.

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:

Man proposes: God disposes

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.

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.

4. Case Studies

Linked to these lecture notes are five issues of MP in Action which describe applications of Mathematical Programming:

  • contents next

  • Comments