SHSP: Structure-Aware Hierarchical Solution Prediction for Mixed-Integer Linear Programming

Zherong Zhang; Guanlin Li; Chengrui Gao; Haopu Shang; Ke Xue; Jixiang Lu; Weiyong Yang; Chao Qian

Source-linked AI summary

SHSP: Structure-Aware Hierarchical Solution Prediction for Mixed-Integer Linear Programming

Zherong Zhang, Guanlin Li, Chengrui Gao, Haopu Shang, Ke Xue, Jixiang Lu, Weiyong Yang, Chao Qian

arXiv:2608.25282v1Aug 26, 2026cs.LGcs.AI

TL;DR

Large and highly constrained MILPs remain expensive, while one-shot predictors model variable dependencies only implicitly. SHSP hierarchically decodes variables using coupling structure and confidence-aware repair, achieving a 54% average reduction in absolute primal gap across benchmarks and frameworks.

Problem
One-shot solution predictors simultaneously estimate variable marginals despite strong constraint-induced dependencies, limiting their treatment of combinatorial assignments.
Method
SHSP constructs a variable coupling graph, decodes variables from weakly to strongly coupled while conditioning on earlier assignments, and applies mask-and-repair.
Results
54% average reduction in absolute primal gap is reported across four benchmarks, three frameworks, and two downstream solvers.
Takeaways & Limitations
SHSP consistently outperforms one-shot baselines and provides a drop-in predictor for diverse learning-guided acceleration frameworks.
Takeaways & Limitations
The evaluation focuses on MILP instances whose integer variables are binary, with general integer variables handled through preprocessing reduction.

Abstract

from arXiv · show

Mixed-Integer Linear Programming (MILP) is a fundamental optimization paradigm in combinatorial optimization and has been widely applied across real-world domains. Due to its NP-hard nature, obtaining optimal solutions for large-scale or highly constrained MILP instances remains computationally prohibitive. Learning-based solution prediction has therefore emerged as a promising approach to provide high-quality variable assignment for solver acceleration. However, existing methods typically adopt a one-shot prediction paradigm that predicts the marginal probabilities of all variables simultaneously. As a result, the conditional dependencies among variables are only implicitly captured through message passing, with the burden of modeling the combinatorial structure falling entirely on the representational capacity of graph neural networks. To address this limitation, we propose the Structure-Aware Hierarchical Solution Prediction (SHSP) framework that replaces the parallel marginal decoding of one-shot methods with a novel hierarchical conditional decoding mechanism. Specifically, SHSP constructs a variable coupling graph from the constraint structure, decodes variables sequentially along a hierarchy of increasing coupling strength, and conditions each hierarchy on previously predicted assignments. To mitigate error accumulation during the decoding process, SHSP further incorporates a confidence-aware mask-and-repair mechanism to identify and correct unreliable intermediate predictions. We integrate SHSP with multiple learning-guided search methods, and evaluate it on four standard MILP benchmarks. Experimental results demonstrate that SHSP significantly outperforms existing one-shot prediction baselines, achieving a 54% average reduction in solution gap.

1 Introduction

MILP solving remains expensive on large or highly constrained instances, motivating learning-based solution prediction. SHSP addresses one-shot prediction’s treatment of interdependent variables by decoding assignments hierarchically and improves primal gaps across benchmarks.

Large-scale and highly constrained MILP instances remain computationally expensive despite advanced solver techniques.
Existing solution predictors usually estimate all variable marginals simultaneously, leaving constraint-induced dependencies implicit in the GNN encoder.
SHSP explicitly models dependencies using a weighted variable coupling graph and sequentially predicts weakly coupled before strongly coupled variables.
SHSP combines hierarchical prediction with structure-aware variable fixing that prioritizes strongly coupled variables to reduce the downstream search space.
54% average reduction in absolute primal gap is achieved across four benchmarks, while SHSP consistently outperforms one-shot baselines.

2 Preliminaries

MILP optimizes a linear objective over linear constraints with integer and continuous variables, and learning-guided methods such as PaS use predicted marginals to guide solver search. PaS converts marginal predictions into partial assignments and a trust-region optimization problem.

2.1 Mixed-Integer Linear Programming: MILP optimizes a linear objective over a linearly constrained feasible region, with a subset of decision variables restricted to integer values.
2.1 Mixed-Integer Linear Programming: The paper focuses on instances with binary integer variables, treating general integer variables as reducible to binary ones through preprocessing.
2.1 Mixed-Integer Linear Programming: MILP instances can be represented as weighted bipartite graphs connecting constraint nodes to variables appearing with nonzero coefficients.
2.2 Predict-and-Search: PaS integrates neural solution prediction with mathematical optimization in a two-stage framework for accelerating MILP solving.
2.2 Predict-and-Search: PaS factorizes the joint solution distribution into per-variable marginals under a variable-wise independence assumption.
2.2 Predict-and-Search: PaS fixes variables with the highest and lowest predicted marginals, then constrains optimization to a trust-region neighborhood around the resulting partial solution.
2.2 Predict-and-Search: When ∆ = 0, PaS degenerates to the hard-fixing scheme used by neural diving.

