CAREER: Machine Learning for Discrete Optimization

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

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.