Using Graph Convolution Neural Networks for Solving Mixed Integer Linear Programs
Sử dụng mạng tích chập đồ thị để giải các bài toán quy hoạch nguyên hỗn hợp
Abstract
This paper focuses on an exact algorithm for solving NP-hard combinatorial optimization problems which
frequently requires significant specialized knowledge and trial and error, especially, Mixed Integer Linear Programs (MILP). This challenging, tedious process can be automated by learning the algorithms instead. In many practical applications, the same optimization problem is tackled again and again on regular basis, maintaining the same problem structure but varying in the data. This offers an opportunity for learning algorithms that employ the structure of such recurrent problems. With the motivation, we present a network model for learning branch-and-bound variable selection policies based on reinforcement learning, which leverages the natural variable constraint bipartite graph representation of MILPs. The model is trained
going through mimic learning from the strong branching rule. Experimental results claim that using graph convolutional neural networks for solving MILPs can improve for designing branching rules to solve large problems, and outperforms prior models.
References
B. H. Korte, J. Vygen, B. Korte, and J. Vygen, Combinatorial optimization, vol. 1. Springer, 2011.
S. Martello, M. Minoux, C. Ribeiro, and G. Laporte, Surveys in combinatorial optimization. Elsevier, 2011.
N. Vesselinova, R. Steinert, D. F. Perez-Ramirez, and M. Boman, “Learning combinatorial optimization on graphs: A survey with applications to networking,” IEEE Access, vol. 8, pp. 120388–120416, 2020.
Y. Bengio, A. Lodi, and A. Prouvost, “Machine learning for combinatorial optimization: a methodological tourd’horizon,” European Journal of Operational Research, vol. 290, no. 2, pp. 405–421, 2021.
E. B. Khalil, B. Dilkina, G. L. Nemhauser, S. Ahmed, and Y. Shao, “Learning to run heuristics in tree search.,” in Ijcai, pp. 659–666, 2017.
M. Gasse, D. Chételat, N. Ferroni, L. Charlin, and A. Lodi, “Exact combinatorial optimization with graph convolutional neural networks,” Advances in Neural Information Processing Systems, vol. 32, 2019.
Y. Pochet and L. A. Wolsey, Production planning by mixed integer programming, vol. 149. Springer, 2006.
A. M. Alvarez, Q. Louveaux, and L. Wehenkel, “A machine learning-based approximation of strong branching,” INFORMS Journal on Computing, vol. 29, no. 1, pp. 185– 195, 2017.
E. Khalil, P. Le Bodic, L. Song, G. Nemhauser, and B. Dilkina, “Learning to branch in mixed integer programming,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 30, 2016.
D. Selsam, M. Lamm, B. Bunz, P. Liang, L. de Moura, and D. L. Dill, “Learning a sat solver from single-bit supervision,” arXiv preprint arXiv:1802.03685, 2018.
F. K. Karzan, G. L. Nemhauser, and M. W. Savelsbergh, “Information-based branching schemes for binary linear mixed integer problems,” Mathematical Programming Computation, vol. 1, no. 4, pp. 249–293, 2009.
W. Xia and R. Yap, “Learning robust search strategies using a bandit-based approach,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 32, 2018.
A. Balafrej, C. Bessiere, and A. Paparrizou, “Multi-armed bandits for adaptive constraint propagation,” in TwentyFourth International Joint Conference on Artificial Intelligence, 2015.
M.-F. Balcan, T. Dick, T. Sandholm, and E. Vitercik, “Learning to branch,” in International conference on machine learning, pp. 344–353, PMLR, 2018.
J. H. Liang, V. Ganesh, P. Poupart, and K. Czarnecki, “Learning rate based branching heuristic for sat solvers,” in International Conference on Theory and Applications of Satisfiability Testing, pp. 123–140, Springer, 2016.
H. He, H. Daume III, and J. M. Eisner, “Learning to search in branch and bound algorithms,” Advances in neural information processing systems, vol. 27, 2014.
A. Sabharwal, H. Samulowitz, and C. Reddy, “Guiding combinatorial optimization with uct,” in International conference on integration of artificial intelligence (AI) and operations research (OR) techniques in constraint programming, pp. 356–361, Springer, 2012.
J. Song, R. Lanka, A. Zhao, A. Bhatnagar, Y. Yue, and M. Ono, “Learning to search via retrospective imitation,” arXiv preprint arXiv:1804.00846, 2018.
Y. Li, “Deep reinforcement learning: An overview,” arXiv preprint arXiv:1701.07274, 2017.
E. Balas and A. Ho, Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study, pp. 37–60. Berlin, Heidelberg: Springer Berlin Heidelberg, 1980.
C. Hansknecht, I. Joormann, and S. Stiller, “Cuts, primal heuristics, and learning to branch for the timedependent traveling salesman problem,” arXiv preprint arXiv:1805.01415, 2018.