LLM-Guided Evolution of Symbolic Acceleration Inequality Families for MILP

Milad Yazdani; Mahdi Mostajabdaveh; Samin Aref; Zirui Zhou

cs.AIAug 16, 2025

LLM-Guided Evolution of Symbolic Acceleration Inequality Families for MILP

Authors: Milad Yazdani, Mahdi Mostajabdaveh, Samin Aref, Zirui Zhou

Organizations: Department of Electrical and Computer Engineering, University of British Columbia, Vancouver, BC, Canada · Huawei Technologies Canada, Burnaby, BC, Canada · Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, ON, Canada

Abstract

Integer programming (IP) is central to many combinatorial optimization tasks but remains challenging due to its NP-hard nature. A practical way to improve IP solvers is to manually design inequality families that exploit problem structure. However, this creative process requires deep expertise and has therefore been difficult to automate. Our proposed framework, Symbolic Acceleration via Generative Evolution (SAGE), automates symbolic discovery of acceleration inequality families at the modeling level. It reasons over a symbolic IP formulation and a natural language description of the problem to discover a reusable set of acceleration inequality families that can be instantiated for each problem instance. These acceleration inequality families are selected through empirical admissibility and impact screening rather than mathematical proofs. SAGE (i) initializes a population of candidate acceleration inequality families via an initializer agent that uses an LLM; (ii) it screens candidates for admissibility on a small development admissibility set for solution feasibility and the separation of the relaxation solution; and (iii) it iteratively refines the population of inequalities through evolutionary crossover and mutation agents. Across seven MILP benchmarks, SAGE reduces optimality gaps by up to $62.1\%$ relative to baseline MILP formulations solved with a fixed time budget and reaches target gaps up to $5.51\times$ faster according to shifted geometric mean speedup. Comprehensive ablations show its robustness across different LLM backends and across solvers and internal cut settings. Code: https://github.com/milad1378yz/sage

Figures & tables

Figure 1: View of SAGE in two stages: during development, SAGE learns a reusable set of acceleration inequality families for a symbolic MILP formulation using a natural language description. During deployment, the families are instantiated for each problem instance and appended to its instantiated MILP before solving.

Mechanism	Stage	Problem-specific structure	Operates on	Derivation	Output
SAGE	Model design, before the solver is called	Yes, for a problem class	Symbolic MILP formulation	Automated, by LLM agents with evolutionary search	A reusable acceleration inequality family, instantiated for each instance
Formulation strengthening ( Vielma, 2015 ; Klotz & Oberdieck, 2024 )	Model design, before the solver is called	Yes, for a problem class	Symbolic MILP formulation	Manual, by an expert	A tighter equivalent formulation of the problem class
Solver presolve ( Savelsbergh, 1994 ; Achterberg et al., 2020 )	Inside the solver, before branch-and-bound	No, generic reductions	Instantiated MILP	Automated, by solver routines	A reduced model of that one instance
Solver cuts and learned runtime policies ( Turner et al., 2023 ; Gasse et al., 2019 ; Li et al., 2023 )	Inside the solver, during branch-and-bound	No, generic cuts or learned policies	Instantiated MILP	Automated, by solver routines or trained policies	Cuts and search decisions during the solve

Table 1: SAGE compared with other mechanisms that augment or transform a MILP: the stage at which each acts, whether it uses problem-specific structure, what it operates on, whether it is manual or automated, and what it returns.

Figure 2: SAGE workflow: an initializer agent proposes a population of candidate acceleration inequality families. Each candidate passes through the Inequality Admissibility Screen for code validity, OSS on the admissibility set $D_{adm}$ , and an LP-separation check, then through the Inequality Impact Scorer on $D_{imp}$ to obtain an inequality impact score based on the optimality gap. Tournament/elite selection and crossover/mutation driven by LLM agents generate the next population.

