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

Purdue University, West Lafayette IN

Investigators

Abstract

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.