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

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

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.