Hard Graph Problems - Theory and in Practice

总结：我们将研究最大权团和最大边权团问题，开发新的算法，编译一组研究人员可以用来比较算法的现实基准实例，并分析算法探索的搜索树，以更好地了解它们在实践中如何工作以及如何改进。图--节点的集合，在一些节点对之间有边--是一个基本的数学对象。最大团问题的任务是找到，对于一个给定的图，尽可能大的一组节点，使每对节点在集合中加入一个边缘。在社交网络的背景下，我们可以将其视为找到尽可能多的共同朋友的问题。这一点，以及相关的问题，有广泛的实际应用领域，如生物学和计算机view.AIMS和提示：我们的项目将研究最大团问题的两个概括。在第一种情况下，最大权重团（MWC），每个节点都有一个权重，我们试图找到一组具有尽可能高的总权重的成对相邻顶点。这是一个众所周知的问题，包括在组合拍卖（其中参与者出价捆绑，而不是个别项目）的赢家确定问题的应用程序。我们将考虑的第二个问题是最大边权重团（MEWC），其中每条边都有权重。我们将开发和实施新的算法来解决这些问题。我们将探索编码的问题，可以直接解决现有的通用求解器，也开发新的定制算法的问题。我们将开发精确算法和启发式算法，精确算法保证找到最优解，启发式算法并不总是找到最优解，但在实践中可能会更快地找到一个好的解决方案。（并在解决后扩大），和过滤步骤（以删除冗余的顶点和边），可以应用为预-我们将进行实证研究，以了解影响算法性能的问题特征。我们还将检查每个算法探索的搜索树，以更好地了解其行为，并寻求减少必须执行的工作量的方法来找到解决方案。我们将开发理论来解释为什么有些问题实例很难，而其他的很容易。这一理论将被实证检验，并用于指导新算法和算法的工程化。现有MWC文献的一个弱点是用于比较算法性能的基准实例是以非常人工的方式生成的，与现实世界的问题几乎没有相似之处。我们将编译一组更现实的实例的基准。这将是我们在我们的实验中使用，并将是一个宝贵的资源，为其他研究人员调查这一点和相关problems.APPLICATIONS：我们将探索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.