Learning to select cutting planes in mixed integer linear programming solving

Cutting planes (cuts) are crucial for solving Mixed Integer Linear Programming (MILP) problems. Advanced MILP solvers typically rely on manually designed heuristic algorithms for cut selection, which require extensive expert knowledge and cannot be generalized to MILP problems with varying instance sizes across different domains. Therefore, learning-based methods for cut selection are considered a promising direction. State-of-the-art learning-based methods formulate cut selection as a sequence-to-sequence problem, easily handled by sequence models. However, the existing sequence models need help with the following issues: (1) the model only captures cut information while neglecting the Linear Programming (LP) relaxation; (2) the sequence model utilizes positional information of the input sequence, which may influence cut selection. To address these challenges, we design a novel model HGTSM for better cut selection. We encode MILP problem state as a heterogeneous tripartite graph, utilizing heterogeneous graph networks to fully capture the underlying structure of MILP problems. Simultaneously, we propose a novel sequence model whose architecture is tailored to handle inputs in different orders. Experimental results demonstrate that our model outperforms heuristic methods and learning-based baselines on multiple challenging MILP datasets. The code of HGTSM can be found at https://github.com/aqi007/Learn2Cut-HGTSM.