Accelerating MILP Solving through Bipartite GNN-Based Embeddings

The Branch and Bound (BB) algorithm is a fundamental method for solving mixed integer linear programs (MILPs), in which the choice of branching variables critically affects the size of the search tree and the overall solving time. For variable selection in BB, GNN-based methods have garnered significant attention due to their ability to extract informative representations from the graph structure of MILPs. However, typical GNN-based methods primarily focus on refining and learning useful features from graphs while overlooking the impact of embedding dimension. Moreover, empirical results indicate that the choice of embedding dimension also has a significant impact on the efficiency of variable selection in MILP solving. To address these challenges, we introduce a new bipartite graph neural network framework, GIN-BGE, for jointly addressing embedding dimension evaluation and variable selection. We represent the MILP problem state with a bipartite graph and associated neighborhood graphs, leveraging an entropy-based objective to adaptively determine the embedding dimension for different MILP instances. Our model further employs a bipartite graph isomorphic network to learn expressive representations.We compare GIN-BGE with existing baselines on a series of NP-hard benchmarks, and empirical experiments demonstrate that GIN-BGE achieves better performance compared with the state-of-the-art methods on a series of metrics. Furthermore, GIN-BGE shows strong potential for extension to larger-size and heterogeneous MILP instances, highlighting its scalability and versatility across diverse optimization challenges.