BRITE Relaunch: Compact Network Flows for Critical Infrastructure Engineering

网络无处不在。我们的社会每天都依赖于能源、交通和通讯网络。网络的设计和运行是一个跨越许多工程学科的主要问题。这项促进工程变革和公平进步的研究理念（BRITE）重新启动奖利用了网络流数学建模的新范式，以实现(1)开发更快、更可扩展的算法，以解决运输中大型、复杂的路由问题；(2)设计弹性电信网络，即使在关键组件损坏时也能继续提供高水平的服务。如果成功，该项目将大大提高我们设计和运营物流和通信关键基础设施网络的能力。将从历史上代表性不足的工程群体中招募本科生研究助理，参与一项补充性活动，旨在向公众展示项目成果，并向可能不了解该领域的未来学生推广运营工程。研究助理将与一个由学生和志愿者组成的多元化社区进行互动，这些学生和志愿者目前正在与首席研究员进行类似的活动。与标准的节点弧表示相比，新范式显著减少了网络优化问题的整数规划模型中的变量和约束的数量。这反过来又可以导致更快的解决算法。该项目的目标是使用该范式开发(1)针对固有困难的网络优化问题的精确算法，这些算法可以比现有方法在更短的时间内找到可证明的最优解决方案，以及(2)快速找到高质量但不一定最优的解决方案的启发式方法。解决方法将包括专门为新配方导出的切割平面，该项目将测试一个假设，即新模型的结构允许单纯形法的专门实现。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Networks are ubiquitous. Every day our society relies on networks for energy, transportation, and communication. The design and operation of networks is a major concern that cuts across many engineering disciplines. This Boosting Research Ideas for Transformative and Equitable Advances in Engineering (BRITE) Relaunch award leverages a new paradigm for the mathematical modeling of network flow to enable (1) the development of faster and more scalable algorithms for solving large, complex routing problems in transportation and (2) the design of resilient telecommunication networks that have the ability to continue to provide a high level of service even when critical components are damaged. If successful, this project will significantly improve our ability to design and operate critical infrastructure networks for logistics and communications. Undergraduate research assistants from historically underrepresented groups in engineering will be recruited to work on a complementary activity designed to demonstrate outcomes of the project to the general public and to promote Operations Engineering to prospective students who might otherwise not be aware of the field. The research assistants will interact with a diverse community of students and volunteers who are currently engaged with the principal investigator in a similar activity.The new paradigm significantly reduces the number of variables and constraints in integer programming models for network optimization problems compared to the standard node-arc representation. This in turn can lead to faster solution algorithms. The goals of the project are to use the paradigm to develop (1) exact algorithms for inherently difficult network optimization problems that find provably optimal solutions in less time than existing methods, and (2) heuristics that quickly find solutions that are high-quality, but not necessarily optimal. Solution methodology will include cutting planes derived specifically for the new formulations and the project will test a hypothesis that the structure of the new model allows for a specialized implementation of the Simplex Method.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.