New strongly polynomial algorithms for network optimisation problems

The proposed research contributes to fundamental topics in Combinatorial Optimisation, aiming to devise strongly polynomial algorithms for new classes of linear and nonlinear optimisation problems.
The notion of polynomial-time complexity, introduced in the 1970s, is a standard way to capture computational efficiency of a wide variety of algorithms. Strongly polynomial-time algorithms give a natural strengthening of this notion: the number of arithmetic operations should not depend on numerical parameters such as costs or capacities in the problem description, but only on the number of such parameters. Strongly polynomial algorithms are known for many important optimisation problems. However, it remains an outstanding open problem to devise such an algorithm for a very fundamental optimisation problem: Linear Programming.
The most important goal of the proposal is to develop a strongly polynomial algorithm for linear programs with at most two nonzero entries per column. The problem is equivalent to minimum-cost generalised flows, a classical model in the theory of network flows. Finding a strongly polynomial algorithm was a longstanding open question even for the special case of flow maximisation, resolved by the applicant in a recent paper.
Further goals of the proposal include strongly polynomial algorithms for related nonlinear optimisation problems. Nonlinear convex network flow models have important applications for market equilibrium computation in mathematical economics. Very few nonlinear problems are known to admit strongly polynomial algorithms. The proposal aims for a systematic study of such problems, and will also contribute to the understanding of computational aspects of market equilibrium models.

The proposed research contributes to fundamental topics in Combinatorial Optimisation, an area at the intersection of Operational Research, Theoretical Computer Science, and Mathematics.
Optimisation challenges arise in many non-academic context including, for example, industry, medicine, engineering and commerce, with important - and growing - economic and social implications. The increased use by government agencies and commercial organisations of Organisational Research groups tasked with tackling these challenges highlights the breadth and depth of their relevance within these contexts. However, it has also demonstrated the capacity for optimisation to support improved performance within such organisations by enhancing production, logistics and technology use and, thereby, increasing efficiency. The digital revolution of the last two decades has compounded the significance of this contribution as organisations have moved ever further into the digital domain. Instead of simply improving and enhancing existing production schemes, computer scientists and operational researchers are now driving the next stage of optimisation development.

The basic toolbox of Optimisation includes Linear Programming and network flow theory. Advances within such models, both of which are very widely used, promise impacts both in terms of advancing scientific understanding and of supporting the application of Optimisation insights beyond academia. The following three groups will be the main non-academic beneficiaries of the research outcomes.

NA1 Researchers and programmers developing linear programming solvers for use in commercial contexts. Despite significant advances in commercial solutions for linear programmes, there remain fundamental gaps in our understanding. These include questions about the existence of a strongly polynomial algorithm for Linear Programming. By addressing that question, the research will help fill a vital gap in practitioner knowledge. The rapid development of linear and integer programming solvers demonstrates that purely theoretical results may lead ultimately to enhanced software performance, with substantial economic benefits to the companies within which they are used. The new type of Linear Programming algorithms investigated on the road to Main Goal 5 have potentially direct applications in solver development.

NA2 Researcher users and practitioners in sectors such as electronic commerce. Main Goals 3 and 4 address applications of generalised flow type models to market equilibrium computation and may also lead to new insights in mechanism design. Similar models have been implemented, for example, for advertisement slot auctions problems.

NA3 End users among those companies' clients and customers. By supporting improved performance within companies making use of linear programmes and market equilibrium models, the research will help those organisations deliver improved end user services to their customers and clients.

More broadly, by enhancing skills and understanding and providing tools to support enhanced operations - and subsequently improved commercial performance - within existing companies, the research will make an additional contribution to economic growth within the UK and on a global scale.