| 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 Date | Panel Name | Outcome |
|
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
|
|
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: |
|