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

cs.LGAug 26, 2026

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

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

Organizations: State Key Laboratory of Novel Software Technology, Nanjing University · School of Artificial Intelligence, Nanjing University · State Key Laboratory of Technology and Equipment for Defense Against Power System Operational Risks, Nari Technology Co., Ltd.

Abstract

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.

Figures & tables

Figure 1: Overview of the proposed method. Given an original MILP instance, we first construct a variable coupling graph to capture the structural dependencies among decision variables. Based on variable coupling graph, variables are ranked according to their coupling score and divided into multiple hierarchies. Our SHSP sequentially predicts variables following the weak-to-strong hierarchy, with a mask-and-repair mechanism to mitigate error accumulation. Finally, the predicted variable assignments are combined with a structure-aware variable fixing strategy and applied to downstream learning-guided search frameworks such as Predict-and-Search ( Han et al. 2023 ) .

Method	CA $\uparrow$ (BKS:98489.24)		WA $\downarrow$ (BKS:706.86)		IP $\downarrow$ (BKS:11.69)		SC $\downarrow$ (BKS:123.30)
Method	Obj	Gap abs	Obj	Gap abs	Obj	Gap abs	Obj	Gap abs
Gurobi (3600s)	98453.42	35.82	706.86	0.00	11.69	0.00	123.30	0.00
Gurobi (1000s)	97407.51	1081.73	707.07	0.21	12.16	0.47	123.54	0.24
ND	94340.63	4148.61	707.12	0.26	14.18	2.49	123.51	0.21
ND+SHSP	97121.05	1368.19	707.07	0.21	11.83	0.14	123.51	0.21
Improvement	-	67.02%	-	19.23%	-	94.38%	-	0.00%

Table 1: Performance comparison on four benchmark datasets (CA, WA, IP, and SC) using Gurobi under a 1000-second time limit.

\uparrow

indicates that higher values are better, while

\downarrow

indicates that lower values are better. Bold values denote the better results. Improvement denotes the relative reduction in Gap abs relative to the corresponding downstream solution-prediction framework.

Figure 2: The convergence curves of primal gaps as the solving process proceeds. All methods are implemented using Gurobi with a total time budget of 1,000 seconds. For a fair comparison, the graph construction time of SHSP is included in this budget. Results are averaged over 100 testing instances. A lower primal gap indicates faster convergence and better solving performance.

Method	CA $\uparrow$ (BKS:98489.24)		WA $\downarrow$ (BKS:706.86)		IP $\downarrow$ (BKS:11.69)		SC $\downarrow$ (BKS:123.30)
Method	Obj	Gap abs	Obj	Gap abs	Obj	Gap abs	Obj	Gap abs
SCIP (3600s)	97795.78	693.46	708.21	1.35	19.06	7.37	124.58	1.28
SCIP (1000s)	96932.37	1556.87	709.62	2.76	22.69	11.00	125.81	2.51
ND	94338.51	4150.73	707.83	0.97	16.33	4.64	125.87	2.57
ND+SHSP	97267.46	1221.78	707.18	0.32	13.70	2.01	125.84	2.54
Improvement	-	70.57%	-	67.01%	-	56.68%	-	1.17%

Table 2: Performance comparison on four benchmark datasets (CA, WA, IP, and SC) using SCIP under a 1000-second time limit.

\uparrow

indicates that higher values are better, while

\downarrow

Method	CA $\uparrow$	IP $\downarrow$
PaS+SHSP (None)	98380.92	12.12
PaS+SHSP (Mask)	98416.55	12.17
PaS+SHSP (Mask+Repair)	98487.72	11.97
Apollo+SHSP (None)	98385.20	11.78
Apollo+SHSP (Mask)	98344.07	11.80
Apollo+SHSP (Mask+Repair)	98489.24	11.71

Table 3: Ablation study of the proposed confidence-based mask-and-repair strategy on the CA and IP datasets. Bold values denote the better results.

Method (Fixing Strategy)	CA $\uparrow$	IP $\downarrow$
PaS (Structure-Aware)	97184.33	12.12
PaS+SHSP (Original)	98061.51	12.34
PaS+SHSP (Structure-Aware)	98487.72	11.97
Apollo (Structure-Aware)	98015.32	11.87
Apollo+SHSP (Original)	98070.43	12.08
Apollo+SHSP (Structure-Aware)	98489.24	11.71

Table 4: Ablation study of the proposed hierarchical solution prediction and structure-aware fixing strategy on the CA and IP datasets. Bold values denote the better results.

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Index	Variable Feature Name	Description
0	Objective	Normalized objective coefficient
1	Variable coefficient	Average variable coefficient in all constraints
2	Variable degree	Degree of the variable node in the bipartite graph representation
3	Maximum variable coefficient	Maximum variable coefficient in all constraints
4	Minimum variable coefficient	Minimum variable coefficient in all constraints
5	Variable type	Whether the variable is an integer variable or not

Appendix

