GNN-guided approach to enhancing mixed-integer linear programming solvers

Mixed integer linear programming (MILP) is a key technique for solving real-world combinatorial optimization problems such as production planning, supply chain scheduling, and resource allocation, and it falls into the category of NP-hard problems. Traditional solution methods, including branch-and-bound and cutting-plane algorithms, serve as the core of commercial solvers but suffer from insufficient parallel computing capabilities. When dealing with large-scale industrial-level problems, their solution efficiency can hardly meet practical requirements.

Recent ML-based MILP paradigms show progress in approximation, yet face two bottlenecks: most neural networks underutilize constraint coefficients (edge features) in MILP bipartite graphs, limiting structure extraction; post-search algorithms lack adaptability to different instances, leading to poor generalization and tedious tuning. Thus, an integrated framework addressing both graph representation and search rigidity is urgent to boost MILP efficiency, solution quality, and generalization.

To tackle these challenges, this paper proposed the SHARP framework (SinkHorn-regularized edge Attention with adaptive Regret-based search Procedure), with two core innovations: Sinkhorn-normalized Edge-enhanced Graph Attention Network (SKEGAT). Aiming at the problem that the existing Edge-enhanced Graph Attention Network (EGAT) required high-cost matrix expansion due to edge feature matrix dimension mismatch when processing MILP bipartite graphs, the SHARP framework designed SKEGAT. This network innovatively introduced the Sinkhorn algorithm to realize bi-stochastic normalization directly on the original MILP bipartite graph edge matrix, avoiding the computational and storage overhead caused by matrix expansion. Meanwhile, a multi-layer semi-convolutional structure was constructed to enhance the model's ability to represent the complex structure of MILP.

To alleviate the exponential time complexity bottleneck of MILP solving, the variable marginal probabilities learned by the neural network were first used to pre-fix the values of some variables through a confidence threshold, thereby reducing the search space. On this basis, an adaptive regret mechanism was introduced, and a fault-tolerance parameter was set to allow a certain proportion of variables to deviate from the optimal solution values, dynamically adjusting the variable assignment strategy. This not only expanded the search space to avoid suboptimal or infeasible solutions but also adaptively adjusted the deviation degree from the initial greedy solution according to the problem scale, improving the generalization ability.

Evaluated on Combinatorial Auction (CA) and Item Placement (IP) datasets, the SHARP framework demonstrates significant advantages across multiple metrics. In terms of Primal Integral, a measure of both solution quality and speed, SHARP outperforms the traditional solvers Gurobi and SCIP by 24.88% and 5.86% respectively, and surpasses existing state-of-the-art machine learning methods by 17.19%. Throughout the solving process, SHARP consistently maintains the lowest Primal Gap curve, indicating faster convergence to higher-quality solutions. Ablation studies confirm that the proposed SKEGAT module is the key driver of this performance, significantly outperforming standard GCN and GAT variants. Furthermore, SHARP enhances the capabilities of traditional solvers by breaking through computational bottlenecks and, when compared directly against the SOTA method ConPaS, it finds superior solutions more rapidly.

By integrating the edge-enhanced graph attention network with Sinkhorn normalization, the SHARP framework effectively addresses the problem of insufficient utilization of edge features in the MILP bipartite graph and enhances the ability to represent problems. At the same time, the design of the adaptive regret-based greedy search algorithm improves the solution quality and the framework's generalization ability. Experimental results confirm that, on multiple standard datasets, the framework achieves significant performance improvements compared with traditional solvers and existing state-of-the-art machine learning methods, providing an efficient solution for solving large-scale MILP problems.

However, SHARP lacks generalization in large, diverse industrial applications. Future work will:reduce computing resource dependence via model lightweighting and adaptive parameter optimization; extend SHARP to supply chain optimization and production scheduling to test and expand its applications.