Interior Point method for Large Scale Linear Programming (LP) Problems

NAG Library mini-article

Interior Point Method for Large Scale Linear Programming (LP) Problems

NAG introduces at Mark 26.1 a new interior point solver (e04mt) for large scale LP problems. It is part of NAG's ongoing effort to expand and improve its offering in mathematical optimization.

Linear Programming problems became very popular soon after the first practical solvers were developed in the late 1940s thanks to their flexibility and modelling ease. Since then significant improvements in theory as well as a rise in computing power has helped in adopting LP across many fields and industries, including logistics and finance, and the problem sizes have grown significantly.

The new solver is based on an Interior Point Method (IPM), a viable alternative to simplex/active-set methods. Active research in the last 20 years has led to the development of extremely efficient and reliable IPMs. The main characteristic of this type of solver compared to active-set methods is a fast convergence in a low number of iterations, each of which has a high computational cost. In practice, one interior point iteration consists mainly in factorizing one big sparse linear system.

The new solver is built upon a very efficient sparse linear algebra package and actually implements two variants of interior point methods: the Primal-Dual and Self-Dual methods. The Primal-Dual usually offers the fastest convergence and is the default choice for the solver. However, the Self-Dual presents several attractive features:

  • all convergence measures decrease at the same rate;
  • very reliable infeasibility detection;
  • generally better behaviour on pathological problems.

Both methods should present significant improvements for large scale problems over the current LP/QP solvers in the Library, such as e04nq.

e04mt is a part of the NAG Optimization Modelling Suite, it offers clarity and consistency of the interface of the solvers within the suite.

NAG Library: the world’s largest collection of robust, documented, tested and maintained numerical algorithms

If you need to add mathematical and statistical functionality to your applications or if you have complex mathematical problems to solve, the NAG Library will provide a host of benefits. The NAG Library provides a solid numerical foundation and serves diverse mathematical areas. It is expertly documented, maintained and supported and is regularly updated with cutting edge algorithmic capabilities.