CAREER: Machine Learning for Discrete Optimization

离散优化算法用于解决复杂问题，例如为送货卡车寻找最佳路线或规划全球航空公司时刻表。通常，这些问题的解决极具挑战性，需要大量的计算资源和运行时间。该项目旨在使用机器学习(ML)来更有效地解决这些复杂问题。毕竟，例如，一家航运公司必须解决的卡车路线问题每天都会发生变化，但不会有很大变化：尽管需求和交通会有所不同，但公路网将保持不变。这意味着在ML的帮助下可以发现可能的底层结构，以优化针对未来问题的算法运行时。该项目旨在探索算法设计的这一新前沿，其中ML可用于提高现有离散优化算法的性能，帮助实践者在不同的算法中进行选择，并有朝一日设计出全新的算法。除了其主要技术目标外，该项目还通过社区参与和教育扩大其影响。这包括扩大“学习理论联盟”，这是一个旨在支持和发展ML理论社区的导师计划。该项目还包括计划培养研究生，扩大对ML理论研究的参与，并将研究整合到本科生和研究生水平的新课程中。本项目从各种不同的角度研究如何将ML整合到算法设计中，包括(1)算法选择：我们如何使用ML来选择使用哪个算法来解决计算问题？(2)算法配置：许多实用算法，如整数规划求解器，都带有数百个可调参数，众所周知，这些参数很难手动调整。如何使用ML自动配置算法？(3)算法发现：这个研究方向的长期目标是使用ML识别以前从未分析过的新算法。使用ML进行离散优化是具有挑战性的，因为组合算法是高度敏感的，而微小的调整可能会导致运行时或解的质量发生重大变化。这些挑战为这个项目的研究提供了一个独特的机会，为使ML方法与手头的算法任务保持一致提供理论支持的指导，使我们能够解决极其复杂的组合问题。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.