Figure 3: SAGE Inequality Admissibility Screen: candidate family code must compile (code check), pass OSS check on the admissibility set $D_{adm}$ (i.e., not exclude the recorded reference solution), and separate at least one stored fractional LP optimum (LP-separation check). Failures trigger feedback and regeneration.

Problem	LLM	5 s	10 s	50 s	150 s	300 s	1000 s	2000 s	Average
TSP	DeepSeek-R1	8.2 (± 26.0)	9.1 (± 26.9)	11.9 (± 32.2)	18.1 (± 30.9)	18.5 (± 33.8)	12.9 (± 31.3)	20.7 (± 30.7)	14.2
	Gemini 3 Pro	13.1 (± 27.5)	15.0 (± 27.9)	22.6 (± 31.3)	34.2 (± 30.3)	27.6 (± 33.1)	26.4 (± 33.3)	37.0 (± 31.1)	25.1
	GPT-5.1	12.1 (± 28.4)	8.8 (± 29.7)	15.6 (± 33.2)	17.4 (± 34.1)	11.3 (± 35.0)	16.7 (± 33.8)	18.2 (± 31.6)	14.3
MCND	DeepSeek-R1	3.3 (± 17.8)	4.3 (± 19.9)	11.7 (± 27.0)	13.0 (± 28.2)	14.7 (± 28.9)	18.9 (± 32.4)	16.7 (± 29.7)	11.8
	Gemini 3 Pro	6.8 (± 17.7)	8.2 (± 19.9)	15.1 (± 25.8)	17.4 (± 26.9)	17.8 (± 25.5)	23.2 (± 27.9)	15.8 (± 28.6)	14.9
	GPT-5.1	25.5 (± 30.1)	22.3 (± 29.6)	16.5 (± 27.7)	6.9 (± 30.0)	15.6 (± 28.9)	18.1 (± 29.8)	20.4 (± 25.2)	17.9

Table 2: Test set mean stabilized relative gap improvement

\bar{\Delta}_{g}

(%) from adding the selected SAGE acceleration inequality family (Gurobi, three LLMs). Mean

\pm\sigma

is reported at each checkpoint. Positive values correspond to

g_{\mathrm{aug}}<g_{\mathrm{ref}}

at that checkpoint. Average reports the row average of checkpoint means.

	$g=10^{-5}$		$g=10^{-4}$		$g=10^{-3}$		$g=10^{-2}$		$g=10^{-1}$		Average
Problem	B/A	SGM	B/A	SGM	B/A	SGM	B/A	SGM	B/A	SGM	B/A	SGM
TSP	26/35	3.21	27/37	3.13	27/37	3.16	31/44	3.00	44/47	1.83	31.0/40.0	2.87
MCND	56/57	1.04	62/62	1.04	62/62	1.03	69/69	1.04	76/74	0.92	65.0/64.8	1.01
CWLP	26/23	2.44	35/36	4.24	35/36	4.42	35/36	5.19	35/36	3.83	33.2/33.4	4.02
JSSP	7/8	2.18	7/8	2.31	7/8	2.42	7/8	2.55	10/19	7.20	7.6/10.2	3.33
PDPTW	0/5	5.18	0/5	5.18	0/5	5.19	0/5	5.25	0/20	6.77	0.0/8.0	5.51

Table 3: Time to reach target gaps

g

: baseline vs. SAGE . B/A: instances reaching

g

within 2000 s (Baseline/ SAGE ). SGM: shifted geometric mean speedup (

>1

better). Average reports the row average over all target gaps.

SAGE	Solver-layer policy	Avg SGM speedup
Off	SCIP default	1.00
Off	Turner et al.	2.12
Off	Lawless et al. LLM(0)	2.58
Off	Lawless et al. LLM(5)	2.60
On	SCIP default	3.13
On	Turner et al.	3.45

Table 4: CWLP factorial with learned runtime policies, held-out OR-Library test set, SCIP 10.0, 2000 s time limit, single seed. The reported value is the average over the five target gaps

