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.