CAREER: OneSense: One-Rule-for-All Combinatorial Boolean Synthesis via Reinforcement Learning

图上的组合优化问题产生于许多应用领域，如规划，调度和电子设计自动化（EDA），是NP-难的，最近引起了理论，算法设计和机器学习社区的极大兴趣。例如，许多EDA问题（例如布尔优化）都是组合优化问题，不太可能通过多项式时间算法来解决。在实践中，这些问题可以使用可扩展的优化算法与近似和特定于领域的算法来解决，这些算法主要是通过大量的手工工程工作与强大的领域知识来开发的。然而，由于技术知识的高障碍、耗时的手工工程和几种误导性的设计策略，开发这种算法和相关算法的最新进展显着放缓。该项目旨在采用强化学习和神经网络来实现图形上的自学习高性能算法和算法，这些算法和算法可以在没有人类监督和领域知识的情况下优于现有的手工制作方法。这将可以推广到自主学习和发现新的基于图的组合优化算法在广泛的应用领域，没有任何人的指导。该项目将制作开源软件和会议教程，以促进多学科社区中的技术转移和富有成效的产学互动。该项目开发了OneSense系统，这是一个图学习驱动的强化学习框架，用于探索图上的自学习新算法和算法，特别关注基于图的大规模布尔优化问题。该项目的核心包括新颖的强化学习公式和神经架构，以及特定领域的在线图采样技术，以实现自学习高性能图优化算法。具有各种奖励公式和新型训练方法和算法的强化代理将能够有效地学习新型组合优化启发式方法，并具有广泛的性能定制。OneSense系统将与开源的端到端EDA设计空间探索系统集成，这将允许在布尔优化中对图形进行有效的探索和部署自学优化算法。此外，还将发布OneSense强化学习框架，用于在其他研究领域探索自学习的图优化算法，并将其用作教育平台。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

Combinatorial optimization problems over graphs arising from numerous application domains, such as planning, scheduling, and electronic design automation (EDA), are NP-hard, and have recently attracted considerable interest from the theory, algorithm design, and machine learning communities. For example, many of the EDA problems such as Boolean optimization are combinatorial optimization problems, which are unlikely to be solved by polynomial-time algorithms. In practice, those problems can be solved using scalable optimization algorithms with approximations and domain-specific heuristics, which are mostly developed by extensive hand-engineering efforts with strong domain knowledge. However, recent progress in developing such algorithms and associated heuristics is slowing down significantly due to the high barrier of technical knowledge, time-consuming hand-engineering, and several misleading designing strategies. This project aims to employ reinforcement learning and neural networks to enable self-learning high-performance algorithms and heuristics over graphs, which can outperform existing hand-crafted approaches without human supervision and domain knowledge. This will can be generalized to autonomously learn and discover novel graph-based combinatorial optimization heuristics at a wide range of application domains without any human guidance. This project will produce open-source software and conference tutorials to facilitate technology transfers and fruitful industry-academia interactions in a multidisciplinary community.This project develops the OneSense system, a graph learning driven reinforcement learning framework for exploring self-learning novel algorithms and heuristics over graphs, with special focuses on graph-based large-scale Boolean optimization problems. The core of the project includes novel reinforcement learning formulations and neural architecture with domain-specific online graph sampling techniques to enable self-learning high-performance graph optimization heuristics. The reinforcement agent with the various reward formulations and novel training methodologies and algorithms will enable effectively learning novel combinatorial optimization heuristics with a wide range of performance customization. OneSense system will be integrated with an open-source end-to-end EDA design space exploration system, which will allow productive exploration and deployment of self-learned optimization heuristics over graphs in Boolean optimization. Moreover, the OneSense reinforcement learning framework will be released to allow exploring self-learned graph optimization algorithms in other research domains and be used as an educational platform.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.