A machine-learning method called SHSP reported a 54% average reduction in solution gap compared with one-shot prediction baselines. The gap was measured as the absolute difference between a solver's objective value and a best-known solution, written as |OBJ-BKS|. The 54% is the abstract's reported average; no confidence interval or inferential uncertainty estimate was reported.
SHSP combines hierarchical conditional decoding guided by a variable-coupling graph, mask-and-repair, and structure-aware variable fixing. The study used that design to form ND+SHSP, PaS+SHSP and Apollo+SHSP by replacing the original predictor and fixing strategy in each framework.
Where the reported gains appeared
With PaS, the reported absolute-primal-gap reductions were 99.7% on Combinatorial Auctions (CA) instances, 38.1% on Workload Appointment (WA), 24.3% on Item Placement (IP), and 42.1% on Set Covering (SC).
The Apollo-integrated result reported no gap on CA, corresponding to a 100.0% reduction. Reported reductions were 92.9% on IP, 28.6% on WA and 41.7% on SC.
The ND comparison reported absolute-primal-gap reductions of 94.4% on IP, 67.0% on CA and 19.2% on WA. Across the PaS, Apollo and ND comparisons, the paper presents the figures as reductions against the corresponding prediction baselines.
A separate SCIP comparison reported four improvement figures for the ND+SHSP row: 70.57%, 67.01%, 56.68% and 1.17%.
The method's moving parts
Component comparisons pointed in the same direction. The ablation reported that coupling masking with repair consistently produced the best results across datasets and prediction frameworks. A hierarchical predictor was reported to provide higher solution quality for PaS and Apollo than the original GNN predictor, while structure-aware fixing outperformed normal fixing in those two frameworks.
Each main benchmark used 240 training instances, 60 validation instances and 100 testing instances. The main solver comparison used the best objective value reached within a 1,000-second limit for each test instance. The reference best-known solution came from a single-threaded Gurobi run allowed 3,600 seconds, and the gap formula used |OBJ-BKS|. That reference is time-limited and does not necessarily equal the exact optimum.
The added computation was reported as modest relative to the solver budget. Neural-network inference took less than 0.2 seconds across benchmarks. Graph construction ranged from 0.26 to 15.23 seconds, and that work was included in the 1,000-second budget.
Strong results, narrow evidence
On combinatorial-auction instances, a SHSP variant reportedly surpassed full-budget Gurobi's solution quality within a substantially smaller time budget. The comparison is tied to those instances and budgets, so it does not by itself establish the same result elsewhere.
The study also tested an IIS subset of MIPLIB. It contained 11 instances, including 8 for training and 3 for testing, and the results tables reported that SHSP methods outperformed their corresponding baselines. Because the subset is small and selected rather than representative of all MIPLIB, it provides only a limited check of broader performance.
Those boundaries matter when reading the 54% figure. The evaluation used selected benchmark datasets and a small IIS subset rather than broad heterogeneous coverage. The analysis reports no confidence intervals, per-instance uncertainty summaries or formal significance tests, so the averages do not quantify how much results may vary from instance to instance. The findings support a computational comparison under specified settings, not a guarantee of the same gains under other time budgets, solver configurations or MILP classes.
The manuscript is an arXiv preprint dated 26 Aug 2026. The paper states that its code is available at https://github.com/lamda-bbo/SHSP.
Paper data and sources
Original title: SHSP: Structure-Aware Hierarchical Solution Prediction for Mixed-Integer Linear Programming
Authors: Zherong Zhang, Guanlin Li, Chengrui Gao et al.
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: Not available
Original paper · Full text