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 million 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.

This approach has been the subject of very extensive research, notably due to the availability of increasingly powerful supercomputers. Today several world-renowned solvers (e.g. Ilog-CPLEX, FICO-Xpress-MP, Gurobi) benefit from this research, as well as a growing number of free solvers such as COIN and GLPK.

Today Linear Programming has many industrial applications in the fields of oil, agri-foodstuffs, heavy industry, and manufacturing, and also in the service, transport, finance, insurance and other industries.

For more details, please contact us
Name
First Name
Company
Email *
Phone number
Your request *

* Mandatory fields

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 simplex and 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 the computer memory available, 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. This makes it possible to tackle problems of potentially infinite size.

Eurodecision has been using Linear Programming and its extensions since the company was founded, and today we are recognised experts in the field. We have used it for developing and deploying several projects for our customers, and it plays a key role in the design of our development platform and most of our software components. Our LP-Toolkit/LP-Colgen development platform enables teams to quickly develop Mathematical Programming solutions and interface them with their choice of any of the best solvers on the market, notably:

  • CPLEX (ILOG/IBM)
  • Xpress-MP (FICO)
  • Gurobi
  • COIN
  • GLPK
  • lp-solve

Eurodecision teams continuously monitor the latest solver technology available and are fully aware of each solver’s relative performance.