Teaching LLMs to Generate Challenging MILP Instances via Solver Feedback

Jitin Singla; Parikshit Pareek; Pratik Jawanpuria; Parag Singla

cs.AISep 29, 2026

Teaching LLMs to Generate Challenging MILP Instances via Solver Feedback

Authors: Jitin Singla, Parikshit Pareek, Pratik Jawanpuria, Parag Singla

Organizations: IIT Roorkee · IIT Bombay · IIT Delhi

Abstract

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.

Figures & tables

Method	Artifact	Difficulty Signal	Difficulty	Learns	Input at	Solver at	Text
Method	Artifact	Difficulty Signal	Scale	Hardness	Generation	Inference	control
Verifier-in-the-loop RL
Absolute Zero	Code task	Solver success rate	Relative	✓	Past tasks	✓	✗
R-Zero	Question	Majority agreement	Relative	✓	None	✗	✗
STP	Conjecture	Prover pass rate	Relative	✓	Seed theorems	✗	✗
MILP instance generators

Table 1: Comparison with verifier-in-the-loop RL and MILP instance generators.

		Capacitated Facility Location (CFL)				Max-Cut
Bracket	Arm	Parse $\uparrow$	Feas $\uparrow$	Nodes $\uparrow$	Gap $\uparrow$	Parse $\uparrow$	Feas $\uparrow$	Nodes $\uparrow$	Gap $\uparrow$
B1	Gemma-4-12B	78.9	72.7	22 [1, 456]	18 [1, 63]	100.0	85.9	41 [15, 91]	258 [182, 314]
	OptiScribe -12B-D	84.8	82.4	21 [1, 388]	18 [1, 55]	99.6	89.1	41 [15, 90]	260 [190, 315]
	OptiScribe -12B	94.1	91.8	109 [2, 755]	30 [2, 74]	100.0	89.1	142 [29, 297]	338 [237, 392]
B2	Gemma-4-12B	88.3	86.7	224 [1, 1873]	22 [4, 63]	99.6	91.8	81 [29, 182]	298 [237, 354]
	OptiScribe -12B-D	85.5	85.2	170 [1, 1587]	24 [2, 65]	99.6	96.9	85 [31, 193]	300 [238, 355]

Table 2: Main results for CFL and Max-Cut under SCIP.

256

instances per arm and bracket. Nodes is the median node count and Gap the median post-root-cut gap (

\times 10^{-3}

), both over feasible instances, with the

2.5

th and

97.5

th percentiles in brackets. Bold marks the best value.

		Max-Cut			Capacitated facility location
Bracket	Arm	Parsing (pp)	Nodes	Gap (pp)	Parsing (pp)	Nodes	Gap (pp)
111–170	OptiScribe -4B-D	$+4.69$	$4.96\times$	$+10.61$	$+14.84$	$2.23\times$	$-0.27$
	OptiScribe -4B	$+2.34$	$5.08\times$	$+10.74$	$+17.19$	$12.23\times$	$+1.14$
	OptiScribe -4B-xH	$+9.38$	$7.22\times$	$+13.40$	$+17.19$	$26.68\times$	$+2.75$
171–225	OptiScribe -4B-D	$-0.78$	$4.74\times$	$+10.40$	$+1.56$	$6.93\times$	$+1.13$
	OptiScribe -4B	$+0.78$	$5.26\times$	$+11.02$	$+1.56$	$15.63\times$	$+1.45$

Table 3: Qwen arms against untrained Qwen3.5-4B under SCIP. Parsing and median post-root-cut gap are differences in percentage points (pp). Nodes is the ratio of median node counts.

128

completions per model and cell, feasible instances only. OptiScribe -4B-xH raises the hardness weight and drops the diversity term. Bold marks the largest value.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Family	Bracket	Geometry hint ( SIZE line)	$c$
CFL	76–110	about 8 depots and 12 customers	41
CFL	111–170	about 10 depots and 15 customers	41
CFL	171–225	about 14 depots and 13 customers	26
CFL	226–350	about 16 depots and 17 customers	29
CFL	351–500	about 20 depots and 20 customers	28
Multiple knapsack	76–110	not trained at this bracket

