Autoregressive RL Approach for Mixed-Integer Linear Programs

Paul Mingzheng Tang, Hoong Chuin Lau, Moses Hong De LeeLION19 2025 · OpenReview

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...

Figure