CAREER: Machine Learning for Discrete Optimization

职业：用于离散优化的机器学习

• 批准号: 2338226
• 负责人: Ellen Vitercik
• 金额: $ 55.88万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-03-15 至 2029-02-28
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2338226&HistoricalAwards=false
• 关键词: CAREER; Machine; Learning; 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.

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