BRITE Relaunch: Compact Network Flows for Critical Infrastructure Engineering

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.