Appendix

Table 4: Geometry hint and capacity constant

c

by family and bracket. Multiple knapsack is not trained at 76–110: no screened geometry for that family branched at that size, so the cell is excluded from the curriculum rather than assigned a hint.

Statement	Meaning
MILP <family> <min\|max>	Three-token header with problem class, family name and optimization sense.
set S <size>	Index set $S=\{1,\dots,\|S\|\}$ .
par p[S,T]	Parameter table $p\in\mathbb{R}^{\|S\|\times\|T\|}$ , values given in the data block.
var v[S,T] [<lb> <ub>] <type>	Variable family $v_{ij}$ , $(i,j)\in S\times T$ , with type continuous , integer or binary . A bound is a number or a parameter entry indexed by the running indices of the family, e.g. dem[d] . Bounds are omitted for binary , which fixes them to $[0,1]$ .
obj <min\|max> <sum> + <sum>	Objective, a sum of terms such as sum i in S, j in T: c[i,j]*v[i,j] .
con <name>: for i in S{, j in T}: <lhs> op <rhs>	Constraint family with one row for every element of the product of the listed sets.

Appendix

Table 5: Statements of the index-set template: Each line of the structure block is one statement.

S

and

T

are declared index sets,

i\in S

and

j\in T

are their running indices, and op is one of <= , >= , = . Indices are bound by sum and for clauses; in a var statement, the running index of each set is its lowercase name.

Family	Geometry	$n$	$m$	Compact	Expanded	Ratio
Facility location	$\|F\|{=}8,\ \|D\|{=}12$	104	116	786	7,827	0.10
Facility location	$\|F\|{=}10,\ \|D\|{=}15$	160	175	962	12,279	0.08
Max-cut	$\|V\|{=}9$	90	162	438	6,401	0.07
Max-cut	$\|V\|{=}12$	156	288	585	11,727	0.05

Appendix

Table 6: Encoding length in characters:

n

and

m

are the numbers of variables and constraints after expansion. Compact is the index-set template including its data block, and Expanded writes every constraint explicitly. Ratio is Compact divided by Expanded.

Policy and optimization		Reward and solver
Base models	Gemma-4-12B-it, Qwen3.5-4B	$N_{\mathrm{ref}}$	$5{,}000$
Adaptation	LoRA, rank $16$	Node cap	$50{,}000$
Algorithm	GRPO, group $G=64$	Wall-clock kill (training)	$20$ s
Learning rate	$5\times 10^{-5}$	In-loop solver	SCIP 10.0
KL coefficient $\beta$	$0.1$	Evaluation-only solvers	HiGHS, Gurobi 13.0.3
Decoding	$T=1.0$ , top- $p=0.95$

Appendix

Table 7: Training and reward configuration. Settings are fixed across arms and rungs. Only the size-bracket schedule differs.

Family	Geometry	$n$	Bracket	Nodes	$H$	$\sigma_{H}$	$>$ 1 node (%)	Status
Facility location	$\|F\|{=}14,\|D\|{=}13$	196	171–225	48.5	0.426	0.155	100.0	A
	$\|F\|{=}12,\|D\|{=}7$	96	76–110	11.0	0.165	0.205	75.0
	$\|F\|{=}10,\|D\|{=}9$	100	76–110	9.0	0.251	0.203	75.0
	$\|F\|{=}13,\|D\|{=}7$	104	76–110	10.5	0.221	0.176	58.3
	$\|F\|{=}8,\|D\|{=}12$	104	76–110	7.0	0.173	0.124	100.0	✓
	$\|F\|{=}13,\|D\|{=}10$	143	111–170	38.5	0.399	0.170	91.7

