Skip to main content

Magnus First Grant

EPSRC grant for Magnus Wahlström

  • Date14 August 2016

The grant is for research in Polytope Methods in Parameterized Complexity.

Magnus 2

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.

Related topics

Explore Royal Holloway

Get help paying for your studies at Royal Holloway through a range of scholarships and bursaries.

There are lots of exciting ways to get involved at Royal Holloway. Discover new interests and enjoy existing ones

Heading to university is exciting. Finding the right place to live will get you off to a good start

Whether you need support with your health or practical advice on budgeting or finding part-time work, we can help

Discover more about our 21 departments and schools

Find out why Royal Holloway is in the top 25% of UK universities for research rated ‘world-leading’ or ‘internationally excellent’

Royal Holloway is a research intensive university and our academics collaborate across disciplines to achieve excellence.

Discover world-class research at Royal Holloway

Discover more about who we are today, and our vision for the future

Royal Holloway began as two pioneering colleges for the education of women in the 19th century, and their spirit lives on today

We’ve played a role in thousands of careers, some of them particularly remarkable

Find about our decision-making processes and the people who lead and manage Royal Holloway today