Imposing Connectivity Constraints in Large-Scale Network Problems

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

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.