CAREER: Machine Learning for Discrete Optimization

Discrete optimization algorithms are used to solve complex problems, such as finding the best routes for delivery trucks or planning global airline schedules. Oftentimes, these problems are extremely challenging to solve, requiring significant computational resources and running time. This project aims to use machine learning (ML) to solve these complex problems more efficiently. After all, the problems that, for example, a shipping company must solve to route its trucks will change daily, but not drastically: although demand and traffic will vary, the road network will remain the same. This means that there is likely underlying structure that can be uncovered with the help of ML to optimize algorithm runtime on future problems. This project aims to explore this new frontier of algorithm design where ML can be used to improve the performance of existing discrete optimization algorithms, help practitioners select among different algorithms, and--one day--design entirely new algorithms. In addition to its main technical objectives, this project extends its impact through community engagement and education. This includes expanding the "Learning Theory Alliance," a mentorship program designed to support and develop the ML theory community. The project also includes plans to train graduate students, broaden participation in ML theory research, and integrate the research into new courses at the undergraduate and graduate levels. This project investigates how ML can be integrated into algorithm design from a variety of different perspectives, including (1) Algorithm selection: How can we use ML to choose which algorithm to employ to solve a computational problem? (2) Algorithm configuration: Many practical algorithms, such as integer programming solvers, come with hundreds of tunable parameters that are notoriously difficult to tune by hand. How can we automate algorithm configuration using ML? (3) Algorithm discovery: The long-term goal of this research direction is to identify new algorithms using ML that have never previously been analyzed. Employing ML for discrete optimization is challenging because combinatorial algorithms are highly sensitive, and minor adjustments can result in significant changes in runtime or solution quality. These challenges pose a unique opportunity for the research in this project to provide theoretically-backed guidance for aligning ML approaches to the algorithmic tasks at hand, enabling us to solve extremely complex combinatorial problems. 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.