Learning Branching Policies for MILPs with Proximal Policy Optimization
Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (29) · 24379-24387
DOI: 10.1609/aaai.v40i29.39619 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Abdelouahed Ben Mhamed und 2 weiteren Autor:innen.
Abstract (Originalsprache)
Branch-and-Bound (B&B) is the dominant exact solution method for Mixed Integer Linear Programs (MILP), yet its exponential time complexity poses significant challenges for large-scale instances. The growing capabilities of machine learning have spurred efforts to improve B&B by learning data-driven branching policies. However, most existing approaches rely on Imitation Learning (IL), which tends to overfit to expert demonstrations and struggles to generalize to structurally diverse or unseen instances. In this work, we propose Tree-Gate Proximal Policy Optimization (TGPPO), a novel framework that employs Proximal Policy Optimization (PPO), a Reinforcement Learning (RL) algorithm, to train a branching policy aimed at improving generalization across heterogeneous MILP instances. Our approach builds on a parameterized state space representation that dynamically captures the evolving context of the search tree. Empirical evaluations show that TGPPO often outperforms existing learning-based policies in terms of reducing the number of nodes explored and improving p-Primal-Dual Integrals (PDI), particularly in out-of-distribution instances. These results highlight the potential of RL to develop robust and adaptable branching strategies for MILP solvers.
Zitieren
APA
Mhamed, A. B., Idrissi, A. K., & Seghrouchni, A. (2026). Learning Branching Policies for MILPs with Proximal Policy Optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 40(29), 24379-24387. https://doi.org/10.1609/aaai.v40i29.39619
Vancouver
Mhamed AB, Idrissi AK, Seghrouchni A. Learning Branching Policies for MILPs with Proximal Policy Optimization. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(29):24379-24387. doi:10.1609/aaai.v40i29.39619
BibTeX
@article{Mhamed2026,
author = {Mhamed, Abdelouahed Ben and Idrissi, Assia Kamal and Seghrouchni, Amal},
title = {Learning Branching Policies for MILPs with Proximal Policy Optimization},
journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
year = {2026},
volume = {40},
number = {29},
pages = {24379--24387},
doi = {10.1609/aaai.v40i29.39619}
}
EUVIMED