Mathematical optimisation

Article 3
Every problem has its algorithm
Rail & Recherche n°23 - April/May/June 2002

Two factors have contributed to the renewed interest in mathematical optimisation.
One is the rapidly growing power of computers. The other is the availability of more efficient algorithms, especially when so-called discrete solutions (i.e. binary choices like putting the locomotive on this train or that train) are sought. "Easy problems are ones that an exact algorithm can solve in polynomial time," says David De Almeida, of SNCF's Research Department. But for difficult problems, he notes, the time required by exact algorithms increases exponentially with the amount of input data, and the solution may take days or even weeks to find. Consequently, approximate algorithms, which look not for the optimal solution but for feasible solutions approaching the optimum, are needed.

Exact, approximate or heuristic algorithm

One trick with discrete-variable problems as with integer programs is to allow continuous choices (e.g. the program can allocate one-half or one-third of a locomotive to a train). The resulting solutions are unacceptable, but they determine the maximum achievable efficiency. The solution to the real problem, in which the locomotive remains whole, can be calculated by rounding the continuous-variable solution. The algorithm calculates the gap between this approximate solution and the optimal solution. Combinatorial optimisation problems can also be approached with the family of meta-heuristic algorithms, such as simulated annealing* and genetic algorithms. They produce acceptable, approximate optimisation solutions without, however, guaranteeing their quality. Algorithms in a final category are based not on mathematics but on a very general set of common sense notions whose efficiency is not always quantifiable. The choice of an exact, approximate or heuristic algorithm depends very often on the time available to find the solution. If the program has several hours, it can explore all possible choices; if time is short, it will test only a small set of combinations to arrive at an acceptable solution more rapidly. The most efficient algorithm is not necessarily the one that gives the optimal solution, but the one that comes up with at least one solution in the time available.

*Simulated annealing: a technique for searching the solution space through probability-based movements from one solution to another.