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

May 8, 2026cs.LG

MathConstraint: Automated Generation of Verified Combinatorial Reasoning Instances for LLMs

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.

Viresh Pati, Zhengyu Li, Piyush Jha +3

Georgia Institute of Technology, USA · KNOWIDEA Technologies

Combinations Constraint Satisfaction Satisfiability Structural Constraints

Ask PDF

Jul 2, 2026cs.AI

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

Most LP-from-text benchmarks are static datasets of word problems written and labeled by hand. Once such a dataset is released, its size is fixed, its difficulty is fixed, and every problem can leak into the training data of future LLMs. We present \textbf{A

^{2}

utoLPBench}, a benchmark for testing LLM-driven agents on linear programming problems written in plain text. We first pick a feasible point and dual, then write down a problem for which that point is optimal and the objective value is known. The answer is known by construction, with no solver call and no human annotator. The evaluation environment bundles a reference solver-critic baseline and a Docker image whose usage instructions are written for an LLM-driven agent to read. With these in place, any agent can run the benchmark and get a calibrated score with one command. Because the benchmark is a generator rather than a fixed dataset, it has properties no fixed dataset can match: an unlimited supply of fresh problems, a difficulty knob set by

(n,m)

, ground-truth answers correct by construction, low LLM-side cost per problem relative to human authoring, repeatable scores across independent batches, and resistance to training-data leakage when fresh post-cutoff seed ranges are used.

Shuo Ren, Yaohui Han, Yifan Shi +6

The Chinese University of Hong Kong

Agentic Benchmarks Large Language Model Benchmarks Reinforcement Learning Baseline Training Data Construction

Ask PDF

Jul 29, 2024cs.AI

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

Optimization problems are pervasive in sectors from manufacturing and distribution to healthcare. However, most such problems are still solved heuristically by hand rather than optimally by state-of-the-art solvers because the expertise required to formulate and solve these problems limits the widespread adoption of optimization tools and techniques. We introduce a Large Language Model (LLM)-based system designed to formulate and solve (mixed integer) linear programming problems from their natural language descriptions. Our system can develop mathematical models, write and debug solver code, evaluate the generated solutions, and improve efficiency and correctness of its model and code based on these evaluations. OptiMUS is designed as a productivity tool for optimization practitioners who understand the problem domain and can describe it precisely, but seek to accelerate the modeling and implementation workflow. OptiMUS-0.3 utilizes a modular structure to process problems, allowing it to handle problems with long descriptions and complex data without long prompts. Experiments demonstrate that OptiMUS-0.3 outperforms direct-prompting baselines by over 43% on easy and 18% on hard instances. It remains competitive with fine-tuned specialist models on benchmark problems, and outperforms them on real-world case studies (28.6% vs. 0%) where fine-tuned models fail to generalize. Ablation studies show that modular architecture with error correction is central to these gains. A key finding is that system architecture is a stronger driver of performance than model capability. Structured decomposition with targeted error correction enables weaker models to match stronger models under naive prompting, and remains competitive with fine-tuned specialist models without retraining costs.

Ali AhmadiTeshnizi, Wenzhi Gao, Herman Brunborg +3

a School of Management Science and Engineering, Stanford University, Stanford, California 94305 · b Institute for Computational and Mathematical Engineering, Stanford University, Stanford, California 94305

Optimization Modeling Solvers

Ask PDF

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