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.
