SRG: Score-based Relaxation-guided Generation for Mixed Integer Linear Programming

Ruobing Wang; Xin Li; Yujie Fang; Mingzhong Wang

cs.LGMar 25, 2026

SRG: Score-based Relaxation-guided Generation for Mixed Integer Linear Programming

Authors: Ruobing Wang, Xin Li, Yujie Fang, Mingzhong Wang

Organizations: Beijing Institute of Technology, Beijing, China · University of the Sunshine Coast, Australia

Abstract

We propose Score-based Relaxation-guided Generation (SRG), a generative framework based on an approximate formulation of relaxation-guided stochastic differential equations (SDEs) for mixed-integer linear programming. SRG employs a Transformer-based score network that incorporates feasibility and optimality signals into score modeling, encouraging the learned generative model to place more probability mass on feasible, high-quality regions of the solution space. At inference time, SRG directly samples diverse candidate solutions from the learned score model without requiring any additional guidance module. These candidates are then used to construct compact trust-region subproblems for standard MILP solvers. Across multiple public benchmarks, SRG matches or improves upon the solution quality of the strongest learning-based baselines, with particularly strong gains in challenging candidate-generation settings. Moreover, SRG shows promising zero-shot transferability to unseen cross-scale and cross-problem instances, improving solver objectives and reducing search time in several cases through higher-quality initial candidates and compact trust-region search.

Figures & tables

Method	SC		MIS		CA		CFL
Method	Obj( $\downarrow$ )	$\mathrm{Gap}_{\mathrm{ref}}$ ( $\downarrow$ )	Obj( $\uparrow$ )	$\mathrm{Gap}_{\mathrm{ref}}$ ( $\downarrow$ )	Obj( $\uparrow$ )	$\mathrm{Gap}_{\mathrm{ref}}$ ( $\downarrow$ )	Obj( $\downarrow$ )	$\mathrm{Gap}_{\mathrm{ref}}$ ( $\downarrow$ )
SCIP ( Bestuzheva et al., 2023 )	$55.68\pm 10.49$	$0.00$	$455.84\pm 6.03$	$0.00$	$60797.78\pm 1245.71$	$0.00$	$8858.28\pm 446.19$	$0.00$
PaS(S) ( Han et al., 2023 )	$55.68\pm 10.49$	$0.00$	$455.32\pm 6.80$	$0.52$	$60693.89\pm 1184.15$	$103.89$	$8861.92\pm 444.80$	$3.64$
ConPaS(S) ( Huang et al., 2024 )	$55.68\pm 10.49$	$0.00$	$455.44\pm 6.38$	$0.40$	$\textbf{60693.89}\pm 1184.15$	103.89	$8861.93\pm 444.80$	$3.65$
L2O-DiffILO(S) ( Geng et al., 2025 )	$55.68\pm 10.49$	$0.00$	$452.02\pm 9.26$	$3.82$	$58433.46\pm 1468.10$	$2364.32$	$8858.28\pm 446.19$	$0.00$
Apollo-MILP(S) ( Liu et al., 2025 )	$55.68\pm 10.49$	$0.00$	$451.60\pm 9.00$	$4.24$	$59131.99\pm 1301.43$	$1665.79$	$8865.97\pm 446.48$	$7.69$

Table 1: Results on medium-scale MILP benchmarks. Results are averaged over 50 test instances. “

/

” indicates subproblem

M_{\text{search}}(\tilde{x})

is infeasible. “

(\text{S})

” and “

(\text{G})

” mean the underlying solver is SCIP and Gurobi, respectively. All baselines have a 1 00s time limit to search for the best primal bound.

