Efficient Algorithms for Multiple Instance Network Flow and Cut Problems

本项目将重点研究多实例组合优化问题，特别是两类多实例网络流问题和割问题，以及通过这种多实例计算解决的组合问题。许多非平凡的组合问题都是通过求解一系列网络流或最小割问题来解决的，其中每个连续的问题实例都以高度结构化的方式与其前一个问题实例不同。与单独解决每个实例相比，问题实例的相似性允许更有效地解决序列。该项目将专注于通过改变源节点和汇节点的选择或通过系统地改变边缘容量而产生的多实例网络流和最小割问题。解决这些问题的一个重要方法是理解序列中可能遇到的所有问题实例的空间的解集合的结构，并使用这种结构理解以某种紧凑的隐式形式有效地表示所有潜在实例的解集合。然后，一旦指定了特定实例，就可以更快地从表示中展开和检索该实例，而不是从头开始求解该实例。因此，该项目的很大一部分是为了开发这种结构理解和紧凑的表示法。

This project will focus on problems of multiple instance combinatorial optimization, particularly two types of multiple instance network flow and cut problems, and combinatorial problems that are solved by such multiple instance computations. Many non-trivial combinatorial problems are solved by solving a sequence of network flow or minimum cut problems, where each successive problem instance differs from its predecessor in a highly structured way. The similarity of the problem instances allows the sequence to be solved much more efficiently than by solving each instance independently. This project will concentrate on multiple instance network flow and minimum cut problems that are generated either by changing the choice of source and sink nodes, or by systematically changing edge capacities. An important approach to these problems is to understand the structure of the set of solutions to the space of all problem instances that might be encountered in the sequence, and to use this structural understanding to efficiently represent, in some compact implicit form, the set of solutions to all potential instances. Then once a particular instance is specified, it can be expanded and retrieved from the representation faster than by solving the instance from scratch. Hence a large part of the project is directed towards developing such structural understanding and compact representations.