Table 5: The variable features, constraint features, and edge features used for the graph representation. Newly introduced features are shown in bold.

	CA	WA	IP	SC
Constraint Number	2592	64318	195	3000
Variable Number	1500	61000	1083	5000
Binary Variables	1500	1000	1050	5000
Continuous Variables	0	60000	33	0
Integer Variables	0	0	0	0

Appendix

Table 6: Summary statistics of the benchmark datasets used in the main evaluation.

Instance	Constraint Number	Variable Number	Binary Variables
ex1010-pi	1468	25200	25200
fast0507	507	63009	63009
glass-sc	6119	214	214
iis-glass-cov	5375	214	214
iis-hc-cov	9727	297	297
ramos3	2187	2187	2187

Appendix

Table 7: Statistical information of the instances in the IIS dataset. All instances contain only binary variables.

Dataset	PaS $(k_{0},k_{1},\Delta)$	ND $(k_{0},k_{1})$
CA	$(600,0,20)$	$(600,0)$
WA	$(0,500,10)$	$(0,500)$
IP	$(400,5,10)$	$(400,5)$
SC	$(2000,0,100)$	$(2000,0)$

Appendix

Table 8: Hyperparameter settings for PaS and ND on different benchmark datasets.

	CA	WA	IP	SC
Iteration 1	$(400,0,60)$	$(20,200,100)$	$(100,20,50)$	$(1000,0,200)$
Iteration 2	$(200,0,30)$	$(10,100,50)$	$(40,15,20)$	$(500,0,100)$
Iteration 3	$(100,0,15)$	$(10,5,5)$	$(20,15,10)$	$(250,0,50)$
Iteration 4	$(50,0,10)$	$(1,10,5)$	$(5,50,30)$	$(10,0,5)$

Appendix

Table 9: Hyperparameter configuration of

(k_{0}^{(i)},k_{1}^{(i)},\Delta^{(i)})

in Apollo-MILP.

Dataset	ND+SHSP	PaS+SHSP	Apollo+SHSP
CA	$(0.10,0.90,0.5)$	$(0.10,0.90,0.5)$	$(0.04,0.90,0.7)$
WA	$(0.10,0.90,0.7)$	$(0.10,0.90,0.7)$	$(0.10,0.95,0.8)$
IP	$(0.05,0.95,0.7)$	$(0.10,0.90,0.7)$	$(0.10,0.50,0.5)$
SC	$(0.10,0.90,0.5)$	$(0.10,0.90,0.5)$	$(0.10,0.90,0.7)$

Appendix

Table 10: The additional hyperparameter settings

(\theta_{0},\theta_{1},\eta)

for ND+SHSP, PaS+SHSP and Apollo+SHSP on different benchmark datasets.

Method	CA $\uparrow$ (BKS:98489.24)		WA $\downarrow$ (BKS:706.86)		IP $\downarrow$ (BKS:11.69)		SC $\downarrow$ (BKS:123.30)
Method	Obj	Gap abs	Obj	Gap abs	Obj	Gap abs	Obj	Gap abs
PaS+SHSP (None)	98380.92	108.32	707.06	0.20	12.12	0.43	123.47	0.17
PaS+SHSP (Mask)	98416.55	72.69	707.05	0.19	12.17	0.48	123.53	0.23
PaS+SHSP (Mask+Repair)	98487.72	1.52	706.99	0.13	11.97	0.28	123.41	0.11
Apollo+SHSP (None)	98385.20	104.04	707.10	0.24	11.78	0.09	123.42	0.12
Apollo+SHSP (Mask)	98344.07	145.17	707.01	0.15	11.80	0.11	123.39	0.09

Appendix

Table 11: Detailed ablation study of the proposed confidence-based mask-and-repair strategy.

\uparrow

indicates that higher values are better, while

\downarrow

indicates that lower values are better. Bold values denote the best results, including ties.

Method	CA $\uparrow$ (BKS:98489.24)		WA $\downarrow$ (BKS:706.86)		IP $\downarrow$ (BKS:11.69)		SC $\downarrow$ (BKS:123.30)
Method	Obj	Gap abs	Obj	Gap abs	Obj	Gap abs	Obj	Gap abs
PaS (structure-aware fixing)	97184.33	1304.91	707.08	0.22	12.12	0.43	123.49	0.19
PaS+SHSP (original fixing)	98061.51	427.73	707.01	0.15	12.34	0.65	123.53	0.23
PaS+SHSP (structure-aware fixing)	98487.72	1.52	706.99	0.13	11.97	0.28	123.41	0.11
Apollo (structure-aware fixing)	98015.32	473.92	707.09	0.23	11.87	0.18	123.40	0.10
Apollo+SHSP (original fixing)	98070.43	418.81	707.01	0.15	12.08	0.39	123.37	0.07

Appendix

Table 12: Detailed ablation study of the proposed hierarchical solution prediction predictor and structure-aware fixing strategy.

\uparrow

indicates that higher values are better, while

\downarrow

indicates that lower values are better. Bold values denote the best results, including ties.

