New strongly polynomial algorithms for network optimisation problems

Lead Research Organisation: London School of Economics & Pol Sci
Department Name: Management Department


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.

Planned Impact

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.
Description The main achievements of the project are (i) the first constant factor approximation guarantee for the asymmetric travelling salesman problem (ATSP); (ii) new strongly polynomial algorithms for generalized network flow models, (iii) the development of the theory of geometric rescaling algorithms for Linear Programming; (iv) new algorithms for submodular function minimisation.
The main achievement in the first direction is represented by our joint paper with Ola Svensson and Jakub Tarnawski, that received the best paper award at the the flagship conference Symposium on Theory of Computing (STOC 2018), and is considered as a major breakthrough in the theory of computing and optimisation by resolving a longstanding open problem.
In the second direction, our main achievement is a joint paper with Neil Olver that was presented at STOC 2017. This paper presents a simple, yet very efficient algorithm for generalized flow maximization. In the theory of Linear Programming, our ongoing collaboration with Daniel Dadush and Giacomo Zambelli builds a systematic theory of a novel approach to the most fundamental optimisation problem. Some of our findings were presented on the conference on Integer Programming and Combinatorial Optimization (IPCO 2016); we are currently working on the second part of a planned series of 4 papers. Together with the research assistant Patrick Veenstra we have computer implementations and preliminary computational results. The results and the code will be published later during 2018. Our joint paper with Dadush and Zambelli at the Symposium on Discrete Algorithms (SODA 2018) applied the rescaling technique to submodular function minimisation, thereby giving the first polynomial time variant of Wolfe's classical algorithm. Moreover, we developed a robust and general framework for strongly polynomial computability. From the practical perspective, our result with Alina Ene and Huy Nguyen, presented at the Advances in Neural Information Processing Systems (NIPS 2017) conference, combined discrete and continuous approaches to obtain practically applicable algorithms for applications of submodular function minimisation such as image recognition.
Exploitation Route Our research addresses fundamental optimisation models. These models are used in real-life problems in many sectors such as telecommunication, finance, transportation and healthcare. New, efficient linear programming algorithms can lead to the development of more efficient optimisation solver, with impact across various fields of industry.
Sectors Digital/Communication/Information Technologies (including Software),Financial Services, and Management Consultancy,Healthcare,Transport

Description European Research Council Starting Grant
Amount € 1,488,674 (EUR)
Funding ID 757481 
Organisation European Research Council (ERC) 
Sector Public
Country European Union (EU)
Start 01/2018 
End 12/2022