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

图的组合优化问题产生于许多应用领域，如计划、调度和电子设计自动化(EDA)，是NP-Hard问题，近年来引起了理论界、算法设计界和机器学习界的极大兴趣。例如，许多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.