Learning to Pivot as a Smart Expert
Proceedings of the AAAI Conference on Artificial Intelligence · 24.03.2024 · 38 (8) · 8073-8081
DOI: 10.1609/aaai.v38i8.28646 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 24.03.2024. Verfasst von Tianhao Liu und 3 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref).
Abstract (Originalsprache)
Linear programming has been practically solved mainly by simplex and interior point methods. Compared with the weakly polynomial complexity obtained by the interior point methods, the existence of strongly polynomial bounds for the length of the pivot path generated by the simplex methods remains a mystery. In this paper, we propose two novel pivot experts that leverage both global and local information of the linear programming instances for the primal simplex method and show their excellent performance numerically. The experts can be regarded as a benchmark to evaluate the performance of classical pivot rules, although they are hard to directly implement. To tackle this challenge, we employ a graph convolutional neural network model, trained via imitation learning, to mimic the behavior of the pivot expert. Our pivot rule, learned empirically, displays a significant advantage over conventional methods in various linear programming problems, as demonstrated through a series of rigorous experiments.
Zitieren
APA
Liu, T., Pu, S., Ge, D., & Ye, Y. (2024). Learning to Pivot as a Smart Expert. Proceedings of the AAAI Conference on Artificial Intelligence, 38(8), 8073-8081. https://doi.org/10.1609/aaai.v38i8.28646
Vancouver
Liu T, Pu S, Ge D, Ye Y. Learning to Pivot as a Smart Expert. Proceedings of the AAAI Conference on Artificial Intelligence. 2024;38(8):8073-8081. doi:10.1609/aaai.v38i8.28646
BibTeX
@article{Liu2024,
author = {Liu, Tianhao and Pu, Shanwen and Ge, Dongdong and Ye, Yinyu},
title = {Learning to Pivot as a Smart Expert},
journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
year = {2024},
volume = {38},
number = {8},
pages = {8073--8081},
doi = {10.1609/aaai.v38i8.28646}
}
EUVIMED