Reinforcement Learning for Integer Programming: Learning to Cut

Abstract

Integer programming (IP) is a general optimization framework widely applicable to a variety of unstructured and structured problems arising in, e.g., scheduling, production planning, and graph optimization. As IP models many provably hard to solve problems, modern IP solvers rely on many heuristics. These heuristics are usually human-designed, and naturally prone to suboptimality. The goal of this work is to show that the performance of those solvers 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 the trained RL agent significantly outperforms human-designed heuristics, and effectively generalizes to 10X larger instances and across IP problem classes. The trained agent is also demonstrated to benefit the popular downstream application of cutting plane methods in Branch-and-Cut algorithm, which is the backbone of state-of-the-art commercial IP solvers.

Accepted at International Conference on Machine Learning (ICML) 2020

References in corpus (6)

• Sequence to Sequence Learning with Neural Networks
• Learning Combinatorial Optimization Algorithms over Graphs
• Evolution Strategies as a Scalable Alternative to Reinforcement Learning
• IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures
• Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
• Learning to Branch

Cited by in corpus (9)

• Deep Reinforcement Learning for Electric Vehicle Routing Problem with Time Windows
• Generative AI and Process Systems Engineering: The Next Frontier
• Solving Mixed Integer Programs Using Neural Networks
• Branch and Bound in Mixed Integer Linear Programming Problems: A Survey of Techniques and Trends
• Machine Learning for Cutting Planes in Integer Programming: A Survey
• Accelerating Primal Solution Findings for Mixed Integer Programs Based on Solution Prediction
• Fusion 360 Gallery: A Dataset and Environment for Programmatic CAD Construction from Human Design Sequences
• Smart Feasibility Pump: Reinforcement Learning for (Mixed) Integer Programming
• Benders Cut Classification via Support Vector Machines for Solving Two-stage Stochastic Programs