Optimisation technologies are used to deliver parcels and groceries cheaply and efficiently, to decide who gets a kidney transplant, to identify candidate chemicals for new drugs, to explain the building blocks of life, and to understand disease transmission in livestock. Graphs are the natural way of describing relationships, compatibilities, transport networks, chemical molecules, instructions and interactions in computer programs, and structured patterns; in particular, many important questions ask, in effect, whether certain graphs contain another subgraph, or can be covered by a collection of subgraphs. This project addresses optimisation problems which involve subgraphs, either with other constraints, or with a complex objective. Problem of this nature are common---we will be working with four real-world application areas involving disease transmission in livestock, matching kidney donors to recipients, metabolomics, and computational algebra.
Currently, dealing with these kinds of problems is complex, time-consuming, and requires a specialist. One option would be to select a particular constraint programming (CP), mixed integer programming (MIP), or boolean satisfiability (SAT) solver. These solvers require a problem to be modelled in terms of variables which have domains of values, and constraints between variables; the solver then finds a way of giving each variable a value from its domain, whilst satisfying all the constraints (or the best such way, as defined by some objective function). Different solver technologies have different restrictions upon the types of variables and constraints allowed---for example, SAT solvers support only boolean (true / false) variables and simple logical constraints. None of these technologies support graphs directly, and so the modeller would also have to come up with a way of encoding the graph part of the problem in a way that is compatible with the other constraints and the objective. Unfortunately, even the most experienced modellers are unlikely to make the best choice of solver and encoding on the first attempt, and even after a long development process, current optimisation technologies give performance several orders of magnitude worse than dedicated algorithms when dealing with subgraph problems.
Another alternative would be to implement a simple algorithm manually---but this is time-consuming and error-prone, and without a huge development effort the performance is again unlikely to be sufficient except for very small inputs. To address this, one might try to adapt a state-of-the-art algorithm from the literature to handle side constraints, but this has an even larger development cost: the theories underlying recently published algorithms are specific to certain variants of subgraph problems (e.g. induced or non-induced, sparse or dense, with particular injectivity and labelling rules, ...) and are not immediately compatible with arbitrary side constraints. Also, publicly available implementations of these algorithms are tailored to support scientific investigation, rather than being engineered for use in a production environment.
The aim of this project is to address the difficulties in solving graph-based optimisation problems from two directions. At the high level, we will provide modelling support for working with graphs directly: being able to express graph problems in a high level optimisation modelling language will make models easier to produce, understand, teach, and verify, and will make optimisation and subgraph technologies accessible to a wider academic and industrial audience. At the low level, we will improve solver support for graph-based and hybrid models: co-operation between general purpose optimisation solvers and dedicated subgraph algorithms will deliver better performance and scalability than any one technique can on its own, and will introduce new opportunities for automatic reformulation and constraint inference.
|