M.Sc Thesis


M.Sc StudentBen-David Avrech
SubjectCombinatorial Optimization with Graph Reinforcement Learning
DepartmentDepartment of Electrical and Computer Engineering
Supervisors PROF. Shie Mannor
ASSOCIATE PROF. Tamir Hazan


Abstract

Combinatorial optimization problems are abundant in machine learning applications. In this work we show how graph neural networks can exploit the structure of combinatorial optimization problems to learn their solutions.


We begin by showing how graph neural networks with evolution strategy search in the neural network computational graphs can be used in deep neural network accelerators for automated memory mapping, instead of manual heuristic approaches. We train and validate our approach directly on the Intel NNP-I chip for inference and show that our method outperforms policy-gradient, evolutionary search and dynamic programming baselines on BERT, ResNet-101 and ResNet-50. We additionally achieve 28-78\% speed-up compared to the native NNP-I compiler on all three workloads. The proposed approach does not sacrifice model performance for speed, agnostic to the hardware architecture and offers risk-less machine learning method for hardware companies to gain automatic improvement for their native compilers. 


In a different domain, we explore how to use reinforcement learning and graph neural networks to solve generic combinatorial problems by learning to select cutting-planes in SCIP (Solving Constraint Integer Programs) to minimize its primal-dual gap in shorter time. We propose evaluation metric for cut selection algorithms, and suggest RL formulation for tuning SCIP cut selection parameters which optimizes this metric. We conduct extensive experiments in aggressive separation setting showing that our agent improves over SCIP default cut selection by ~14%. In addition, our agent performs on par or better than one-time exhaustive tuning done on a validation set. We further analyze the effect of our cut selection policy on the Branch-and-Cut algorithm, and draw directions for complementary future work that will make the aggressive use of cutting planes and RL-based cut selection beneficial for SCIP. A modified SCIP version supporting distributed RL environment for cut selection is publicly available at https://github.com/avrech/learning2cut.git.