g\in\{10^{-5},10^{-4},10^{-3},10^{-2},10^{-1}\}

of the time-to-target SGM speedup vs the reference cell ( SAGE off, plain SCIP defaults), following the protocol of Table 3 . Values

>1

are faster. The reference cell is 1.00

\times

by construction.

Problem	Solver	5 s	10 s	50 s	150 s	300 s	1000 s	2000 s	Average
TSP	Gurobi	13.1 (± 27.5)	15.0 (± 27.9)	22.6 (± 31.3)	34.2 (± 30.3)	27.6 (± 33.1)	26.4 (± 33.3)	37.0 (± 31.1)	25.1
TSP	HiGHS	2.5 (± 13.8)	2.9 (± 14.9)	11.3 (± 23.3)	18.6 (± 26.5)	18.5 (± 27.2)	21.4 (± 28.1)	21.9 (± 28.7)	13.9
MCND	Gurobi	6.8 (± 17.7)	8.2 (± 19.9)	15.1 (± 25.8)	17.4 (± 26.9)	17.8 (± 25.5)	23.2 (± 27.9)	15.8 (± 28.6)	14.9
MCND	HiGHS	6.0 (± 15.1)	7.0 (± 16.9)	6.6 (± 22.5)	1.4 (± 27.7)	5.5 (± 28.4)	2.0 (± 29.3)	5.7 (± 29.0)	4.9
CWLP	Gurobi	43.8 (± 20.7)	49.4 (± 22.3)	68.8 (± 28.6)	76.3 (± 23.8)	64.8 (± 23.0)	35.2 (± 39.3)	30.1 (± 38.9)	52.6
CWLP	HiGHS	25.5 (± 24.6)	25.3 (± 24.6)	23.0 (± 24.8)	28.1 (± 29.8)	39.1 (± 36.2)	62.3 (± 32.3)	64.2 (± 31.9)	38.2

Table 5: Gemini 3 Pro selected acceleration inequality family: test stabilized

\bar{\Delta}_{g}

(%) with Gurobi vs. HiGHS. Mean

\pm\sigma

is reported at each checkpoint. Average reports the row average of checkpoint means.

Problem	Solver	5 s	10 s	50 s	150 s	300 s	1000 s	2000 s	Average
TSP	No internal cuts	34.9 (± 25.1)	37.8 (± 25.5)	53.5 (± 23.3)	61.6 (± 18.1)	64.2 (± 16.5)	64.0 (± 16.8)	62.0 (± 20.2)	54.0
TSP	Default internal cuts	13.1 (± 27.5)	15.0 (± 27.9)	22.6 (± 31.3)	34.2 (± 30.3)	27.6 (± 33.1)	26.4 (± 33.3)	37.0 (± 31.1)	25.1
MCND	No internal cuts	2.5 (± 10.0)	2.9 (± 11.0)	4.3 (± 14.8)	3.4 (± 15.3)	1.7 (± 17.1)	4.1 (± 17.2)	5.1 (± 13.6)	3.4
MCND	Default internal cuts	6.8 (± 17.7)	8.2 (± 19.9)	15.1 (± 25.8)	17.4 (± 26.9)	17.8 (± 25.5)	23.2 (± 27.9)	15.8 (± 28.6)	14.9
CWLP	No internal cuts	53.6 (± 19.8)	60.6 (± 21.2)	86.7 (± 19.8)	84.3 (± 28.3)	94.8 (± 8.8)	94.5 (± 8.9)	93.9 (± 9.2)	81.2
CWLP	Default internal cuts	43.8 (± 20.7)	49.4 (± 22.3)	68.8 (± 28.6)	76.3 (± 23.8)	64.8 (± 23.0)	35.2 (± 39.3)	30.1 (± 38.9)	52.6

Table 6: Gemini 3 Pro selected acceleration inequality family: test stabilized

\bar{\Delta}_{g}

(%) with Gurobi internal cuts disabled vs. default. Mean

\pm\sigma

