Yunhao Tang: Reinforcement Learning for Integer Programming: Learning to Cut

Deep Learning and Combinatorial Optimization 2021 “Reinforcement Learning for Integer Programming: Learning to Cut“ Yunhao Tang - Columbia University Abstract: Integer programming is a general optimization framework with a wide variety of applications. As Integer Programs (IPs) model many provably hard-to-solve problems, modern IP solvers rely on heuristics. These heuristics are often human-designed, and tuned over time using experience and data. The goal of this work is to show that the performance of those heuristics can be greatly enhanced using reinforcement learning (RL). In particular, we investigate a specific methodology for solving IPs, known as the cutting plane method. This method is employed as a subroutine by all modern IP solvers. We present a deep RL formulation, network architecture, and algorithms for intelligent adaptive selection of cutting planes (aka cuts). Across a wide range of IP tasks, we show that our trained RL agent significantly outperforms human-designed heuristics. The trained