Linear and Mathematical Programming (Optimisation)

Linear programming, also known as linear optimisation, is a mathematical programming technique used to solve optimisation problems in which the constraints and objectives can be expressed in linear form. A linear programming model consists of an objective function to be optimised (such as maximising profits or minimising costs) and a series of linear constraints (such as limits on available resources). Linear programming uses mathematical algorithms to find the optimal solution that satisfies all the constraints.

Many resource optimisation problems involve maximising a linear function under linear constraints.

In mathematical terms:

Max Z = ∑i Xi (“Objective function”) Xi ≥ 0 For all values of j, ∑j AijXi ≤ Bj (“Linear constraints”)

Linear Programming is a widely used method for solving large-scale linear optimisation problems (sometimes involving several hundred thousand or even millions of unknowns). Although the initial groundwork was laid by the French mathematician Fourier, the field was given a major boost by George Dantzig’s development of the Simplex method in the 1940s.

Why use linear programming?

Linear programming is the most elegant approach available to us for solving a decision-making problem. It is an exact method that provides the optimal solution to the problem being addressed. However, care must be taken to ensure that the mathematical formalism and the data used accurately reflect the target decision-making problem, whose definition may evolve over time.

Driven by the emergence of increasingly powerful computing platforms, a very dynamic research activity is today benefiting world-renowned commercial solvers that implement this type of approach (IBM ILOG CPLEX, FICO-XPRESS-MP, GUROBI), as well as a growing number of open-source products such as COIN or GLPK. EURODECISION has developed extensive expertise across all of these products.

Many industrial applications of linear programming exist today in the oil, food processing, heavy industry and manufacturing sectors, as well as in services, transport and the finance/insurance domain.

What are the advantages and disadvantages of linear programming?

The advantage of linear programming is that it is an exact method for solving maximisation or minimisation problems involving linear functions subject to linear constraints. The resolution algorithms used in linear programming are efficient and reliable, and there are many commercial software tools available to implement them. However, this method cannot be used to solve non-linear problems. Furthermore, it sometimes requires computation times that are incompatible with certain use cases (e.g. real-time contexts).

Integer variables

In order to solve resource optimisation problems requiring the use of integer variables (variables expressing choices or integers), a mixed approach was adopted combining the Simplex method with a tree search method called Branch and Bound. This method is often supplemented by domain reduction techniques based on Constraint Programming or automatic generation of cuts. These improvements reduce the search scope and considerably improve algorithm performance. All these extensions are presently included in leading linear solver products.

The stability and performance of today’s algorithms have encouraged developers of Linear Programming applications to take on very large problems requiring decomposition techniques, so as to make their resolution compatible with available computer memory and to offer acceptable computation times to users. One notable technique, Column Generation, avoids the need to explicitly process all of the variables of a linear problem, making it possible to tackle problems of potentially infinite size.