is reported at each checkpoint. Average reports the row average of checkpoint means.

$(\|D_{adm}\|,\|D_{imp}\|)$	$(2,10)$	$(5,10)$	$(10,10)$	$(10,5)$	$(10,2)$
$\bar{\Delta}_{g}\ {\scriptstyle\pm\sigma}\ (\%)$	37.3 $\pm$ 22.0	37.3 $\pm$ 22.0	40.4 $\pm$ 22.3	37.3 $\pm$ 22.0	7.1 $\pm$ 16.4

Table 7: JSSP: test stabilized

\bar{\Delta}_{g}\ {\scriptstyle\pm\sigma}\ (\%)

at the 2000 s checkpoint for the selected SAGE acceleration inequality family vs.

(|D_{adm}|,|D_{imp}|)

Agent	LLM	Code Fail.%	OSS Fail.%	Not Useful %	Success Rate %	$\bar{\Delta}_{imp}\pm\sigma$ (%)
Initializer
Main	DeepSeek	38.1	11.1	25.4	25.4	12.3 $\pm$ 20.8
	Gemini 3 Pro	5.6	12.8	45.1	36.5	14.8 $\pm$ 19.9
	GPT-5.1	8.9	14.7	46.8	29.6	10.4 $\pm$ 19.5
Mutation
General	DeepSeek	17.6	13.2	2.9	66.2	15.5 $\pm$ 16.6

Table 8: SAGE agent outcomes across three LLMs: code fail, OSS fail, LP-separation rejection, success rate, and mean inequality-impact-score gain

\bar{\Delta}_{imp}\pm\sigma

(%) (successful offspring only).

Run	Tokens	Best $s_{imp}$	$-\bar{d}$ (%)
SAGE (5 generations)	761,451	19.07	64.6
Initializer with feedback	765,308	17.60	56.5

Table 9: JSSP with DeepSeek-R1: development comparison between five generations of SAGE and the initializer with feedback, with token usage matched to within 0.51% after the shared initialization. Appendix C.3 gives the protocol and the deployment results.

Component	What it does	Source status
Binary product rows Eq. ( 3 )	Encode $b_{g,t}=v_{g,t}w_{g,t+1}$ , i.e., whether unit $g$ starts at $t$ and shuts down at $t+1$ .	Standard MILP linearization of binary products, not SHUC-specific ( Glover, 1975 ) .
Startup/shutdown capacity envelopes Eq. ( 4 ) to Eq. ( 5 )	Upper-bound reachable thermal capacity when the unit is starting up or shutting down.	Closely aligned with startup/shutdown ramping and strong UC production upper bounds ( Morales-España et al., 2012 ; Knueven et al., 2020 ) .
Lifted adjacent start/shutdown envelope Eq. ( 6 )	Combines the two derating envelopes and uses $b_{g,t}$ to avoid double-counting when both transition indicators are active.	Built from known lifting and UC derating ideas. Closest references are strong UC upper-bound and ramping formulations ( Knueven et al., 2018 ; Knueven et al., 2020 ) .
Ramp-reachability envelopes Eq. ( 7 ) to Eq. ( 9 )	Bound what unit $g$ can contribute at $t$ using previous dispatch/status and ramp-up capability.	Related to ramping polytope and ramp-aware UC formulations ( Knueven et al., 2018 ; Knueven et al., 2020 ) .
Aggregate auxiliary reachability inequality Eq. ( 10 )	Projects unit-level startup, shutdown, and ramp-reachability envelopes into one system-level condition: net load plus reserve must be coverable by reachable thermal capacity.	In our targeted review, close analogs exist for the unit-level components in the UC formulation literature, including reserve and ramp-capability formulations ( Morales-España et al., 2013 ; Morales-España et al., 2015 ) , but we did not identify Eq. ( 10 ) as this same static aggregate inequality added before solving for the SHUC formulation in Appendix F.7 .

