关于多商品流问题的整数性和存在性的理论研究

Due to its deep intellectual content and wide range of applicability, network flow theory has attracted tremendous research efforts over the past six decades, and become a flourishing discipline containing a body of beautiful theorems and powerful methods. One of the most fundamental problems in this field is the maximum flow problem, which aims to ship as much of a single commodity as possible from the source to the sink in a given network, without exceeding the capacity of each arc. However, the requirement of one single commodity cannot satisfy the development of modern and emerging networks, which gives rise to the more complex but more applicable problem—multicommodity flow or multiflow problem. In multiflow problem, several commodities share the same network, but each of them has the own source and sink, respectively. In this project, the PI proposes to study the maximum multiflow problem, the feasible multiflow problem, and a variant of the classical feasible circulation problem. To be specific, the PI proposes.(i) to prove Karzanov's conjecture on total dual 1/4 -integrality in the maximum multiflow problem;.(ii) to characterize all pairs (G,H), where G is a planar supply graph having H as a demand graph, such a feasible multiflow exists in a given network; and.(iii) to show the structural characterization of 2-edge-connected multigraph admitting a nowhere-zero 3-flow.

由于网络流理论具有广泛的应用价值，比如交通网络、通信网络、社交网络等等，在过去的六十几年间，一直有大量的研究学者在网络流领域做着理论或者应用方面的研究，这也使得网络流理论不断有新的、适应时代的研究方向出现，从而发展成为一个繁荣的、具有多种研究方法的研究领域。传统的网络流问题往往是针对单一商品的运输，但是在很多实际问题中，往往要求多个商品，有各自的收发点，且在同一网络中运输，此时原本的网络流问题就不足以解决这种多商品共存的问题，因此多商品流问题应运而生。在本项目中，申请人拟针对多商品流问题的三个方向做进一步研究：(1)最大多商品流问题的全对偶整数性，即Karzanov猜想的等价命题；(2) 当供应图是平面图时，刻画可行多商品流的存在条件；(3)给出存在处处非零的3流的多重图的结构特征。

本项目根据实际执行情况，完成了有关整数多面体的几何秩的确定问题、竞赛图上反馈点集具有1/3整数解的结构刻画问题，并且即将完稿有关图上旅行售货员问题具有全对偶整数解问题的图形结构。下面针对这几个问题做一下具体说明：.1. 申请人结合前期有关整数多面体的工作，考虑了简单2-匹配多面体和b-匹配多面体的几何秩问题。几何秩是2013年Padberg提出的一个全新的有关多面体的概念，其定义依赖于多面体的结构特征和多面体的最简形刻画。这一新的概念有助于更好的理解某些特定的整数规划或者整数多面体的困难程度，加深对多面体问题的理解。申请人在这一概念的基础上，结合b-匹配问题的相关性质，确定了简单2-匹配多面体和b-匹配多面体的几何秩，丰富了对这一特殊整数多面体的理论研究内容。.2. 申请人针对竞赛图的反馈点集问题，在已有的关于全对偶整数性的图形结构基础上做进一步研究，深入考虑在整数最优解的基础上，具有1/3整数解的情况。申请人完成了竞赛图上具有全对偶1/3整数性的图形结构刻画，并且改进了验证多面体具有1/k-TDI性质的方法，使其在图上具有更强的操作性。这一验证方法可以推广到证明依托于图形结构的具有全对偶整数性的问题上。.3. 申请人针对图上的旅行售货员问题，即在图上确定权值最小的遍历每个顶点至少一次的闭迹，这是传统的旅行售货员问题的一个推广。申请人刻画了具有box-全对偶整数性的图形结构刻画，给出了包含K4缩图作为子图的图形特征，并且结合整数多面体的性质完成了特定结构具有全对偶整数解的验证。这对图上旅行售货员问题的整数最优解的情况进行了补充与完善。