Learning to Cut via Hierarchical Sequence/Set Model for Efficient Mixed-Integer Programming
IEEE Transactions on Pattern Analysis and Machine Intelligence · 2024-12 · 46 (12) · 9697-9713
DOI: 10.1109/tpami.2024.3432716 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024-12. Verfasst von Jie Wang und 9 weiteren Autor:innen. Die Arbeit wurde bisher 13-mal zitiert (Crossref) und nennt 92 Literaturangaben. Gefördert von: National Key R&D Program of China, National Nature Science Foundations of China.
Abstract (Originalsprache)
Cutting planes (cuts) play an important role in solving mixed-integer linear programs (MILPs), which formulate many important real-world applications. Cut selection heavily depends on (P1) which cuts to prefer and (P2) how many cuts to select. Although modern MILP solvers tackle (P1)-(P2) by human-designed heuristics, machine learning carries the potential to learn more effective heuristics. However, many existing learning-based methods learn which cuts to prefer, neglecting the importance of learning how many cuts to select. Moreover, we observe that (P3) what order of selected cuts to prefer significantly impacts the efficiency of MILP solvers as well. To address these challenges, we propose a novel hierarchical sequence/set model (HEM) to learn cut selection policies. Specifically, HEM is a bi-level model: (1) a higher-level module that learns how many cuts to select, (2) and a lower-level module-that formulates the cut selection as a sequence/set to sequence learning problem-to learn policies selecting an ordered subset with the cardinality determined by the higher-level module. To the best of our knowledge, HEM is the first data-driven methodology that well tackles (P1)-(P3) simultaneously. Experiments demonstrate that HEM significantly improves the efficiency of solving MILPs on eleven challenging MILP benchmarks, including two Huawei's real problems.
Förderung
- National Key R&D Program of China
- National Nature Science Foundations of China
Zitieren
APA
Wang, J., Wang, Z., Li, X., Kuang, Y., Shi, Z., Zhu, F., Yuan, M., Zeng, J., Zhang, Y., & Wu, F. (2024). Learning to Cut via Hierarchical Sequence/Set Model for Efficient Mixed-Integer Programming. IEEE Transactions on Pattern Analysis and Machine Intelligence, 46(12), 9697-9713. https://doi.org/10.1109/tpami.2024.3432716
Vancouver
Wang J, Wang Z, Li X, Kuang Y, Shi Z, Zhu F, et al. Learning to Cut via Hierarchical Sequence/Set Model for Efficient Mixed-Integer Programming. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2024;46(12):9697-9713. doi:10.1109/tpami.2024.3432716
BibTeX
@article{Wang2024,
author = {Wang, Jie and Wang, Zhihai and Li, Xijun and Kuang, Yufei and Shi, Zhihao and Zhu, Fangzhou and Yuan, Mingxuan and Zeng, Jia and Zhang, Yongdong and Wu, Feng},
title = {Learning to Cut via Hierarchical Sequence/Set Model for Efficient Mixed-Integer Programming},
journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
year = {2024},
volume = {46},
number = {12},
pages = {9697--9713},
doi = {10.1109/tpami.2024.3432716}
}
EUVIMED