Table 10: Post-hoc source attribution for the selected SHUC acceleration inequality family. The table categorizes each component by whether it has a direct literature analog, follows from the base formulation, or appears to be a formulation-specific aggregate component.

Appendix figures & tables19 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: Example JSSP evolutionary trajectory. The green panels show candidate families with annotated inequality impact scores, and the yellow panels show the agent instructions that produced each offspring.

Figure 5: Best (blue, dashed) and mean (orange, dash-dotted) inequality impact scores across 20 generations for the TSP, MCND, CWLP, JSSP, IMO6, PDPTW, and SHUC benchmarks. Shaded regions show one standard deviation.

$t$ (s)	SAGE	Initializer	Difference	95% CI	W/L/T
5	33.8 (± 22.6)	17.9 (± 28.1)	15.9	$[11.7,20.1]$	44 / 9 / 27
10	34.7 (± 23.1)	25.1 (± 27.8)	9.6	$[6.0,13.2]$	41 / 11 / 28
50	26.8 (± 26.4)	22.8 (± 31.2)	4.0	$[0.9,7.1]$	35 / 15 / 30
150	37.2 (± 28.3)	34.9 (± 33.4)	2.3	$[-0.7,5.3]$	34 / 23 / 23
300	28.4 (± 27.1)	23.5 (± 34.5)	4.9	$[1.1,8.7]$	38 / 17 / 25
1000	38.6 (± 26.8)	34.5 (± 35.2)	4.1	$[-0.4,8.6]$	35 / 22 / 23

Appendix

Table 11: JSSP deployment results for the families selected in Table 9 .

\bar{\Delta}_{g}

is reported as mean with standard deviation (%). Difference and CI give the mean paired difference and its pointwise confidence interval in percentage points. W/L/T gives win, loss, and tie counts for SAGE against the initializer.

Figure 6: Relationship between the integer feasible set $S$ , its LP relaxation $P$ , the set $\operatorname{conv}(S)$ , a valid inequality that removes the fractional LP optimum (useful), and an optimality-preserving inequality that may remove some feasible points while keeping the optimal value.

Figure 7: Change over time (up to 2000 s) of the mean stabilized relative gap improvement

\bar{\Delta}_{g}(t)

after adding the selected SAGE acceleration inequality family to the baseline MILP for TSP, MCND, CWLP, JSSP, PDPTW, IMO6, and SHUC. The solid line is the mean across test instances at each wall-clock time and the shaded band indicates one standard deviation (

\sigma

). Positive values mean the augmented model has a smaller optimality gap at that wall-clock time.

Problem	Separated / Total	Rate (%)
TSP	54/54	100.0
MCND	72/81	88.9
CWLP	36/36	100.0
JSSP	80/80	100.0
PDPTW	165/165	100.0
IMO6	34/34	100.0

Appendix

Table 12: Held-out test-set LP separation rate of the selected SAGE acceleration inequality family.

Problem	Setup (s)	Baseline (s)	SAGE (s)	Solves	Solves with setup
TSP	0.94	1063.8	760.3	238	238
MCND	0.006	640.7	627.1	5276	5278
CWLP	0.97	220.5	11.4	345	347
JSSP	0.46	1886.5	1846.1	1782	1803
PDPTW	0.08	2000.0	1962.7	1933	1935
IMO6	10.55	1594.5	1555.1	1828	2496

Appendix

Table 13: Discovery payback at

g\leq 10^{-3}

on reserved test instances. Setup is the mean added deployment setup time. Solves is the number of deployments whose solver time savings recover the search budget. The last column charges the added setup time to SAGE as well.

Method	Mean stabilized relative gap improvement (%)
Automatic ( $-1$ )	$34.3\pm 29.3$
Deterministic concurrent (4)	$27.6\pm 33.1$

Appendix

Table 14: TSP sensitivity to the Gurobi continuous solution method.