3 Methodology

SHSP builds a coupling-aware hierarchy and decodes variables from weakly to strongly coupled while conditioning on earlier assignments. Confidence-based masking, repair, weighted training, and structure-aware fixing address unreliable predictions and downstream search reduction.

3 Methodology: SHSP sequentially decodes variable assignments in increasing coupling-strength order, conditioning each step on preceding partial assignments.
3.1 Variable Coupling Graph: The coupling graph retains variables connected to binary variables and links variable pairs that co-occur in constraints.
3.1 Variable Coupling Graph: Edge weights combine normalized expected violation and coefficient importance, then aggregate local weights across shared constraints.
3.2 Structure-Aware Hierarchical Prediction: Variables are sorted by variable coupling score and evenly partitioned into hierarchies, with weakly coupled variables decoded first to anchor later predictions.
3.2 Structure-Aware Hierarchical Prediction: Each decoding step augments variable features with tentative assignments and confidence states, while future-step variables receive placeholders.
3.2 Structure-Aware Hierarchical Prediction: The mask-and-repair mechanism preferentially masks lower-confidence predictions and replaces masked assignments with repaired predictions.
3.2 Structure-Aware Hierarchical Prediction: SHSP differs from Apollo-MILP by using coupling-guided hierarchy and operating entirely within prediction rather than alternating prediction with solver calls.
3.2 Structure-Aware Hierarchical Prediction: Training uses weighted losses over hierarchies and repair, with higher-quality solutions receiving greater supervision weight.

4 Experiments

SHSP is evaluated on four MILP benchmarks against traditional solvers and learning-based prediction methods under 1,000-second limits. It consistently reduces primal gaps, accelerates convergence, and benefits from its mask-and-repair, hierarchical prediction, and structure-aware fixing components.

Experimental Setup: Experiments use four benchmarks—CA, WA, IP, and SC—with 240 training, 60 validation, and 100 testing instances per problem.Baselines include Gurobi, SCIP, Neural Diving, Predict-and-Search, and Apollo-MILP.
Main Evaluation: SHSP consistently improves absolute primal gaps across PaS, Apollo, and ND on all four benchmarks.With PaS, reductions reach 99.7% on CA, 38.1% on WA, 24.3% on IP, and 42.1% on SC; Apollo and ND also show substantial reductions.
Main Evaluation: Apollo+SHSP reaches the best-known solution on CA, surpassing the solution obtained by Gurobi with a 3,600-second time limit.The result indicates that SHSP can provide strong initialization for downstream search.
Main Evaluation: SHSP-based methods converge faster and achieve lower primal gaps than corresponding one-shot predictors during runtime.Figure 2 averages results over 100 testing instances under a 1,000-second Gurobi budget that includes SHSP graph construction time.
Ablation Study: Masking alone is inconsistent, whereas combining masking with repair yields the best results across datasets and prediction frameworks.Masking without correction can discard predictive information; the two components are complementary.
Ablation Study: Hierarchical prediction and structure-aware fixing each consistently improve solution quality over their respective original components on PaS and Apollo.The ablations support both the predictor replacement and the fixing strategy as contributors to performance.

5 Conclusion

SHSP introduces structure-aware hierarchical solution prediction for MILP, replacing parallel marginal decoding with conditional decoding guided by variable coupling. Experiments show improved solution prediction and solver acceleration across multiple frameworks and benchmarks.

5 Conclusion: SHSP replaces one-shot marginal prediction with hierarchical conditional decoding that explicitly models dependencies among MILP variables.Variables are organized using a coupling graph and decoded from weakly to strongly coupled groups.
5 Conclusion: SHSP conditions each hierarchy on preceding assignments and uses confidence-aware masking and repair to mitigate accumulated prediction errors.The method also introduces a structure-aware fixing strategy for downstream search-space reduction.
5 Conclusion: SHSP is designed as a drop-in predictor for learning-guided MILP acceleration frameworks and is evaluated across multiple solver components and benchmarks.The framework builds on graph-based solution prediction and integrates with downstream variable fixing.
5 Conclusion: The graph representation extends the standard MILP bipartite graph with target indicator, previous prediction, and previous confidence features.These features support the hierarchical decoding process.
5 Conclusion: The coupling graph assigns variable-pair weights using expected violation and coefficient importance derived from shared constraints.Final edge weights aggregate local coupling contributions over constraints containing both variables.

D.1 Benchmarks in Main Evaluation

