Summary of the impact

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.

Underpinning research

Interior point methods. IPMs are an essential component of the optimization software used throughout the world. Although they were initially only applied to solve linear optimization problems, their potential advantages in other contexts were quickly recognised and they have been extended to other classes of problems: quadratic, nonlinear, conic, and semi-definite. IPMs reached maturity in the 1990s and since then they have been included in all the major commercial optimization solvers. It is widely accepted that IPMs outperform all earlier optimization methods on a broad range of complex problems, especially when instances are very large.

Multiple centrality correctors. Since the mid-1990s, Gondzio and co-workers have been developing new methods for IPMs. A key insight of their research was the recognition of the role of centrality in the practical behaviour of IPMs. This led them to design the first successful practical method exploiting centrality (Gondzio, Computational Optimization and Applications, 6, 137-156, 1996). The technique of multiple centrality correctors of Gondzio was refined in collaboration with Colombo, then a PhD student of Gondzio at the Maxwell Institute [1]. The method was shown to outperform the standard algorithms used at the time for solving difficult optimization problems. Special preconditioners for iterative (Krylov subspace) solvers in IPMs were subsequently developed by Gondzio in collaboration with Bergamaschi and Zilli [2]. The use of these preconditioners was shown to be particularly attractive when solving some difficult quadratic optimization problems. IPMs owe their success to the way in which they deal with the complementarity condition x_i s_j = 0 for all j. IPMs perturb this condition and replace it with x_i s_j = µ, where the parameter µ is driven to zero. To avoid guessing the partitioning into active and inactive inequality constraints, the algorithm forces a systematic reduction of µ. The partition of vectors x and s into zero and nonzero elements is gradually revealed as the algorithm progresses. The theory of IPMs requires that all complementarity products remain close to µ or at least display the same magnitude. This feature is commonly known as a good `centrality' property. However, standard steps in the Newton direction may destroy the centrality of the iterates. The technique of centrality correctors remedies this drawback by using a sequence of corrective actions which re-centre all complementarity products.

Warmstarting techniques. Gondzio and Grothey (also Maxwell Institute) developed new approaches to warmstarting (reoptimization) of interior point methods [3-4]. These are relevant to numerous situations when a series of somewhat similar problems needs to be solved. The warmstarting techniques were demonstrated to be particularly attractive in the context of portfolio optimization. Taken together, the techniques developed by Gondzio and collaborators have led to recognised improvements of IPMs, making them faster and able to solve larger problems.

Attribution. The research was led by J. Gondzio at the Maxwell Institute (MI) from 1998 on. A. Grothey was a PDRA of Gondzio on two EPSRC projects (starting in 1999) see below) before taking up an academic position in the MI (from 2005). M. Colombo, was a PhD student of Gondzio in the MI (graduated in 2007). External collaborators L. Bergamaschi and G. Zilli are at the University of Padova.

References to the research

Those marked with a * best indicate the quality of the research.

Grants

EPSRC grant GR/M68169, Parallel solutions of structured linear programs with interior point methods, £51K (1999).

EPSRC grant GR/R99683/01, Parallel solution of large scale structured nonlinear programs with interior point methods, £145K (2005).

Details of the impact

Linear optimization and quadratic optimization are at the heart of numerous industrial and commercial applications of mathematics. These arise in very different problems and in broad variety of sectors of the economy — finance, energy, telecommunications, transport, manufacturing, to mention but a few. Although many such problems involve some form of nonlinearity, the need to find a compromise between modelling accuracy and ability to solve the resulting optimization problem often necessitates using simplifying assumptions and employing the modelling based on linear and quadratic optimization. As a result, millions of optimization problems are solved every day and the vast majority of them, 90-95%, rely on linear or quadratic optimization models.

The ability to solve such problems efficiently is therefore crucial. In many situations, optimization problems have to be solved in real-time; this is for example the case when optimizing portfolios in high-frequency trading, when optimizing the usage of electricity transmission networks following the changes in energy demand, assigning frequencies to mobile phone communications, scheduling crew for sea or air transport, etc. The corresponding businesses are worth billions of pounds and any improvement in their operations achieved by optimization is of great value to the companies and to society. An indication of the size of the optimization software market is provided by the investment made in recent years by major companies: in 2009, IBM (market capital $220B) acquired ILOG, then owner of Cplex software for $340M (see http://www-03.ibm.com/press/us/en/pressrelease/26403.wss); in 2008 Fair Isaac (FICO, market capital $1.7B) acquired DASH, owner of the software Xpress (see http://www.fico.com/en/Company/News/Pages/01-22-2008.aspx).

Fast optimization solvers that can deliver reliable answers to challenging problems in acceptable time frames are the key to the successes of Cplex, DASH and others. The methods developed by Gondzio, specifically the technique of multiple centrality corrections [1], special preconditioners for KKT systems [2] and warmstarting techniques [3-4] have influenced the design of these modern optimization software. Multiple centrality corrections, in particular, have been implemented in all major commercial optimization solvers: IBM-Cplex, Gurobi, MOSEK, FICO Xpress, and in numerous academic optimization solvers: PCx, BPMPD, HOPDM, OOQP and OOPS [5-9]. Their use contributes to these codes' ability to solve difficult optimization problems. In some cases their use is essential to ensure that a problem can be solved at all. Their importance is reflected in a remark by a senior executive from Gurobi Optimization who stated that `it is not possible to build a competitive interior point code without centrality correctors' [6].

The following optimization solvers, which together dominate the optimization market, use multiple centrality corrections:

• IBM ILOG CPLEX Optimizer [5]
  http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/
• Gurobi Optimization [6]
  http://www.gurobi.com/
• MOSEK [7]
  http://www.mosek.com/
• FICO Xpress Optimization Suite [8]
  http://www.fico.com/en/Products/DMTools/Pages/FICO-Xpress-Optimization-Suite.aspx
• PCx [9]
  http://pages.cs.wisc.edu/~swright/PCx/
• OOQP [9]
  http://pages.cs.wisc.edu/~swright/ooqp/reference-manual/classGondzioSolver.html

Gondzio's research has therefore had an economic impact on the companies commercialising these solvers, and on their numerous customers across the world.

Sources to corroborate the impact

[5] Manager in the Optimization and Mathematical Software Business Analytics and Mathematical Science group of IBM Research USA will confirm that the centrality correctors are used in IBM-Cplex barrier.

[6] Senior executive of Gurobi Optimization will confirm that it is not possible to build a competitive interior point code without centrality correctors.

[7] Senior executive of MOSEK Optimization will confirm that the MOSEK optimization software employs a modified version of the centrality correctors.

[8] Senior software engineer at FICO Xpress will confirm that the underpinning research was useful to developing their software.

[9] Professor at University Wisconsin-Madison will confirm the benefits of using the centrality correctors in research optimization software.