Linear programming (LP) is a branch of optimisation that deals with the solution of optimisation problems with linear restrictions and a linear objective function.
The best-known algorithm for solving LPs is the simplex algorithm. This provides exact solutions for most practically relevant problems in a short computing time. Theoretically, however, the simplex algorithm has the disadvantage that the running time can grow exponentially with the size of the problem. For this reason, some algorithms were developed in the 1980s whose runtime is polynomially limited. However, these have not become established in practice, while some barrier methods have also proved to be practically efficient.
