Summary of the impact

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.

Underpinning research

The underpinning research emanates from the team led by Professor Roger Fletcher, a world-leading researcher in optimization (see prizes and awards). Professor Fletcher has developed methodology and theory for a wide range of constrained optimization problem types such as Linear Programming, Quadratic Programming (QP), Nonlinear Programming (NLP) and Mixed Integer Nonlinear Programming (MINLP), in increasing order of complexity.

NLP concerns the minimization of an objective function of many variables, subject to nonlinear equality and inequality constraints on the values that can be taken by the variables. A well-known method for NLP is the Sequential Quadratic Programming (SQP) method, which involves the iterated solution of a sequence of QP problems.

Professor Fletcher is widely respected for his many contributions over the years to these areas (being the recipient of a number of awards [4]-[8]), including for the introduction of so-called Active Set Methods for QP, and classic optimization methods such as the widely used Davidon-Fletcher-Powell, Fletcher-Reeves and Broyden-Fletcher-Goldfarb-Shanno (BFGS) methods.

Most relevant to this Impact Case, is Professor Fletcher's invention of the filter globalization scheme in 1996 (UoD Numerical Analysis Technical Report NA171, see also ref. [1]). This method has won particular praise for its novelty and effectiveness (Lagrange Prize 2006). Up to that time, the usual procedure for solving an NLP problem was to use a 'penalty function' to induce convergence of e.g. the SQP method, and to require iterations of the SQP method to continuously improve the value of the penalty function. Often this requirement could considerably slow down the speed of convergence of the SQP method. In the filter method, the objective function and the constraint violation function are regarded as two distinct functions, and iterations can be accepted if they improve either one of these functions. This is a much less restrictive condition, and allows faster convergence of the NLP solver. The generality of the filter method allows for its use in many contexts, such as trust region, line search, and interior point methods.

In [1], Professor Fletcher and post-doctoral research assistant Dr Sven Leyffer (UoD 1993 - 2002, including EPSRC grant GR/K51204) introduced the implementation of the filter concept in the context of the SQP method for NLP, with suitable heuristics to induce global convergence. A wide variety of test results for large scale NLP showed its effectiveness and robustness in comparison to another state-of-the-art code. Production quality codes, filterSQP for NLP, and the QP solver bqpd with novel sparse matrix and other user-friendly facilities, were made available for distribution.

In follow-up papers [2, 3], Professor Fletcher was able to refine the heuristics in the filter methods, and used novel arguments so as to provide a mathematically exact proof of convergence.

The introduction of the filter idea has evoked considerable interest in optimization circles, and many mini-symposia and workshops have since been devoted to its implications. The new approach to balancing optimality and feasibility has been shown to have applications in many areas of optimization and has been utilized by researchers in diverse areas such as constrained and unconstrained optimization, solving systems of nonlinear equations (the idea of a multi-filter), and in derivative-free optimization (references [1, 2] have been cited over 1000 times).

The research was carried out by Professor Roger Fletcher, Baxter Chair of Mathematics and post-doctoral research assistant Dr Sven Leyffer between 1993 and 2006. Dr. Leyffer left in 2002 to take up a position at the Argonne National Laboratory, Argonne, IL USA.

References to the research

Evidence of Research Quality:
Prizes and Awards to Professor Roger Fletcher:

[4] Awarded the 1997 George B Dantzig Prize by the Society for Industrial and Applied Mathematics

[5] Elected Fellow of the Royal Society of London, 2003

[6] Awarded the 2006 Lagrange Prize in Continuous Optimization by The Mathematical Programming Society and the Society for Industrial and Applied Mathematics

[7] Awarded the 2008 Royal Gold Medal from the Royal Society of Edinburgh

[8] Elected SIAM Fellow, 2009

Details of the impact

Optimization problems are ubiquitous in industry, for example, how to schedule airline crew, how to improve drug design, how to minimize production costs, how to maximize power output, how to find the lowest energy configuration, and how to find the best combination of medicines for a particular patient.

The invention of the filter method by Professor Fletcher and co-workers meant that a broad range of previously computationally unfeasible optimization problems could be efficiently solved. Arguably the most challenging of the optimization problem types is MINLP, in which some of the variables are constrained to take only discrete values. Until fairly recently it was regarded that such problems were intractable unless the number of variables was small. Professor Fletcher and co-workers showed that using filterSQP to solve the many NLP sub-problems generated in the Branch and Bound method for MINLP, has considerably extended the range of problems that can be solved. A production software product MINLP_BB has been made available and has attracted many users. Since 1997, the University of Dundee has issued close to 100 licenses for Professor Fletcher's optimization software algorithms to a range of end-users including numerous international-scale industrial companies e.g. those referred to in Section 1.

Four examples of where Professor Fletcher's filter method has made direct impact are:

(i) Use of the filter method in the Design Explore software utilized by The Boeing Company.
[Dates Impact Occurred: January 2008 - present]

Boeing is the world's leading aerospace company and the largest manufacturer of commercial jetliners and military aircraft. It employs over 170,000 people worldwide with a total revenue in 2012 of $82 billion. Design Explore is the primary tool for design optimization used by the Boeing company. The filter method invented by Professor Fletcher and co-workers has been at the heart of this software.

"...it is difficult to imagine how different life at Boeing would be without the optimization tools.... whose underlying filter-based methods were inspired by the idea of Roger Fletcher and Sven Leyffer...no constrained optimization problem is ever solved in Design Explore without making use of the [Fletcher] filter", [FS1].

The filter algorithm continues to be used extensively in engineering projects throughout the company. Examples that can be corroborated in open literature are the joined wing sensorcraft (LeDuox et al. AIAA2008-7190), helicopter rotor blade design (Hirsh et al. AIAA2007-1252) and hypersonic vehicle design (Bowcutt et al., AIAA2008-2591).

(ii) Use of the filter method in IPOPT core optimization software in the IBM circuit tuning tool EinsTuner.
[Dates Impact Occurred: January 2008 - present]

IBM is an international IT company employing over 430,000 worldwide (over 20,000 in the UK) with a total revenue in 2012 of $105 billion dollars. The EinsTuner software is used to determine the optimal transistor sizes in commercial digital circuits. The filter concept is central to the IPOPT software, which is at the core of EinsTuner. The advantage offered by this software has been valued by IBM at "millions of dollars" and IPOPT is "extremely widely used". "The filter idea...has extraordinary impact, both at IBM and ..[other] industry" [FS2].

"At IBM Research, we also used Prof. Fletcher's filterSQP and bqpd optimization codes within algorithms for the solution of MINLPs. ...Prof. Fletcher's filterSQP and bqpd solvers are used to solve continuous subproblems, the number of which can be in the millions during the solution of a single MINLP. In this context, the reliability and efficiency of the filterSQP and bqpd software packages have been essential for the good performance of the MINLP solvers." [FS3].

(iii) Use of the filter method in European Space Agency activities.
[Dates Impact Occurred: January 2008 - present]

The ESA is a joint venture between 20 European Member States dedicated to the exploration of space. It employs over 2000 people and has an annual budget of near €5Billion. A fundamental requirement for ESA is to solve optimization problems related to space vehicle manoeuvre planning, trajectory optimization, vehicle performance optimization and optimal vehicle design. ESA has used filterSQP as a benchmarking tool for all their optimization developments. Two projects (totalling approx. €400K) were initiated to foster the utilization of filter techniques in European space industry. The impact of Prof. Fletcher's filter method in the work of ESA is best summarised by the following direct quotes:
"[Fletcher's] input proved indispensable for achieving the targeted quality of work"
"filter techniques.... reduced the computation time by a factor of two"
"Fletcher .. has advanced the way numerical optimization is carried out at the European Space Agency". Dr Sven Erb TEC-ECN / GNC Systems Engineer

(iv) Use of the filter method in TOMLAB.
[Dates Impact Occurred: January 2008 - present]

TOMLAB is the premier developer and distributer of large scale optimization software for use in conjunction with MATLAB. Since 2000, TOMLAB have offered Prof. Fletcher's algorithms (bqpd, filter SQP, miqpBB and minlpBB) as part of their software suite. Commercial clients selecting these codes include Honeywell International, General Motors, International Atomic Energy Authority and Draper Laboratories amongst others [FS4].

Prof. Fletcher's QP solvers are also utilized in a wide range of other industries for example in the forestry management systems GAYA and SIMO used by the Norwegian and Finnish industries. These industries contribute a significant component to the GDP of the Nordic countries [FS5].

As well as software tools, Prof. Fletcher has provided vital advice to a wide range of industrial end-users of his code including a consultancy agreement with the European Space Agency.

Sources to corroborate the impact

Factual Statements have been obtained from:

[FS1] Senior Mathematician, The Boeing Company, P.O. Box 3707, Seattle, WA 98124-2207, USA.

[FS2] Research Relationship Manager, USA (Chemicals), IBM Research Division.

[FS3] Senior Member, Nonlinear Optimization Research Group, IBM Research Division (until 2012); currently Associate Professor at Northwestern University, USA.

[FS4] CEO, TOMLAB Optimization Inc.

[FS5] Senior Researcher, Finnish Forest Research Institute.

Licence details available from Research and Innovation Services, University of Dundee.