Method	Obj $\downarrow$	Gap ${}_{\mathrm{abs}}\downarrow$
Gurobi	211.00	20.00
PaS	209.00	18.00
PaS+SHSP	206.67	15.67
Apollo	214.33	23.33
Apollo+SHSP	208.67	17.67

Appendix

Table 13: Results on the IIS dataset, a subset of MIPLIB used by Liu et al. (2025) . All learning-based methods use Gurobi as the downstream solver, with a solving time limit of 3,600 seconds.

Instance	BKS	Gurobi	PaS	Apollo	PaS+SHSP	Apollo+SHSP
ramos3	186.00	228.00	227.00	242.00	221.00	226.00
scpj4scip	128.00	133.00	131.00	132.00	130.00	131.00
scpl4	259.00	272.00	269.00	269.00	269.00	269.00

Appendix

Table 14: The best objectives found on each test instance in IIS. BKS denotes the best known objective values reported by MIPLIB ( https://miplib.zib.de/index.html ).

Dataset	GNN Predictor	SHSP Predictor	Graph construction time
CA	0.0050s	0.0146s	0.82s
WA	0.0439s	0.2197s	5.48s
IP	0.0043s	0.0131s	0.26s
SC	0.0658s	0.1953s	15.23s

Appendix

Table 15: Comparison of the average per-instance inference time and graph construction time (in seconds) on the four benchmark datasets.

Mixed-Integer Linear Programming

Mixed-integer linear programming (MILP) optimizes linear objectives and constraints when some decisions must be integer-valued.

See all 50 papers

Learning Early-to-Final Solution Consistency for MILP Acceleration
Aug 20, 2026Guanlin Li, Chengrui Gao, Chenguang Wang +6Mixed-Integer Linear Programming Learning to Optimize
State Key Laboratory of Novel SoftwareTechnology, Nanjing University · School of Artificial Intelligence,Nanjing University · State Key Laboratory of Technology and Equipment for Defense Against Power System Operational Risks, Nari Technology Co., Ltd.
Sequence-Structured Decision Learning for Branch-and-Bound in Mixed-Integer Linear Programming
Oct 10, 2026Tengfei Liu, Jinrun Liu, Bai Yan +2Branch and Bound Mixed-Integer Linear Programming
Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen, China · School of Computer Science and Technology, Dongguan University of Technology, Dongguan, China
Reformulation-Contrastive Learning for Mixed Integer Programs
Sep 30, 2026Ousema Bouaneni, Mathis Le Bail, Clément Elliker +2Contrastive Learning Representation Learning
LIX (École Polytechnique, IP Paris, CNRS) · AMIAD (Agence Ministérielle pour l’IA de Défense)

Aug 20, 2026J/K move · Enter open · S save

Learning Early-to-Final Solution Consistency for MILP Acceleration

Guanlin Li, Chengrui Gao, Chenguang Wang, Haopu Shang+5

State Key Laboratory of Novel SoftwareTechnology, Nanjing University · School of Artificial Intelligence,Nanjing University · State Key Laboratory of Technology and Equipment for Defense Against Power System Operational Risks, Nari Technology Co., Ltd.

Mixed-Integer Linear Programming Learning to Optimize Learning-Augmented Algorithms Inference-Time Search

Open paper AskPDF arXiv

Mixed-Integer Linear Programming (MILP) is a fundamental problem class in operations research and combinatorial optimization, with broad applications to industrial decision-making. Owing to their NP-hardness, however, modern solvers may struggle to find high-quality solutions for challenging MILP instances within practical time limits. Recent learning-based approaches seek to accelerate MILP solving by directly predicting high-quality solutions from static instance-level features, such as variable-constraint bipartite graphs. Yet accurate solution prediction from instance features alone is difficult, and these methods largely overlook the information revealed during the solver's search process. In this paper, we find that solutions produced at the early search stage of MILP solvers, which are computationally cheap to obtain, are often structurally close to the solutions found after full-budget search. Motivated by this observation, we propose a new solver-informed paradigm that shifts the learning target from variable assignment to early-to-final consistency: for each variable, we predict whether its early-stage assignment should persist in full-budget solutions. The predicted consistency naturally guides downstream search, for instance by fixing the assignments deemed consistent. At inference time, we further ensemble consistency predictions across multiple early-stage solutions to improve robustness. Experiments across four MILP benchmarks show our method improves prediction-guided search across diverse downstream pipelines. With Gurobi, our proposed method reduces the primal gap by 56.9% on average and closes it completely on combinatorial auction instances. Besides, we transferred the Gurobi-trained model zero-shot to SCIP without adaptation, achieving a 36.4% average gap reduction across benchmarks.

Abstract

Mixed-Integer Linear Programming

Explore similar work

Learning Early-to-Final Solution Consistency for MILP Acceleration

Sequence-Structured Decision Learning for Branch-and-Bound in Mixed-Integer Linear Programming

Reformulation-Contrastive Learning for Mixed Integer Programs