Hard Graph Problems - Theory and in Practice

摘要：我们将研究最大权团和最大边权重团问题，开发新的算法，编译一组现实的基准实例，研究人员可以使用这些实例来比较算法，并分析算法探索的搜索树，以更好地了解它们在实践中的工作方式以及如何改进它们。CONTEXT：图-节点的集合，边位于某些节点对之间-是一个基本的数学对象。最大团问题是对于给定的图，寻找尽可能大的节点集合，使得集合中的每一对节点都由一条边连接。在社交网络的背景下，我们可以将其视为找到尽可能多的共同朋友的问题。这个问题和相关问题在生物学和计算机视觉等领域有着广泛的实际应用。AIMS&目标：我们的项目将研究最大团问题的两个推广。在第一个最大权重团(MWC)中，每个节点都有一个权重，我们寻求找到一组具有尽可能高的总权重的两两相邻的顶点。这是一个众所周知的应用问题，包括组合拍卖中的获胜者确定问题(参与者竞标的是捆绑物品，而不是单个物品)。我们将考虑的第二个问题是最大边权重团(MEWC)，其中每条边都有一个权重。我们将开发和实施新的算法来解决这些问题。我们将探索可由现有通用解算器直接解决的问题的编码，并为这些问题开发新的定制算法。我们将开发精确算法和启发式算法，前者保证能找到最优解，但在实践中并不总是找到最优解，但可能会更快地找到好的解。我们还研究了核化，即对问题进行预处理和压缩(并在解决后扩展)，以及过滤步骤(去除冗余的顶点和边)，可以作为预处理或在搜索中应用。我们将进行实证研究，以了解影响算法性能的问题特征。我们还将检查每个算法探索的搜索树，以更好地了解其行为，并寻找方法来减少找到解决方案所必须执行的工作量。我们将开发理论来解释为什么一些问题实例很难，而另一些问题实例很容易。这一理论将经过经验测试，并用于指导新算法和启发式算法的工程设计。现有关于MWC的文献的一个弱点是，用于比较算法性能的基准实例是以非常人为的方式生成的，与现实世界的问题几乎没有相似之处。我们将编制一组更现实的实例的基准集。这将对我们的实验有用，并将成为研究这一问题和相关问题的其他研究人员的宝贵资源。应用：我们将探索MWC和MEWC的新应用。作为一个具体的例子，我们将使用MWC来寻找肾脏交换问题的最佳解决方案-NHS已经在实践中使用这个问题来为患者分配活体器官捐赠者。我们相信，MWC算法将是解决肾脏交换问题的一种有效而简单的技术，并可以与现有技术相结合，使肾脏交换算法能够扩展到可能在不久的将来存在的国际方案。我们将开发软件，将二进制约束满足问题(CSP)-一类非常通用的问题--编码为MWC，因此将能够使用MWC解算器来解决许多类型的实际问题，如调度和车辆路径。我们将比较该解决方案技术与现有CSP解算器的性能。

SUMMARY: We will study the maximum weight clique and maximum edge weight clique problems, developing new algorithms, compiling a set of realistic benchmark instances which researchers can use to compare algorithms, and analysing the search tree explored by algorithms to better understand how they work in practice and how they may be improved.CONTEXT: Graphs---collections of nodes, with edges between some pairs of nodes---are a fundamental mathematical object. The maximum clique problem is the task of finding, for a given graph, as large a set of nodes as possible such that each pair of nodes in the set are joined by an edge. In the context of a social network, we can view this as the problem of finding as large a group of mutual friends as possible. This, and related problems, have a wide range of practical applications in fields such as biology and computer vision.AIMS & OBJECTIVES: Our project will study two generalisations of the maximum clique problem. In the first of these, maximum weight clique (MWC), each node has a weight and we seek to find a group of pairwise-adjacent vertices with as high a total weight as possible. This is a well known problem with applications including the winner determination problem in combinatorial auctions (in which participants bid on bundles, rather than individual items). The second problem we will consider is maximum edge weight clique (MEWC), in which each edge has a weight. We will develop and implement new algorithms to solve these problems. We will explore encodings of the problems that can be solved directly by existing general-purpose solvers, and also develop new customised algorithms for the problems. We will develop both exact algorithms, which are guaranteed to find an optimal solution, and heuristic algorithms which do not always find an optimal solution but may find a good solution much more quickly in practice.We also investigate kernalisations, where a problem is pre-processed and compressed (and expanded once solved), and filtering steps (to remove redundant vertices and edges) that can be applied as a pre-process or within search.We will perform empirical studies to understand problem features that influence the performance of algorithms. We will also examine the search tree that is explored by each algorithm, to better understand its behaviour and to seek ways to reduce the amount of work that must be carried out to find a solution.We will develop theory to explain why some problem instances are hard and others are easy. This theory will be tested empirically and used to guide the engineering of new algorithms and heuristics.A weakness of the existing literature on MWC is that the benchmark instances used to compare the performance of algorithms are generated in a very artificial way, and bear little resemblance to real-world problems. We will compile a benchmark set of more realistic instances. This will be of use to us in our experiments, and will be a valuable resource for other researchers investigating this and related problems.APPLICATIONS: We will explore new applications of MWC and MEWC. As one concrete example, we will use MWC to find the optimal solution to the kidney exchange problem---a problem which is already used in practice by the NHS to assign living organ donors to patients. We believe that MWC algorithms will be an effective and simple technique for solving the kidney exchange problem, and could be combined with existing techniques to enable kidney-exchange algorithms to scale to international schemes which are likely to exist in the near future.We will develop software that encodes binary constraint satisfaction problems (CSPs)---a very general class of problem---as MWC, and will therefore be able to use MWC solvers to solve many types of practical problems such as scheduling and vehicle routing. We will compare the performance of this solution technique with existing CSP solvers.