Log in
Research led by Professor Roger Fletcher has resulted in the development of a suite of algorithms that are now widely used throughout industry. An algorithm of fundamental importance constructed by Fletcher and co-workers is the filter method — a radically different approach to solving large and complex nonlinear optimization problems typical of those faced by industry. This algorithm was developed with the principal aim of providing a computationally reliable and effective method for solving such problems. The filter method is now utilised by a variety of high-profile industry end-users including IBM, Schlumberger, Lucent, EXXON, Boeing, The Ford Motor Company, QuantiSci and Thomson CSF. The use of the filter method has had a significant economic and developmental impact in these companies through enhanced business performance and cost savings.
Research by Gondzio (Maxwell Institute) on algorithms for large-scale optimization has led to major advances in the design of interior point methods (IPMs). The advances include new ways of exploiting centrality (1996-2008) as well as special preconditioning (2004) and warmstarting (2003, 2008) techniques. These techniques make it possible to solve more difficult optimization problems more quickly. Some of these have been implemented by all major commercial providers of optimization software including IBM, Gurobi, Mosek and FICO. The techniques have therefore had an economic impact on these companies and on thousands of their customers worldwide who now benefit from faster, more reliable methods to solve their challenging optimization tasks.
Graph-theoretic and mathematically rigorous algorithmic methods developed at the University of Hertfordshire have improved the applicability of compiler technology and parallel processing. A compiler developed in the course of a ten-year research programme at the university has been successfully applied to a number of commercial problems by re-purposing the research tool. NAG Ltd has adapted the tool into a commercial product [text removed for publication]. Numerous applications of the mathematical methods (such as type-flow graphs used conjointly for correctness and optimisation) have been deployed by industry (including SAP, SCCH, German Waterways Board) working closely with the university.
Many operations in daily life, from manufacturing to running a hospital, need to optimise the return on use of resources where volume and value are conditions. Scheduling theory tackles some of the hardest practical optimisation problems, not known to be solvable in reasonable computation time. Strusevich and Kellerer have been able to reformulate practical scheduling challenges as `knapsack problems' - dealing with volume and value constraints - and then design approximation algorithms which can be applied back to the original challenge. The work has attracted EPSRC funding, stimulated a new field of research which is developing fast, been widely published, led to presentations at international conferences including the 2009 Computers and Industrial Engineering conference attended by industry practitioners and is impacting on Combinatorial Optimisation research.
Algorithms developed by University of Glasgow researchers have helped NHS Blood and Transplant (NHSBT) tackle the complex problem of increasing the number of kidney transplants in the UK. For people with end-stage renal failure, the most effective form of treatment is transplantation. Dr David Manlove's research team have developed sophisticated algorithms which allow the NHS to help patients who require a kidney transplant, and who have a willing but incompatible donor, to exchange their donor with that of another patient in a similar position, in what is known as a paired exchange. By optimising kidney exchanges, University of Glasgow research has increased the number of transplants from paired donation by 40% between 2008 and 2013, when measured in comparison with the number of transplants that would have been possible with previous pairing techniques. Dr Manlove's work with NHSBT has translated not only into increased quality of life for patients freed from long term dialysis but will also afford the NHS an estimated £16 million of savings over the next 10 years.
Through close collaboration with scientists at the European Space Agency (ESA), research at the University of Southampton has developed new algorithms and an associated software tool that have contributed to more efficient spacecraft design. Now a standard component of the ESA's design technology, the tools have doubled the speed in which crucial design processes can be completed, resulting in increased efficiency over the REF period of 20 person-years — equivalent to €1 million in monetary terms — and maintaining the ESA's manufacturing competitiveness. The success of this work led to a €480,000 EU grant to adapt the tools for the avionics industry as part of efforts to meet ambitious environmental targets under the EU Clean Sky Initiative.
From 1995 Professor Munjiza's research at QMUL has led to the development of a series of algorithms which can predict the movement and relationship between objects. These algorithms have been commercialised by a range of international engineering and software companies including Orica, the world's leading blasting systems provider (via their MBM software package), and the software modelling company, Dassault Systems (via their Abaqus software). Through these commercialisation routes Munjiza's work has generated significant economic impact which is global in nature. For example, his predictive algorithms have enabled safer, more productive blast mining for Orica's clients — in one mine alone, software based on Munjiza's modelling approach has meant a 10% increase in productivity, a 7% reduction in costs and an annual saving of $2.8 million. It has also been used in Dassault Systems' Abaqus modelling software, which is the world's leading generic simulation software used to solve a wide variety of industrial problems across the defence, automobile, construction, aerospace and chemicals sectors with associated economic impact.
Prof Irving and Prof Sterling of the Institute of Power Systems at Brunel University collaborated with National Grid (NG) to develop and deploy a Sparse Dual Revised Simplex (SDRS), optimisation engine for real-time power allocation of all generators that were controlled by the NG. Since 2005-6 NG has been using the algorithms to aid in operation of their Balancing Mechanism, which provides a means of adjusting the level of production or consumption of individual generators or demands in the British Electricity Trading and Transmission Arrangements (BETTA). The algorithms enable the Balancing Mechanism (BM) to efficiently adjust outputs of generators in real time in order to balance the demand for electricity at minimum cost. Therefore, providing economic balancing of the transmission system at a scale of 2-3% of the £5bn annual electricity market (approximately £100M-200M per annum), hence about £800 million has been optimally traded in total in the BM since 2008. It is also important to acknowledge the reliability of the algorithms and SDRS optimisation engine from 2006 to present day, as periods of software outage carry high operational costs. The algorithms developed at Brunel continue to have very significant real world impact in terms of financial volume and its reach, such that every transmission scale power generator in the UK participates in the balancing mechanism and by implication every electricity-user benefits.