Appendix

Table 8: Screened rung geometries: Each row is

12

constructed instances solved by SCIP in the training configuration.

n

is the variable count, which equals the realized count in every row. Nodes and

H

are medians over the

12

instances,

\sigma_{H}

is the standard deviation of

H

, and

>

1 node is the share of instances that branch. Status A marks the family’s target-bracket anchor, which sets the branching bar. ✓ marks the kept geometry,

\circ

a candidate that passed both conditions but lost the tie-break, and a blank a rejected candidate.

Explore similar work

MathConstraint: Automated Generation of Verified Combinatorial Reasoning Instances for LLMs
May 8, 2026Viresh Pati, Zhengyu Li, Piyush Jha +3Combinations Constraint Satisfaction
Georgia Institute of Technology, USA · KNOWIDEA Technologies
A $^{2}$ utoLPBench: An Auto-Generated, Agent-Friendly LP Benchmark via Inverse-KKT Construction
Jul 2, 2026Shuo Ren, Yaohui Han, Yifan Shi +6Agentic Benchmarks Large Language Model Benchmarks
The Chinese University of Hong Kong
OptiMUS-0.3: Using Large Language Models to Model and Solve Optimization Problems at Scale
Jul 29, 2024Ali AhmadiTeshnizi, Wenzhi Gao, Herman Brunborg +3Optimization Modeling Solvers
a School of Management Science and Engineering, Stanford University, Stanford, California 94305 · b Institute for Computational and Mathematical Engineering, Stanford University, Stanford, California 94305

May 8, 2026, cs.LGJ/K move · Enter open · S save

MathConstraint: Automated Generation of Verified Combinatorial Reasoning Instances for LLMs

Viresh Pati, Zhengyu Li, Piyush Jha, Rahul Garg+2

Georgia Institute of Technology, USA · KNOWIDEA Technologies

Combinations Constraint Satisfaction Satisfiability Structural Constraints

Open paper AskPDF arXiv

We introduce MathConstraint, a hard, adaptive benchmark for evaluating the combinatorial reasoning capabilities of LLMs. We combine constraint satisfaction problems with rigorous solver-based verification and design an adaptive generator to create instances that remain challenging as the LLMs improve in their reasoning capabilities. Unlike existing benchmarks that quickly saturate on fixed datasets or use LLM-as-a-judge for checking solutions,MathConstraint uses parameterized problem types that enable scalable generation of arbitrarily difficult and automatically verifiable instances. We release MathConstraint-Easy (

266

instances), on which frontier models achieve between

72.6\%

(gemini-3.1-flash-lite) and

87.6\%

(gpt-5.5) accuracy, and MathConstraint (

329

instances) on which the same models drop to between

18.5\%

(claude-4.6-sonnet) and

66.9\%

(gpt-5.5) accuracy, demonstrating the resilience of our benchmark generator against rapid progress in LLM reasoning capabilities. We evaluate 12 frontier and open-weight models with and without access to a sandboxed Python environment that includes generic SAT/SMT solvers. Tool access roughly doubles frontier accuracy on MathConstraint (mean

+28

pp; up to

+52

pp for claude-4.6-sonnet). Further, halving the tool-call budget from

8

4

rounds erases up to

37

points -- a sensitivity that most single-budget benchmarks miss. We release the generator, dataset, and evaluation harness as a robust environment for studying combinatorial reasoning and tool-use behavior under adversarially-tunable difficulty.

Abstract

Explore similar work

MathConstraint: Automated Generation of Verified Combinatorial Reasoning Instances for LLMs

A2^{2}2utoLPBench: An Auto-Generated, Agent-Friendly LP Benchmark via Inverse-KKT Construction

OptiMUS-0.3: Using Large Language Models to Model and Solve Optimization Problems at Scale

A $^{2}$ utoLPBench: An Auto-Generated, Agent-Friendly LP Benchmark via Inverse-KKT Construction