RI: Medium: Learning to Search: Provable Guarantees and Applications

人工智能和优化被广泛应用于科学和商业应用中。许多人工智能和优化反过来又由分支和定界等搜索技术提供支持。这些搜索技术用于智能地探索问题的大量可能解决方案，以便为手头的问题提出最佳解决方案。不幸的是，在最坏的情况下，它们的运行时间可能是指数级的，并且很多精力都花在设计可调整的搜索策略上，这可能会对运行时、解决方案质量或两者都有很大影响。调整这些策略通常由专家手动完成。最近已经有一些关于自动调整搜索变体的工作，但这些方法并没有提供性能保证，而且一般来说，对于人们可能希望实现什么样的保证，理论上几乎没有理解。这个项目的目标是提供新的机器学习方法，为定制搜索技术和自动确定任何给定问题域的近乎最优的搜索策略提供强有力的可证明保证。该项目旨在为其程序和技术提供正式保证，以解决比目前可能出现的更大、更复杂的问题。这项研究中开发的算法和模型将由优化问题驱动，并应用于包括肾脏交换和组合拍卖设计在内的重要现实应用的核心问题。在这些领域，改进的优化程序会产生重大影响。本项目的具体目标包括：(1)通过机器学习开发有效的树搜索策略(包括分枝定界方法)，这些策略具有广泛的适用性、可扩展性和强大的可证明性保证。(2)同时学习分支和节点选择策略，并学习A*搜索等知情搜索技术的允许启发式算法。(3)应用为解决两个重要应用领域的关键挑战而开发的算法：肾脏交换和自动化机制设计。(4)学习如何在决策树学习的背景下进行分支，这是一种重要的机器学习范式，特别是在设计用于自上而下的决策树归纳的启发式规则时。该项目将影响人工智能、优化、机器学习、计算理论，以及许多需要反复解决给定领域的困难优化问题的领域。这包括肾脏交换和机制设计，这可能会对社会和商业产生广泛影响。除了就与该项目相关的主题向研究生和本科生提供建议外，研究进展将被整合到卡内基-梅隆大学的几门课程的课程中，课程材料将在全球范围内提供。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

AI and optimization are used in a wide range of scientific and business applications. Much of AI and optimization in turn are powered by search techniques such as branch and bound. These search techniques are used to intelligently explore a large number of possible solutions to a problem in order to come up with the best solution for the problem at hand. Unfortunately, in the worst case, their running time can be exponential, and much effort goes into the design of adjustable search strategies that can have a large effect on runtime, solution quality, or both. Tuning these strategies is typically done manually by experts. Recently there has been work on automated tuning of some variations of search, but these methods have not come with performance guarantees, and in general there is little theoretical understanding of what kinds of guarantees one might hope to achieve. The goal of this project is to provide new machine learning approaches with strong provable guarantees for customizing search techniques and automatically determining a nearly optimal search strategy for any given problem domain. This project aims to provide formal guarantees for its procedures as well as techniques that scale up to larger and more complex problems than currently possible. The algorithms and models developed in this research will be driven by, and applied to, optimization problems at the core of important real-world applications including kidney exchange and combinatorial auction design. These are domains where improved optimization procedures have significant impact. Specific goals in this project include: (1) Developing effective tree search strategies (including branch-and-bound methods) via machine learning that are widely applicable, scalable, and have strong provable guarantees. (2) Learning branching and node selection strategies together, and learning admissible heuristics for informed search techniques including A* search. (3) Applying algorithms developed to solve key challenges in two important application domains: Kidney Exchange and Automated Mechanism Design. (4) Learning how to branch in the context of decision-tree learning, an important machine learning paradigm, and in particular in the design of heuristics for top-down decision-tree induction. The project will impact artificial intelligence, optimization, machine learning, theory of computing, as well as many areas that require repeatedly solving hard optimization problems from a given domain. This includes kidney exchange and mechanism design which can have a broad impact across society and commerce. In addition to advising both graduate and undergraduate students on topics connected to this project, research progress will be integrated in the curricula of several courses at Carnegie-Mellon University and course materials will be made available on the web worldwide.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.