Linear programming and mixed integer programming

Linear programming is very useful to model and solve production and network flow problems, and many other types of problems. An LP problem is a problem with a linear objective function and constraints which are either linear equations or linear inequalities. Here is an example for a LP problem:

$$\begin{array}{rrcrcr} \mbox{maximise} & 1000x_1 & + & 1300x_2... ... & & & x_1 & \ge & 0 \\ & & & x_2 & \ge & 0 \\ \end{array}$$

This LP has only two variables and two constraints. Today LP codes can solve problems with 100 000 variables and as many constraints, to just give a rough idea about the sizes of problems that can be solved.

The first ideas of how to solve LP problems date back to 200 years ago. This is not so surprising since LP problems are strongly linked to linear algebra which is an old subject. However, these early ideas were more of a theoretical nature and they were not used to solve any real world problems. George Dantzig developed the simplex algorithm and applied LP solution techniques to planning problems in the american military during the second world war. After the second world war until now there have been advances and continuous research in this area. Also the increase of power of computers has made it possible to apply LP codes to more and larger problems in industry and commerce.

Consider the following small example: A company produces fertilizers of type A and B. One tonne of type A fertilizer consists of 30% nitrogen and requires 3 tonnes of water in the production process. One tonne of type B fertilizer consists of 50% nitrogen and requires 4 tonnes of water in the production process. One tonne of type A fertilizer can be sold for 1000 Euro and one tonne of type B for 1300 Euro. The company can use at most 100 tonnes of water and 11 tonnes of nitrogen per day. How many tonnes of fertilizer of each type should the company produce to maximise its revenue? If $x_1$ and $x_2$ are the daily produced amounts in tonnes of fertilizers A and B respectively then this problem can be formulated in the linear programming form which was given above as an LP example.

If a LP problem has the additional constraint that some (or all) variables must be integer then this is called a mixed integer programming problem (or integer programming problem). Mixed integer programming, abbreviated MIP, problems are much harder to solve than LPs. LPs with 1000 variables and constraints are considered small today, whereas MIP problems of that size generally can not be solved to global optimality. MIP problems are so important because it is possible to model yes-no type decisions with 0-1 variables and also because for a lot of problems certain objects must be integer. For example, when modelling the number of planes an airline should order, the number of planes should of course be an integer. To order 2.6 planes does not make much sense. For further information about LP and MIP look up their frequently asked questions web page.