Method	SC		MIS		CA		CFL
Method	Obj( $\downarrow$ )	$\mathrm{Gap}_{\mathrm{ref}}$ ( $\downarrow$ )	Obj( $\uparrow$ )	$\mathrm{Gap}_{\mathrm{ref}}$ ( $\downarrow$ )	Obj( $\uparrow$ )	$\mathrm{Gap}_{\mathrm{ref}}$ ( $\downarrow$ )	Obj( $\downarrow$ )	$\mathrm{Gap}_{\mathrm{ref}}$ ( $\downarrow$ )
SCIP ( Bestuzheva et al., 2023 )	$13.85\pm 3.89$	$0.00$	$912.40\pm 7.00$	$0.00$	$11759.46\pm 196.36$	$0.00$	$9667.92\pm 503.55$	$0.00$
PaS(S) ( Han et al., 2023 )	$13.90\pm 3.94$	$0.05$	$911.15\pm 8.31$	$1.25$	$11574.91\pm 209.90$	$184.55$	$9672.72\pm 501.40$	$4.80$
ConPaS(S) ( Huang et al., 2024 )	$13.90\pm 3.94$	$0.05$	$910.90\pm 8.56$	$1.50$	$11538.57\pm 228.22$	$220.89$	$9672.72\pm 501.40$	$4.80$
L2O-DiffILO(S) ( Geng et al., 2025 )	$13.90\pm 3.88$	$0.05$	$910.55\pm 8.04$	$1.85$	$11263.01\pm 314.25$	$496.45$	$9667.92\pm 503.55$	$0.00$
Apollo-MILP(S) ( Liu et al., 2025 )	$13.85\pm 3.89$	$0.00$	$910.35\pm 8.14$	$2.05$	$11731.41\pm 200.03$	$229.14$	$9667.92\pm 503.55$	$0.00$

Table 2: C ross- S cale results on large-scale MILP benchmarks. Results are averaged over 20 test instances. All baseline solvers have a 6 00s time limit to obtain the best primal bound. We D irectly use the P retrained SRG from M edium-scale MILP benchmarks for large-scale solving.

Problem	Obj.		Time(s)
Problem	Gurobi	SRG (G)	Gurobi	SRG (G)
IP( $\downarrow$ )	$12.29\pm 6.12$	$\textbf{11.82}\pm 5.81$	$600.16\pm 0.05$	$\textbf{600.30}\pm 0.07$
LB( $\downarrow$ )	$703.80\pm 10.30$	$\textbf{703.80}\pm 10.30$	$600.59\pm 0.18$	$\textbf{589.36}\pm 23.27$
blp-ic98 ( $\downarrow$ )	$4491.45$	4491.45	$19.0$	17.7
cmflsp50 1 1 1 cmflsp50-24-8-8 ( $\downarrow$ )	$55{,}789{,}390$	55,789,390	265.2	$387.3$
cbs-cta ( $\downarrow$ )	$0.00$	0.00	$0.9$	0.8

Table 3: C ross P roblem results with solving time limit of 6 00s.

Figure 2: C ross P roblem solving: Primal bound iteration trajectory for Item Placement and Load Balancing.

Method	CFL(M, Gurobi)
	Obj( $\downarrow$ )	Time( $\downarrow$ )
SRG w/o Guide	$8878.85\pm 441.06$	$0.41\pm 0.31$
SRG (Ours)	$\textbf{8858.28}\pm 446.19$	$0.34\pm 0.17$
Method	CFL (L, Gurobi)
	Obj( $\downarrow$ )	Time( $\downarrow$ )
SRG w/o Guide	$9688.42\pm 502.69$	$0.47\pm 0.22$

Table 4: A blation S tudy on relaxation guidance on CFL (“M” means Medium, and “L” means Large).

