Autoregressive RL Approach for Mixed-Integer Linear Programs
Lists
Only you see this
Abstract
Mixed-Integer Linear Programming (MILP) is a widely used method for modeling combinatorial optimization problems. Due to the NP-hard nature of many of these problems, efforts using machine-learning (ML) have been proposed to generate heuristics to speed up solvers, while maintaining optimality. While there is prior work on using graph neural networks (GNNs) to produce high-quality partial solutions, the methods used are non-auto-regressive which model the prediction of variables as conditionally independent due to concerns with inference speed. In this paper, we propose a novel auto-regressive reinforcement learning (RL) framework using GNNs which directly optimize for optimality and inference speed. Experimental results show our RL method outperforms the benchmark Predict-And-Search (PNS) method on harder real-world problems (55.7% speedup) with time limits and matches performance on easier problems.
BibTeX
@inproceedings{tang2025autoregressive,
author = {Paul Mingzheng Tang and Hoong Chuin Lau and Moses Hong De Lee},
title = {{Autoregressive RL Approach for Mixed-Integer Linear Programs}},
booktitle = {LION19},
year = {2025},
url = {https://openreview.net/forum?id=9rMX0VTMsD},
}Loading related content...