EPSRC Reference: 
EP/P007228/1 
Title: 
Polytope methods in parameterized complexity 
Principal Investigator: 
Wahlström, Dr M A 
Other Investigators: 

Researcher CoInvestigators: 

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 Date  Panel Name  Outcome 
19 Jul 2016

EPSRC ICT Prioritisation Panel  Jul 2016

Announced


Summary on Grant Application Form 
Linear Programming is a mathematical problemsolving 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 worstcase" guarantees are possible. On
the other hand, methods employed in practice, such as branchandbound and
branchandcut, are known to have great success with many "realworld"
instances, despite being highly inefficient in the rare worst case. In
other words, the coarsegrained 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 branchandboundtype methods, from
the perspective of parameterized complexity. In parameterized complexity,
the coarsegrained view described above is replaced by a more
finegrained, 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 branchandbound
algorithms have been shown to have a very good theoretically guaranteed
performance for certain problems, under the assumption that the socalled
"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 programmingformulation of
the problem, referred to as persistence and halfintegrality  properties
that have not previously been fully investigated by the theory community,
possibly since their value is not apparent under a strict coarsegrained
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 branchandbound
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 nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

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: 
