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

University Of Utah, Salt Lake City UT

Investigators

Abstract

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.