Using Graph Convolution Neural Networks for Solving Mixed Integer Linear Programs
Binh Nguyen Thi My, Hoang Long Dao, Van Thien Nguyen, Hong Thai Pham · Journal on Information Technologies & Communications · 2022
This paper focuses on an exact algorithm for solving NP-hard combinatorial optimization problems whichfrequently 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 trainedgoing 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.