Reinforcement Learning for Integer Programming: Learning to Cut

2019-06-11 · ICML 2020 1 · Yunhao Tang, Shipra Agrawal, Yuri Faenza

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.

📄 PDF Abstract BibTeX arXiv:1906.04859

Code (0)

등록된 구현이 없습니다.

Tasks

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)Scheduling

NICE: Robust Scheduling through Reinforcement Learning-Guided Integer Programming

2021-09-24 · Luke Kenworthy, Siddharth Nayak, Christopher Chin, Hamsa Balakrishnan

Integer programs provide a powerful abstraction for representing a wide range of real-world scheduling problems. Despite their ability to model general scheduling problems, solving large-scale integer programs (IP) remai…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)Scheduling

General Method for Solving Four Types of SAT Problems

2023-12-27 · Anqi Li, Congying Han, Tiande Guo, Haoran Li 외

Existing methods provide varying algorithms for different types of Boolean satisfiability problems (SAT), lacking a general solution framework. Accordingly, this study proposes a unified framework DCSAT based on integer …

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Machine Learning Algorithms for Improving Exact Classical Solvers in Mixed Integer Continuous Optimization

2025-08-09 · Morteza Kimiaei, Vyacheslav Kungurtsev, Brian Olimba arxiv

Integer and mixed-integer nonlinear programming (INLP, MINLP) are central to logistics, energy, and scheduling, but remain computationally challenging. This survey examines how machine learning and reinforcement learning…

Reinforcement Learning

DeepFreight: Integrating Deep Reinforcement Learning and Mixed Integer Programming for Multi-transfer Truck Freight Delivery

2021-03-05 · Jiayu Chen, Abhishek K. Umrawal, Tian Lan, Vaneet Aggarwal

With the freight delivery demands and shipping costs increasing rapidly, intelligent control of fleets to enable efficient and cost-conscious solutions becomes an important problem. In this paper, we propose DeepFreight,…

Deep Reinforcement Learning Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning+1

Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates

2023-07-17 · Kyle Mana, Fernando Acero, Stephen Mak, Parisa Zehtabi 외

Discrete optimization belongs to the set of $\mathcal{NP}$-hard problems, spanning fields such as mixed-integer programming and combinatorial optimization. A current standard approach to solving convex discrete optimizat…

Combinatorial Optimization Management reinforcement-learning Reinforcement Learning+1