权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Modelling and Optimisation with Graphs

使用图形进行建模和优化

基本信息

批准号：
EP/P026842/1
负责人：
Jessica Anne Enright
金额：
$ 85.77万
依托单位：
University of Glasgow
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2017
资助国家：
英国
起止时间：
2017 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FP026842%2F1
关键词：
Modelling Optimisation Graphs

项目摘要

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.

优化技术被用于廉价高效地递送包裹和杂货，决定谁可以接受肾移植，识别新药的候选化学物质，解释生命的组成部分，以及了解牲畜中的疾病传播。图是描述关系、兼容性、传输网络、化学分子、计算机程序中的指令和交互以及结构化模式的自然方式;特别是，许多重要的问题实际上都在询问某些图是否包含另一个子图，或者是否可以被一组子图覆盖。该项目解决涉及子图的优化问题，无论是与其他约束，或与一个复杂的目标。这种性质的问题是常见的-我们将与四个现实世界的应用领域合作，涉及牲畜中的疾病传播，肾脏捐赠者与接受者的匹配，代谢组学和计算代数。目前，处理这些问题是复杂的，耗时的，需要专家。一种选择是选择特定的约束规划（CP）、混合整数规划（MIP）或布尔可满足性（SAT）求解器。这些求解器需要一个问题被建模的变量具有域的值，和变量之间的约束;求解器然后找到一种方法，给每个变量一个值，从它的域，同时满足所有的约束（或最好的这样的方式，由一些目标函数定义）。不同的求解器技术对允许的变量和约束的类型有不同的限制-例如，SAT求解器只支持布尔（真/假）变量和简单的逻辑约束。这些技术都不直接支持图，因此建模者还必须想出一种方法，以与其他约束和目标兼容的方式对问题的图部分进行编码。不幸的是，即使是最有经验的建模者也不可能在第一次尝试时就做出最佳的求解器和编码选择，即使经过漫长的开发过程，当前的优化技术在处理子图问题时，其性能也比专用算法差几个数量级。另一种替代方案是手动实现简单的算法---但这既耗时又容易出错，如果没有巨大的开发努力，除了非常小的投入之外，性能也不太可能是足够的。为了解决这个问题，人们可能会尝试从文献中改编一个最先进的算法来处理边约束，但这需要更大的开发成本：最近发表的算法背后的理论是特定于子图问题的某些变体的（例如，诱导或非诱导，稀疏或密集，具有特定的注入性和标签规则，......）并且不立即与任意边约束兼容。此外，这些算法的公开实现是为了支持科学调查而量身定制的，而不是为了在生产环境中使用而设计的。该项目的目的是从两个方向解决基于图的优化问题的困难。在高层次上，我们将为直接使用图形提供建模支持：能够以高级优化建模语言表达图形问题将使模型更容易生成，理解，教学和验证，并将使更广泛的学术和工业受众可以使用优化和子图技术。在低层次上，我们将改进求解器对基于图和混合模型的支持：通用优化求解器和专用子图算法之间的合作将提供比任何一种技术本身更好的性能和可扩展性，并将为自动重构和约束推理带来新的机会。