Problem	5 s	10 s	50 s	150 s	300 s	1000 s	2000 s	Average
RNTD	$18\pm 35$	$-50\pm 197$	$24\pm 17$	$24\pm 19$	$25\pm 20$	$28\pm 20$	$23\pm 19$	13

Appendix

Table 15: RNTD test mean stabilized relative gap improvement

\bar{\Delta}_{g}\ (\%)

. Mean

\pm\sigma

is reported at each checkpoint.

Target gap	B/A	SGM speedup
$10^{-5}$	9/12	$4.2\times$
$10^{-4}$	9/12	$4.2\times$
$10^{-3}$	9/13	$4.2\times$
$10^{-2}$	44/44	$2.7\times$
$10^{-1}$	44/44	$1.0\times$
Average	23.0/25.0	$3.3\times$

Appendix

Table 16: RNTD time to target results. B/A counts the baseline and augmented runs that reach the target.

Problem	Static literature valid inequalities	SAGE families
CWLP	$3.01\times$	$4.02\times$
JSSP	$1.91\times$	$3.33\times$
MCND	$1.01\times$	$1.01\times$
TSP	$2.57\times$	$2.87\times$

Appendix

Table 18: Mean SGM speedup for static literature valid inequalities and SAGE acceleration inequality families. Each value is averaged over the same five target gaps used in Table 3 .

Solver	Parameter	Default	Role
Gurobi	MIPGapAbs	1e-10	Absolute optimality gap tolerance.
Gurobi	Presolve	-1	Automatic presolve control.
Gurobi	Cuts	-1	Automatic global cut generation control.
Gurobi	Heuristics	0.05	Target fraction of runtime for primal heuristics.
Gurobi	MIPFocus	0	Balanced MIP search focus.
Gurobi	Symmetry	-1	Automatic symmetry detection.

Appendix

Table 19: Important default solver parameters not otherwise listed in the experimental setup.

Figure 8: Gap trajectories over time for four representative TSP instances ( gr202 , kroB150 , kroA200 , and kroD100 ) from Reinelt (1991) . Orange: baseline MILP augmented with the selected SAGE acceleration inequality family. Blue: baseline MILP.

Figure 9: Evolution of the solver’s best bound for four representative TSP instances. Blue lines: baseline MILP (reference). Orange lines: MILP with the selected SAGE acceleration inequality family.

Figure 10: PDI trajectories for the same four TSPLIB instances used in Figs. 8 - 9 . Lower curves are better. Orange: baseline + selected SAGE acceleration inequality family. Blue: baseline MILP.

Figure 11: Gap trajectories for four MCND instances where the selected acceleration inequality family slightly hurts the gap ( R-r18.9.dow , R-r15.6.dow , R-r15.3.dow , and R-r13.9.dow ). Orange: baseline MILP augmented with the selected SAGE acceleration inequality family. Blue: baseline MILP.

Benchmark	# Instances	Variables	Constraints
TSP	54	$15821.65\pm 15593.23$	$15931.00\pm 15655.59$
MCND	81	$24991.89\pm 17962.83$	$2485.22\pm 1330.64$
CWLP	36	$34398.00\pm 47121.26$	$420.22\pm 487.64$
JSSP	80	$21382.25\pm 31271.97$	$42046.88\pm 62013.04$
PDPTW	165	$11090.00\pm 0.00$	$4565.00\pm 0.00$
IMO6	34	$20759.50\pm 22078.88$	$7524.50\pm 7842.23$

Appendix

Table 20: Scale of held out benchmarks before solver presolve. Variable and constraint counts are reported as mean

\pm

sample standard deviation for the baseline formulations and exclude the SAGE families.

Synthetic source for $D_{imp}$ / $D_{adm}$	Variables	Constraints
TSP synthetic	$16737.80\pm 15413.50$	$16852.61\pm 15473.23$
MCND synthetic	$24988.19\pm 17868.66$	$2485.22\pm 1322.35$
CWLP synthetic	$19690.59\pm 31363.09$	$420.22\pm 449.19$
JSSP synthetic	$21382.25\pm 31075.91$	$42046.88\pm 61624.24$
PDPTW synthetic	$8645.00\pm 1038.60$	$3627.50\pm 548.92$
IMO6 synthetic	$41740.75\pm 44521.34$	$14863.25\pm 15606.55$

