CAREER: Novel Parallelization Frameworks for Large-Scale Network Optimization with Combinatorial Requirements: Solution Methods and Applications

这项教师早期职业发展计划(CALEAR)补助金将通过支持研究高效、可扩展的方法来解决大规模网络优化问题，为科学进步和国家繁荣与福利的推进做出贡献。这些问题出现在列车调度、信息基础设施和电信网络设计中，往往涉及复杂的结构，使得它们的最优解对于现实问题的规模具有极大的挑战性。多核和集群计算的最新进展创造了令人兴奋的机会来开发新的方法，这些方法可以利用这些发展来增强优化方法的可扩展性。该奖项追求对网络元素的基本理解，这些网络元素可以通过新颖的并行化框架更有效地建模，从而设计出具有成本效益和结构健壮的网络。随之而来的教育计划旨在通过开发与优化概念相一致的新游戏工具，并通过适当的K-12和大学级场地传播这些工具，同时为代表不足的学生提供机会，促进新一代学生对STEM教育的参与度。本研究将开发一个新的基于图形的并行框架来解决具有组合要求的大规模网络优化问题。该方法利用决策图的结构，提供了网络问题的紧凑图形表示，设计了一种有效的并行化策略，具有均衡的工作负载和并行核之间的低通信开销，缓解了传统混合整数规划算法的巨大计算挑战。本研究还将通过新的分解和外逼近框架，将决策图的应用从传统的离散优化扩展到包括连续决策变量。开发的方法将应用于单元列车调度、负载平衡、带宽分配和可生存网络模型中出现的不可分网络流问题，与现代解算器和最新方法的结果相比，改善其解决时间和质量。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

This Faculty Early Career Development Program (CAREER) grant will contribute to the progress of science and the advancement of national prosperity and welfare by supporting research to study efficient scalable methods for solving large-scale network optimization problems. These problems, which appear in train scheduling, information infrastructure and telecommunication network design, often involve complex structures that make their optimal solution exceedingly challenging for realistic problem sizes. Recent advances in multi-core and cluster computing create exciting opportunities to develop new approaches that can exploit these developments to enhance the scalability of optimization methods. This award pursues a fundamental understanding of the network elements that can be modeled more effectively through novel parallelization frameworks, leading to the design of cost-efficient and structurally robust networks. The accompanying educational plan aims to boost the engagement of the new generation of students in STEM education by developing new gaming tools aligned with optimization concepts and disseminating them through appropriate K-12 and college-level venues, while providing opportunities for underrepresented students.This research will develop a new graph-based parallelization framework to solve large-scale network optimization problems with combinatorial requirements. The methodology exploits the structure of decision diagrams, that provide a compact graphical representation of the network problem, to design an effective parallelization strategy with balanced workloads and low communication overheads between parallel cores, mitigating a formidable computational challenge for conventional mixed-integer programming algorithms. This research will also expand the application of decision diagrams from the traditional discrete optimization to include continuous decision variables through novel decomposition and outer approximation frameworks. The developed methods will be applied to the unsplittable network flow problem that arises in unit train scheduling, load balancing, bandwidth allocation, and survivable network models to improve their solution time and quality when compared to the outcome of modern solvers and state-of-the-art methods.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.