Setting	$L,p$	$\rho_{o},\rho_{c}$	$\gamma_{o},\gamma_{c}$	Obj.( $\uparrow$ )
$\rho_{c}$	$(12,4)$	$(0.3,0.3)$	$(2,5)$	$62729.85\pm 1081.66$
$\rho_{c}$	$(12,4)$	$(0.3,0.5)$	$(2,5)$	$63054.66\pm 1183.44$
$\rho_{c}$	$(12,4)$	$(0.3,1.0)$	$(2,5)$	$62854.61\pm 1317.24$
$\rho_{o}$	$(12,4)$	$(0.5,0.3)$	$(2,5)$	$62584.80\pm 1051.49$
$\rho_{o}$	$(12,4)$	$(1.0,0.3)$	$(2,5)$	$62754.48\pm 1161.98$
$\gamma_{o},\gamma_{c}$	$(12,4)$	$(0.3,0.3)$	$(2,7)$	$62770.34\pm 1127.15$

Table 5: S ensitivity A nalysis results for different components in SRG on Medium CA. We report averaged metrics on 50 instances. Except for the training-step experiment, all experiments use

T=50

Figure 3: A blation R esults for adaptation rules on $\gamma_{o}$ and $\gamma_{c}$ .

Appendix figures & tables15 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5: Toy 2D LP instance with objective contours and constraints

TYPE	SC	MIS	CA	CFL	Time Limit	Num.
ECOLE (Middle)	(1000, 1000)	(1000, $\sim$ 4213)	(2000, $\sim$ 1375)	(1550, 1581)	100s	50
ECOLE (Large)	(2000, 1000)	(2000, $\sim$ 8478)	(2000, $\sim$ 2345)	(2550, 2601)	600s	20

Appendix

Table 6: Problem sizes for each benchmark (variables, constraints). All benchmark ground truth solutions are obtained by Gurobi within 600 seconds.

TYPE	Item Placement	Load balancing	Time Limit	Num.
ML4CO	(1,083, 195)	(61,000, 64,363)	600s	5

Appendix

Table 7: Problem sizes for public benchmarks from ML4CO (variables, constraints).

Size	blp-ic98	cmflsp50-24-8-8	cbs-cta	tbfp-network
Variables	13,640	16,392	24,793	72,747
Discrete Variables	13,550	1,392	2,467	72,747
Continuous Variables	90	15,000	22,326	0
Constraints	717	3,520	10,112	2,436

Appendix

Table 8: Problem sizes for public benchmarks from MIPLIB (variables, constraints).

	SC	IS	CA	CFL
Generate Time (M)	$0.46\pm 0.03$	$0.48\pm 0.06$	$0.45\pm 0.03$	$0.47\pm 0.03$
Generate Time (L)	$0.53\pm 0.05$	$0.48\pm 0.04$	$0.48\pm 0.04$	$0.47\pm 0.05$

Appendix

Table 9: Generation time of SRG on medium and large-scale instances.

Figure 6: Training curves on four benchmarks.

Medium	SC	CA	IS	CFL
$(h,w)$	(25,40)	(40,50)	(25,40)	(31,50)
$T_{\text{Train}}$	50	50	20	20
$L$	12	12	12	12
$p$	10	4	4	4
$(\gamma_{o},\gamma_{c})$	(5, 10)	(2, 5)	(3,5)	(0.05,10)
$(\rho_{o},\rho_{c})$	(0.3,0.3)	(0.3,0.5)	(0.3,0.3)	(0.3,0.3)

Appendix

Table 10: Training parameters for main results.

	Medium								Large
	Gurobi				SCIP				Gurobi				SCIP
	SC	CA	IS	CFL	SC	CA	IS	CFL	SC	CA	IS	CFL	SC	CA	IS	CFL
$T_{\text{sample}}$	20	20	20	20	20	20	20	20	20	20	20	20	20	20	20	20
$k_{1}$	20	150	500	100	20	150	200	100	50	50	150	150	50	150	150	150
$k_{2}$	400	800	50	200	400	800	400	200	300	200	800	300	300	800	800	300
$\Delta$	300	500	400	150	300	500	400	150	200	200	500	200	200	500	500	200

Appendix

Table 11: Sampling parameters for main results, split by solver.

Figure 7: Primal bound iterations on MIPLIB instances.