Appendix

Table 21: Synthetic development source scale for

D_{imp}

and

D_{adm}

. Variable and constraint counts are reported as mean

\pm

population standard deviation over the size pool of each generator.

Parameter	DeepSeek	Gemini 3 Pro	GPT-5.1
Model	deepseek-reasoner	google/gemini-3-pro-preview	gpt-5.1
Maximum output tokens	10,000	10,000	10,000
Temperature	1.0	1.0	1.0
Frequency penalty	0.0	0.0	0.0
Presence penalty	0.0	0.0	0.0
Total input tokens	$\sim$ 26 M	$\sim$ 19 M	$\sim$ 28 M

Appendix

Table 22: LLM API settings and estimated token costs used for all SAGE experiments. Costs use Jan 2026 OpenRouter list prices. The Gemini 3 Pro API identifier and pricing follow OpenRouter OpenRouter (2025) .

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

Strategy-Aware Optimization Modeling with Reasoning LLMs
May 4, 2026Ruiqing Zhao, Fengzhi Li, Yuan Zuo +5RL for Code Generation LLM-Based Program Synthesis
School of Computer Science and Engineering, Beihang University, Beijing, China · JIUTIAN Research, Beijing, China · MIIT Key Laboratory of Data and Decision Intelligence, Beihang University, Beijing, China
FormuEvo: LLM-Guided Evolution for Discovering Solver-Efficient Mixed-Integer Programming Formulations
Aug 24, 2026Haofeng Yuan, Jianing Peng, Jieyi Bi +3Large Language Model-Guided Optimization Mixed-Integer Linear Programming
Department of Automation, BNRist, Tsinghua University · College of Computing and Data Science, Nanyang Technological University · School of Computing and Information Systems, Singapore Management University
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.

May 4, 2026J/K move · Enter open · S save

Strategy-Aware Optimization Modeling with Reasoning LLMs

Ruiqing Zhao, Fengzhi Li, Yuan Zuo, Rui Liu+4

School of Computer Science and Engineering, Beihang University, Beijing, China · JIUTIAN Research, Beijing, China · MIIT Key Laboratory of Data and Decision Intelligence, Beihang University, Beijing, China

RL for Code Generation LLM-Based Program Synthesis Constrained Optimization Natural Language to Optimization Modeling

Open paper AskPDF arXiv

Large language models (LLMs) can generate syntactically valid optimization programs, yet often struggle to reliably choose an effective modeling strategy, leading to incorrect formulations and inefficient solver behavior. We propose SAGE, a strategy-aware framework that makes Modeling Strategy explicit in both data construction and post-training. SAGE builds a solver-verified multi-strategy dataset and trains a student model with supervised fine-tuning followed by Segment-Weighted GRPO using a composite reward over format compliance, correctness, and solver efficiency. Across eight benchmarks spanning synthetic and real-world settings, SAGE improves average pass@1 from 72.7 to 80.3 over the strongest open-source baseline. With multiple generations, SAGE discovers more distinct correct formulations and improves component-level diversity at pass@16 by 19-29%. At the largest scale, SAGE produces more compact constraint systems with 14.2% fewer constraints than the baseline, consistent with solver-efficient modeling. Overall, these results show that making Modeling Strategy explicit improves automated optimization modeling. Code is available at https://github.com/rachhhhing/SAGE.

Abstract

Mixed-Integer Linear Programming

Explore similar work

Strategy-Aware Optimization Modeling with Reasoning LLMs

FormuEvo: LLM-Guided Evolution for Discovering Solver-Efficient Mixed-Integer Programming Formulations

Learning Early-to-Final Solution Consistency for MILP Acceleration