EPSRC logo

Details of Grant 

EPSRC Reference: EP/P007228/1
Title: Polytope methods in parameterized complexity
Principal Investigator: Wahlström, Dr M A
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department: Computer Science
Organisation: Royal Holloway, Univ of London
Scheme: First Grant - Revised 2009
Starts: 15 January 2017 Ends: 14 April 2018 Value (£): 100,848
EPSRC Research Topic Classifications:
Fundamentals of Computing
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:
Panel DatePanel NameOutcome
19 Jul 2016 EPSRC ICT Prioritisation Panel - Jul 2016 Announced
Summary on Grant Application Form
Linear Programming is a mathematical problem-solving tool that has proven

immensely useful in industrial planning, operational research, and in

mathematical optimisation more generally. Over the decades since its

inception, a deep and rich mathematical theory has developed around it,

which has become a central part of the field of theoretical computer

science. The field has also spawned multiple commercial companies,

including ILOG (now owned by IBM), who developed the CPLEX optimisation

suite, credited by IBM for improvements in business efficiency yielding

multiple cases of savings of hundreds of millions of dollars.

However, there is a disconnect between the theoretical and practical

strands of this research. In theoretical computer science, the focus is on

methods with absolute guarantees of performance, i.e., performance

guarantees (in terms of efficiency of the algorithm and quality of the

produced solution) that apply for every possible input to the algorithm in

question. Consequently, the set of algorithms considered is restricted to

those for which such "universal worst-case" guarantees are possible. On

the other hand, methods employed in practice, such as branch-and-bound and

branch-and-cut, are known to have great success with many "real-world"

instances, despite being highly inefficient in the rare worst case. In

other words, the coarse-grained problem view of theoretical computer

science leads to unnecessarily pessimistic conclusions.

We propose a study of combinatorial optimisation, and in particular of the

power of linear programming tools and branch-and-bound-type methods, from

the perspective of parameterized complexity. In parameterized complexity,

the coarse-grained view described above is replaced by a more

fine-grained, multivariate view of problem complexity, where the

feasibility of "easy" problem instances can be explained by some parameter

of these instances being bounded, i.e., we can use a structural parameter

to capture and quantify the relative instance difficulty.

This perspective has recently had some success, where branch-and-bound

algorithms have been shown to have a very good theoretically guaranteed

performance for certain problems, under the assumption that the so-called

"integrality gap" of these instances is bounded (a condition that is also

known to be relevant in practice). These results build upon some very

particular structural properties of the linear programming-formulation of

the problem, referred to as persistence and half-integrality -- properties

that have not previously been fully investigated by the theory community,

possibly since their value is not apparent under a strict coarse-grained

worst case perspective.

This project will investigate the conditions for such structural

properties in several ways, thereby laying the foundations for a theory of

structured problem relaxations, and using these tools to develop new and

useful algorithms for a range of important problems, both branch-and-bound

based and more traditional combinatorial ones.

Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: