权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Imposing Connectivity Constraints in Large-Scale Network Problems

在大规模网络问题中施加连接约束

基本信息

批准号：
1662757
负责人：
Austin Buchanan
金额：
$ 25.06万
依托单位：
Oklahoma State University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2017
资助国家：
美国
起止时间：
2017-06-15 至 2021-05-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1662757&HistoricalAwards=false
关键词：
Imposing Connectivity Constraints Large Scale

项目摘要

The design and analysis of networks constitute one of the most important classes of problems in the field of optimization. In practice, network models are used to address such diverse applications as wireless communication, energy distribution, and conservation planning. A network consists essentially of a set of "nodes", linked in some fashion by "arcs". Connectedness is often a critical feature of a functioning network. However, enforcing connectivity in standard network optimization formulations remains a significant computational challenge. This project considers new formulations that address node-connectivity constraints directly. Results from this project are expected to allow for the solution of large-scale instances of these problems to optimality in a reasonable amount of time. The PI will mentor graduate and undergraduate students, and through collaboration with the Oklahoma Louis Stokes Alliance for Minority Participation (OK-LSAMP), students from underrepresented populations will be provided the opportunity to participate in the research activities. Results from the project will be integrated into undergraduate and graduate courses. This project aims to develop fundamental theoretical and algorithmic advances for effectively imposing connectivity constraints in mixed integer programming (MIP) models in which the key decisions are at the vertex (i.e., node) level. Previous MIP-based approaches to solve vertex-centric connectivity problems use additional edge (and possibly flow) variables, which overburden commercial solvers, or rely on simple, weak inequalities, leading to the exploration of a large number of branch-and-bound nodes. This research is expected to overcome these limitations through two broad research tasks: (1) developing a rich body of knowledge about connectivity polyhedra in the space of vertex variables, and (2) designing efficient algorithms for solving related problems by exploiting this polyhedral information. It is expected that the research will also allow for significant improvements in solving hop-constrained and survivable network design problems.

网络的设计和分析是最优化领域中最重要的一类问题。在实践中，网络模型用于解决诸如无线通信、能量分配和保护规划等各种应用。网络基本上由一组“节点”组成，这些节点以某种方式通过“弧”连接。连通性通常是功能正常的网络的一个关键特征。然而，在标准网络优化公式中强制连接仍然是一个重大的计算挑战。该项目考虑直接解决节点连接约束的新配方。该项目的结果预计将允许在合理的时间内解决这些问题的大规模实例的最优性。 PI将指导研究生和本科生，并通过与俄克拉荷马州路易斯·斯托克斯少数民族参与联盟（OK-LSAMP）的合作，将为代表性不足的学生提供参与研究活动的机会。该项目的成果将纳入本科和研究生课程。该项目旨在开发基本理论和算法的进步，以有效地在混合整数规划（MIP）模型中施加连通性约束，其中关键决策位于顶点（即，节点）级别。以前的基于MIP的方法来解决以顶点为中心的连接问题使用额外的边缘（和可能的流）变量，这使商业求解器负担过重，或者依赖于简单的弱不等式，导致探索大量的分支定界节点。本研究通过两个广泛的研究任务来克服这些局限性：（1）在顶点变量空间中开发关于连通性多面体的丰富知识，以及（2）通过利用这些多面体信息来设计解决相关问题的有效算法。预计这项研究也将允许显着改善解决跳约束和生存的网络设计问题。