网络环境下的新型组合优化问题研究

Combinatorial Optimization (CO) is a young and exciting discipline in Operations Research that is full of vigor. The progress of human life and development of science and technology continuously bring CO various challenges. Thousands of real-world problems can be formulated as CO problems. Classical CO problems based on traditional networks, such as the traveling salesman problem, matching, and network flow, play an important role in establishing and developing the research system of models, theories, and algorithms for CO. With the rapid development of information technology, the Internet has revolutionized not only the way people work, but also the way people live; "Internet" has become synonymous with "network". Classic CO models and methods are far from being able to cope with the new challenges posed by a variety of new networks created by the Internet. This project will focus on the study of new key CO models, theories and algorithms which arise in Internet applications to social networks, transportation networks, communication networks, and supply chain networks. The major topics under investigation include social network marketing, network ride sharing, and network facility location. From these major practical problems in every aspect of modern society, we will extract new CO and algorithmic game theoretical models, establish resolving algorithmic mechanisms, advance computational complexity theory, and develop new tools of algorithm design and analysis for CO under the environment of network interconnection, which would open up several new research directions, and promote the advancement of CO in the new era of networks.

组合优化是运筹学中充满活力的年轻学科。人类生活的进步和科技的发展源源不断地为这门学科提出各种挑战。成千上万的实际问题均可抽象成组合优化问题。基于传统网络的经典组合优化问题，如旅行商、匹配、网络流等问题对组合优化模型、理论和算法研究体系的建立发展起举足轻重的作用。随着科技日新月异，互联网彻底改变了人类的生活方式，逐渐成为网络的代名词。经典模型与方法已经远远无法应对互联网及其所促生的各种新型网络提出的新挑战。本项目将围绕互联网应用环境下的社会网络、交通信息网络、供应链网络出现的新型组合优化关键问题的模型、理论和算法展开研究。内容涵盖社会网络营销、网络车辆共享及网络设施选址。从这些与人们现代生活息息相关的重大实际问题中提炼新的组合优化和算法博弈模型、建立求解的算法机制、发展计算复杂性理论、开发网络互联环境下组合优化算法设计与分析的新工具，开拓若干新的研究方向，带动国内整个学科的发展。

组合优化是运筹学中充满活力的多学科交叉分支。大量的实际问题可抽象成组合优化问题，如旅行商问题，网络流问题、设施选址问题等等。随着互联网的广泛应用，人类社会的方方面面都发生了根本性的变化。这些日新月异的变化给经典优化模型与方法提出了一系列新的挑战。. 本项目围绕互联网应用环境下的社交网络、交通信息网络、供应链网络涌现的新型组合优化问题展开研究。建立了网络的疏密度、自私路由、路径博弈、车辆共享、设施选址等问题新的组合优化、矩阵优化和博弈模型。给出了相关的问题的最优解与均衡解的性质分析，设计了相应的多项式时间求解算法和算法机制。发表学术论文113篇。. 本项目取得的主要成果包括：（1）为一般图上的稠密连通k-子图问题设计了首个非平凡的强多项式时间近似算法。（2）设计了求解最优分数边着色和最密子图的强多项时间算法。（3）给出了德国数学家布雷斯于1960年代发现一个自私路由悖论的完整解答。（4）获得了该类动态路由的第一个子博弈精炼纳什均衡存在性结果，以及均衡、最优反应等一系列可计算性结果。（5）证明了居民的“自私路径选择行为”在高出行需求情况下能够使居民平均出行时间达到最小。（6）提出了求解不满足凹性或次模性设施选址问题的有效算法。（7）研究了线型网络上具有分段线性效用函数选址博弈问题，给出了常用机制仍然是防策略可信的充分必要条件，并证明了算法机制下界。（8）给出了求解私家车共享系统中的组合优化问题的计算复杂性分析和近似算法。（9）给出了求解群组背包问题几乎完整的算法及近似度分析。（10）给出了求解矩阵优化问题的谱算子函数的连续性，可微性和半光滑性的数学刻画。. 上述成果，解决了组合优化及相关领域若干公开难题，提出了一些新的既有很强应用背景又有理论意义的组合优化问题，为新型网络技术的应用与发展提供了理论基础和方法支撑。