The main evaluation uses four benchmark datasets generated from established procedures or obtained from the NeurIPS ML4CO 2021 competition, with additional IIS instances from MIPLIB for challenging real-world cases.

D.1 Benchmarks in Main Evaluation: The main evaluation includes CA, SC, IP, and WA benchmark datasets.CA and SC are generated using established combinatorial optimization instance-generation procedures, while IP and WA come from the NeurIPS ML4CO 2021 competition.
D.1 Benchmarks in Main Evaluation: The IIS dataset is a MIPLIB subset selected using similarity based on 100 human-designed features.It is used to evaluate solver performance on challenging real-world instances.
D.1 Benchmarks in Main Evaluation: IIS contains eleven instances, including eight training instances and three testing instances.The testing instances are ramos3, scpj4scip, and scpl4.

E Implementation Details

The SHSP predictor builds on a prior GNN-based MILP architecture and adds a learnable decoding-step embedding so predictions can adapt across hierarchical steps.

E Implementation Details: SHSP uses a graph neural network architecture based on previous learning-based MILP approaches.The predictor retains the bipartite message-passing architecture used in earlier methods.
E Implementation Details: A learnable step embedding is fused with each variable representation to adapt predictions across decoding steps.The current decoding step and variable features are combined before message passing.
E Implementation Details: The predictor represents each variable node using its feature vector together with the current decoding step.The fused representation is then passed through the established bipartite network.

E.2 Training Details

Training and inference replace baseline predictors and fixing strategies with SHSP variants, while accounting for graph-construction costs within solver time budgets.

E.2 Training Details: Training data consists of the best 50 solutions collected from single-threaded Gurobi runs lasting 3,600 seconds per training and validation instance.The predictor starts with a learning rate of 0.001 and trains for 500 epochs.
E.2 Training Details: SHSP training uses teacher forcing early and linearly decays the teacher-forcing ratio from 1.0 to 0 over 50 epochs.Ground-truth assignments condition later steps with probability ρt; model predictions are used otherwise.
E.2 Training Details: The experiments form ND+SHSP, PaS+SHSP, and Apollo+SHSP by replacing each framework’s original predictor and variable-fixing strategy.The corresponding baseline hyperparameter settings are retained for SHSP.
E.2 Training Details: For ND and PaS, the coupling graph is constructed once before inference, whereas Apollo updates it before prediction on each reduced subproblem.Graph construction and update time are deducted from the solver time budget.
E.2 Training Details: SHSP uses two decoding steps on all benchmarks except WA, which uses four.Experiments run on a single machine with an AMD EPYC 7513 processor and NVIDIA GeForce RTX 4090 GPUs.

F.1 More Ablation Study Results

The ablations separately evaluate SHSP’s hierarchical predictor, structure-aware fixing strategy, and confidence-based mask-and-repair mechanism across four MILP benchmarks. Each component contributes to more accurate predictions, stronger variable fixing, or improved search-space reduction.

Confidence-Based Mask and Repair Mechanism: The mask-and-repair ablation compares None, Mask, and Mask+Repair variants across CA, WA, IP, and SC.The two components are complementary and jointly contribute to overall performance.
Hierarchical Solution Prediction Predictor: The hierarchical predictor generates more accurate solution predictions than the original GNN predictor under the same structure-aware fixing strategy.More accurate predictions enable more effective variable fixing and problem reduction.
Fixing Strategies: Prioritizing structurally important variables produces more effective search-space reduction than the original fixing strategy.The resulting reduction allows the solver to explore the remaining search space more efficiently.

F.2 Results on MIPLIB

SHSP is additionally evaluated on IIS, a homogeneous subset of the heterogeneous MIPLIB dataset. On this real-world subset, SHSP methods outperform their corresponding baselines, supporting their potential for real-world applications.

Results on MIPLIB: The MIPLIB evaluation uses IIS, a subset containing similar instances selected because heterogeneous instances make direct application of ML-based solvers difficult.Additional information on IIS is provided in Appendix D.2.
Results on MIPLIB: SHSP methods outperform their corresponding baselines on the IIS dataset.Solving performance is reported in Tables 13 and 14, with Gurobi used as the downstream solver under a 3,600-second limit.

F.3 Runtime Results

SHSP adds little neural inference overhead, while graph construction remains substantially shorter than the overall solver runtime. The reported runtime analysis covers inference and graph construction across the four benchmark datasets.

Runtime Overhead: SHSP inference time is only slightly higher than that of the original GNN predictor and remains negligible versus overall solver runtime.The runtime comparison reports average per-instance inference and graph construction times.
Runtime Overhead: Graph construction takes 0.26s to 15.23s per instance, which is much shorter than the solver runtime.This overhead is included in the solver time budget for the evaluated frameworks.