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.