The grant is for research in Polytope Methods in Parameterized Complexity.
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.
