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 combinatorial ones.

This research has the potential for significant long-term impact in the general areas of operational research, combinatorial optimisation, and discrete mathematics.

First and foremost, Mixed-Integer Linear Programming (MILP) methods are an essential tool for solving practical optimisation problems, both in an industry setting and more broadly. The research of this project points in several ways towards future investigations which could both improve our understanding of the efficiency of these methods, and lead to the development and deployment of improved methods for solving these problems in practice.

Regarding the former of these developments, it is common knowledge that MILP-solving methods are frequently efficient in practice, despite having
no non-trivial theoretical performance guarantees in general. That is, there is a significant gap between theory and practice, where the
(worst-case based) predictions from theory are found to be excessively pessimistic when compared to empirical real-world performance.

An analogous situation appears for SAT solvers, where modern CDCL (conflict-driven, clause-learning) SAT solvers are commonly praised as a near-universal solution method for several types of problems (including large-scale circuit verification problems), while on the other hand no non-trivial general performance guarantees are believed to be possible. In this case, a well-established theory of so-called backdoor sets has been developed to explain the efficiency of these methods.

One possible outcome of a future extension of this project in such a direction is a parameterized study of the efficiency if MILP solvers, analogous to the theory of backdoor sets for SAT. Preliminary research in this project points in this direction, including the study of the feasibility of using gap parameters in FPT algorithms.

There are also connections to be made regarding the identification of particularly effective cutting plane methods and well-solvable problem categories, extending the well-known class of max-flow problems.

Less broadly, the present project also suggests new algorithmic approaches for solving several problems which are of practical importance, in particular the classes of 0-Extension and Metric Labelling problems, which are natural problem formulations, motivated by practical applications. These approaches include fixed-parameter tractable cutting plane approaches (also known as branch-and-cut algorithms) for both natural parameters and gap parameters.

In addition to this, further long-term impactful applications are possible going via detours of generalisations of matroid theory and related topics in discrete mathematics, subject to successful outcomes of the corresponding sections of the project.

That said, all of the above impact cases would necessarily extend significantly beyond the end of the proposed lifetime of this project. The chief contribution of this project towards those impact stories would be to initiate these areas as fruitful venues of researh investigation, and to function as "seed example" for research to be built upon in later stages.

In turn, the best way to achieve such long-term impact will be to solidly ground the proposed research as relevant to the theoretical computer science community, and to engage actively with other researchers in related, relevant fields.

On a shorter time scale, although still reaching beyond the end of the planned project, algorithms developed in the scope of this project may also be of direct practical relevance. Ways to ensure this include the development of reference (open source) software implementations, either as independent software libraries or within the scope of existing projects such as COIN-OR, and to actively seek out and engage with practitioners where connections can be made.