Figure 8: Obj/Penalty/Sparsity metric trajectories during the iterative generation process for a medium-scale Combinatorial Auction instance.

Figure 9: Obj/Penalty/Sparsity metric trajectories during the iterative generation process for a medium-scale Facility Location instance.

Figure 10: Qualitative illustration of the generation process for medium-scale Combinatorial Auction.

Figure 11: Qualitative illustration of the generation process for medium-scale Facility Location.

Figure 12: Influence of different parameters on the target-score approximation loss on the medium-scale CA benchmark.

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

Teaching LLMs to Generate Challenging MILP Instances via Solver Feedback
Sep 29, 2026Jitin Singla, Parikshit Pareek, Pratik Jawanpuria +1Mixed-Integer Linear Programming Large Language Model-Guided Optimization
IIT Roorkee · IIT Bombay · IIT Delhi
Constrained Graph Diffusion for Mixed Integer Optimization
Aug 13, 2026Vincenzo Di Vito, Yusuf Guven, Babak Badnava +3Mixed-Integer Linear Programming Constrained Optimization
University of Virginia · MIT · Los Alamos National Laboratory
GRIMIP: A General Framework for Instance-Specific Configuration of MIP Solvers Using LLMs
Jun 22, 2026Yidong Luo, Xuemin Chen, Chenguang Wang +3Surrogate-Assisted Optimization Mixed-Integer Linear Programming
School of Data Science, The Chinese University of Hong Kong, Shenzhen · School of Science and Engineering, The Chinese University of Hong Kong, Shenzhen · Noah’s Ark Lab, Huawei

Sep 29, 2026J/K move · Enter open · S save

Teaching LLMs to Generate Challenging MILP Instances via Solver Feedback

Jitin Singla, Parikshit Pareek, Pratik Jawanpuria, Parag Singla

IIT Roorkee · IIT Bombay · IIT Delhi

Mixed-Integer Linear Programming Large Language Model-Guided Optimization Synthetic Benchmark Generation RL for Combinatorial Optimization Natural Language to Optimization Modeling Mathematical Problem Generation

Open paper AskPDF arXiv

Generating optimization instances that are both feasible and computationally challenging is crucial for benchmarking solvers and training learning-based optimization algorithms. Existing non-LLM generators rely on seed instances or parameter tuning, resulting in high test-time computational cost, while existing LLM generators lack explicit hardness measures. Recent reinforcement learning methods with verifier feedback evaluate only binary correctness, which is misaligned with generating challenging problems. We note that an optimization solver reports the cost of solving at several stages of its pipeline, and leverage this to design a reward that scores both the solvability and the hardness of generated problems, measured by branch-and-bound nodes and post-cut relaxation gaps. Our key idea is a challenger-solver asymmetric self-play approach, where an LLM challenger generates progressively harder instances and the solver verifies feasibility and hardness, so no seed or training MILP instances are required. We fine-tune Gemma-4-12B and Qwen3.5-4B with GRPO and a size curriculum into OptiScribe-12B and OptiScribe-4B, which generate feasible yet challenging MILP problems from natural language instructions. On capacitated facility location and max-cut, OptiScribe-12B raises median SCIP search nodes by 1.7-5x and post-cut gaps by 1.1-1.7x over its base model and improves the feasibility rate on facility location by 9-19 points, while OptiScribe-4B raises median nodes by up to 15.6x. The problems cover a wider difficulty range than public benchmarks of the same size, follow instructions on density and difficulty, and can tune solver settings for families that public libraries lack. These results indicate that optimization-specific rewards, used in self-play mode, can teach LLMs to generate high-difficulty optimization benchmarks. We will release our code and models publicly on acceptance.

Abstract

Mixed-Integer Linear Programming

Explore similar work

Teaching LLMs to Generate Challenging MILP Instances via Solver Feedback

Constrained Graph Diffusion for Mixed Integer Optimization

GRIMIP: A General Framework for Instance-Specific Configuration of MIP Solvers Using LLMs