acceptodds
Under review as a conference paper at ICLR 2027

Teaching LLMs to Generate Challenging MILP Instances via Solver Feedback

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–5 and post-cut gaps by 1.1–1.7 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.6. 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 publicly on acceptance.

Primary area:
reinforcement learning
Keywords:
Optimization Instance Generation, Solver-In-Loop RL, MILP, Large Language Models

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_2Q3UOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies generating hard instances for mixed-integer linear programs via large language models (LLMs), given a problem family and size. The LLM is trained to produce valid and varied instances of the requested size that are complex to solve. The complexity is measured by the gap remaining after root cuts and the number of branch-and-bound nodes explored. The method is mainly evaluated on the Capacitated Facility Location and Max-Cut problem families. The results show that the trained models produce instances with higher post-cut gaps and more explored branch-and-bound nodes than their base models, even for instances larger than those in the training set, and that the increase in explored nodes persists for the two solvers not used in training (HiGHS and Gurobi).

Critical strengths

Training an LLM from solver metrics such as post-cut gap and number of nodes explored via branch-and-bound is a novel and well-motivated approach. It also alleviates the need for seed instances. The paper will release the code of the generators of hard MILP instances for the Capacitated Facility Location and Max-Cut problem families. This addresses a real lack of training and benchmark instances, and these new hard instances could make learning-based methods less susceptible to overfitting.

Critical weaknesses

The experiments are not fully convincing as they do not compare the proposed approach against existing instance generators such as MILP-Evolve or against frontier models prompted to generate hard instances. I am also concerned about the capacity of the method to generalize to other problems (its effectiveness is only demonstrated on two of the three families it is trained on) and its ability to scale to large instances, since the data is fully written by the LLM.

Questions for authors
  • The reward RiR_i has many parameters (weights, the 0.25/0.75 split between the post-cut gap and the number of nodes explored, τ\tau, α\alpha, NrefN_\textrm{ref}) that seem arbitrarily chosen. How were the values of these parameters selected? And are the results sensitive to these parameters?
  • Does the size term in the reward have a significant impact on the size of the instances produced by the trained model? Wouldn’t relying only on the requested size in the generation prompt give similar results while enabling the generator to return instances with more diverse sizes?
  • Do you have insights on the importance of the model’s temperature in producing diverse instances? Would generating a few instances and keeping the hardest one improve the results of both your approach and the base models?
3 comments
AuthorsOpenReview ↗

Reply to Reviewer 2Q3U: Comparisons, generalization and scale weaknesses addressed

Thank you for this comment. We address the three points in turn.

Comparisons: The original manuscript compares proposed model generated instances with MILP-Evolve at matched size. It is part of public benchmarks in Figure 2 along with other benchmarks listed in Appendix G.8. Public instances of this size are mostly either trivial (about 10 nodes) or near the 50,000-node cap, while our instances span the range between. This is because these generators depend on seeds and can manipulate hardness near seed but cannot generate diverse problems of varying hardness. The manuscript also reported comparison with standard synthetic generators in Appendix G.6.

Importantly, we now compare with three frontier LLMs (Opus 5.5, Gemini 4 Argon, Gemini 3.8 Flash). They write valid instances reliably, but OptiScribe-12B needs 2.7–7.5× more median SCIP nodes on Max-Cut at every size, and more on CFL at three of four sizes (Appendix G.7).

Generalization: We extended evaluation on three families never seen in training (GISP, bin packing, network flow). Our 4B model (trained with the strict verifier writes valid GISP and bin-packing instances more often than its base, and its instances are harder on GISP at every size (1.3–2.8×) and on bin packing at 351–500 (median 184 vs 1 node), with no change on network flow (Appendix G.3). When bin packing and network flow are added to training (Appendix G.4), bin packing becomes much harder. (See W3 of Reviewer JUAW)

Scale: In the original manuscript we showed generalization by producing valid hard instances up to 2x training sizes i.e. train up to 225 and test on 500. Now we go beyond that up to 1000 variables and show that with a strict validity gate OptiScribe-4B can write harder instances reaching median SCIP nodes 1,144 at 751–1,000 variable brackets on CFL, and 50,000 on Max-Cut. Also, on Max-Cut the trained model reaches the 50,000-node cap in 124/128 instances. We report this in new Appendix G.5. (See W3 of Reviewer JUAW). Writing all data explicitly is affordable at this scale: a 1,000-variable instance needs about 3,000–3,400 tokens. A natural extension is for the model to write data rules (ranges, sparsity patterns, a seeded generator) instead of every number, so output length stays nearly constant as size grows, at the cost of per-instance control. We have now added this to the limitation paragraph.

AuthorsOpenReview ↗

Reply to Reviewer 2Q3U: Reward parameter ablations, size term details, temperature and best-of-k questions answered

Q1: Reward parameters. Thank you for this question. We ran five reward ablations and a repeat seed as suggested by the reviewer. Below we present the reasoning of selecting different reward weights and these ablation results.

The reward weights 0.70 / 0.15 / 0.15 were chosen to make hardness the main objective, with size and diversity as secondary terms. Within the hardness score, the node count gets 0.75 and the post-cut gap 0.25, because the gap alone cannot rank our instances. On Max-Cut the gap exceeds τ on 99.9% of valid instances, so the gap term is constant there and only the node count separates instances. The threshold τ = 0.10 sets the scale of the gap term where relative gaps between 0-10% earn proportionally more reward, and larger gaps earn the full gap reward. The exponent α = 3 sets how quickly the size reward falls as an instance misses the requested size, a 30% miss still scores 0.41. The node reference N_ref = 5,000 is the node count at which the node term saturates. We raised it from 1,000 before training, because 23–41% of valid CFL instances at 226–500 variables already saturated the node term at 1,000. Finally, the node cap of 50,000 bounds solver effort during training must exceed N_ref.

The original paper already compared N_ref = 5,000 with 50,000 (Appendix G.11) and varies the hardness weight (OptiScribe-4B-xH, Table 3).

New ablations: We retrained the 4B model with five different settings, changing one reward setting each time: (i) N_ref = 50,000 (default 5,000); (ii) a 0.5 / 0.5 gap/node split (default 0.25 / 0.75); (iii) α = 1 (default 3); (iv) hardness from the node count only, with no gap term; and (v) no diversity term. We also retrained the default with a second seed to measure run-to-run noise. Each run is compared with the default in 8 cells (CFL and Max-Cut, 4 sizes each), using paired tests with Holm correction. The second seed differs from the default in 1 of 8 cells, and ablations (i)–(iii) stay within this noise. Ablation (iv) makes Max-Cut harder at 171–500 variables. Ablation (v) makes instances harder in all 8 cells (CFL 2.9–15.8×, Max-Cut 1.2–2.1×), but they collapse to one shape as there is no diversity term. The results are therefore robust to the reward's numerical settings, and the diversity term trades some hardness for variety. Temperature is a sampling setting rather than a reward parameter, and we answer it under Q3. Details are added in Appendix G.15.

Q2: Size term. Thank you, this is a good suggestion. The reviewer is right that stating the size in the prompt is enough for an untrained model. The base models write instances inside the requested range in most cases: Gemma4-12B 99–100%, Qwen3.5-4B 80–99% on CFL. But once the model is rewarded for hardness, the easiest way to raise its reward is to generate larger instances than requested, since more variables generally mean more nodes. If we want to remove the size reward term, the validity gate must reject instances outside the requested range. Either way some form of size control is required.

Q3: Temperature and best-of-k.

(a) Temperature: We now sampled our 4B model at T = 0.7, 1.0 (the paper's setting) and 1.3. At high temperature, Max-Cut validity falls from 93% to 44% for the base and from 97% to 79% for OptiScribe-4B. Our 4B model trained using a strict parser (one that rejects outside bracket instances while training) stays at 99–100%. Trained models stay harder at every temperature. Median nodes at 171–225 for T = 0.7 / 1.0 / 1.3, strict parser 4B model vs base: CFL: 225 / 221 / 157 vs 61 / 47 / 15 and Max-Cut: 1,173 / 1,161 / 1,085 vs 269 / 220 / 87.

This shows that with fixed geometry in prompt, variety barely changes with Temp. Diversity is therefore better controlled through the request (size, density) than through temperature.

(b) Best-of-k: We computed exact best-of-k medians from the samples stored, with invalid draws counting as "no instance". On Max-Cut, using best-of-k the base model does not reach near trained models. No base sample reaches the trained median nodes at 111–225 (k ≥ 30 for Qwen and k ≥ 60 for Gemma, as one-sided 95% bounds). On CFL, the reviewer's intuition holds, the best of 2–4 base samples match one trained sample at 171–500. At equal k, the trained model stays ahead. OptiScribe-12B's best-of-4 median is higher than the bases in 11 of 12 cells, and lower in none.

However, the Best-of-k needs k generations and up to k solver calls per kept instance (29–32 solves at k = 32 on Max-Cut). The trained model needs one generation and no solver.

Dear Reviewer 2Q3U,

Since the rebuttal is going to end very soon, we humbly request you to take a look into our rebuttal. Please let us know if you have any further queries.

Thanks and best regards, Authors

Reviewer_JUAWOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes OptiScribe, which trains an LLM to generate hard MILP problems. It solves the generated instances and uses the cost of solving as several stages as the reward to score both the solvability and the hardness, measured by branch-and-bound nodes and post-cut relaxation gaps. The authors use this method to train some small models with GRPO. Experiments show increased instance difficulty over the base models on facility location and Max-Cut.

Critical strengths

This paper learns to generate challenging MILP problems, which is a critical and meaningful problem. This paper also proposes proper reward design.

Critical weaknesses
  • The training process need call the solver many times, which involve significant computational cost.
  • The authors should add some training-free baselines. For example, prompting a stong model such as Opus-5.5 or GPT-6-astra to generate challenging problems. It is very possible that such strong models can directly do this very well.
  • Evaluation covers only three problem families and at most 500 variables.
  • The proposed method is trivial GRPO. There is no much new insight.
Questions for authors

See weaknesses.

2 comments
AuthorsOpenReview ↗

Reply to Reviewer JUAW: Frontier Model Comparison, Computational Cost Explained, Size & Problem Family Expanded

W1: Solver cost. Yes, the training process needs solver calls. However, this is unavoidable as solver effort is the standard of hardness ( Please see reply to Q2 of Reviewer Pexv for details). Further, an important comparison is that our approach of training models is GPU intensive and solver calls have small contributions in total cost. For example a three-size curriculum makes about 11,000 solver calls of 1.1–1.6 s each: 3.4–5.2 CPU-hours of solving in total. The same runs use 21–25 GPU-hours (4B, 2× A100) and 73 GPU-hours (12B, 8× A100). Equally importantly, for comparison, we want to highlight that the SOTA models like MILP-Evolve reports 10 days on 60 parallel threads,of solver effort along with 9,044 GPT-4o prompts, most of which was spent on parameter search and filtering via solver calls. Therefore, we propose a more effective method to produce hard instances of a class of MILP problems.

W2: Frontier-model baselines. Thank you for this suggestion. We now add results from three frontier models (Claude Opus 5.5, Gemini 4 Argon and Gemini 3.8 Flash) using our exact evaluation prompts. We generate 128 instances in each MILP family (CFL and Max-Cut) × 4 size brackets, or 1,024 instances per model. We scored them with SCIP at default settings. We found that frontier models write 97-100% valid instances in every cell. As the table below shows, OptiScribe-12B's instances are 2.7-7.5x harder on Max-Cut at every size (median nodes), and harder on CFL at three of four sizes. At 171–225, Opus 5.5's instances need more nodes (516 vs 391). API cost was about USD 43 (Opus 5.5), USD 12 (Argon) and USD 4 (Flash) per 1,024 instances, against no per-call cost for a local 12B model.

FamilyModel111–170171–225226–350351–500
Max-CutGemini 4 Argon3499289972
Max-CutGemini 3.8 Flash1992287867
Max-CutClaude Opus 5.53154267910
Max-CutOptiScribe-12B1423641,0022,578
CFLGemini 4 Argon6275380910
CFLGemini 3.8 Flash65329367898
CFLClaude Opus 5.512516495125
CFLOptiScribe-12B1093917101,014

Therefore, our approach is at least comparable to frontier models without any per-call cost.

W3: More Families & Larger Instances. First, we already show generalization beyond the training range. Models were trained on at most 225 variables, and the 226–350 and 351–500 brackets are outside the training range, where the model still generates harder problems than base models. We now extend the evaluation in both directions to cover more families and larger number of variables.

Larger instances: Beyond 2× the training size, the current models do not perform well. We tested this by requesting 1,000-variable problems, 4× the largest training size. The reason for this generalization limitation was soft penalization of size term in the reward function. To eliminate this, we retrained Qwen3.5-4B with hard reject validity gate, i.e., rejecting every instance outside the requested size. The strict-gate model produces over 90% valid problems and writes harder instances reaching median SCIP nodes 1,144 at 751–1,000 variable bracket on CFL, and 50,000 on Max-Cut. Also, on Max-Cut the trained model reaches the 50,000-node cap in 124/128 instances. We report this in new Appendix G.5.

New families (inference only): We evaluated three families never seen in training: GISP, bin packing and fixed-charge multi-commodity network flow (4 sizes × 128 each). Against its base, OptiScribe-4B (trained with strict gate, as mentioned above) writes valid GISP and bin-packing instances more often, and its instances are harder e.g. 1.3–2.8× on GISP at every size (median ratio), and a median of 184 vs 1 node on bin packing at 351–500. Network-flow instances stay near the root for every model (Appendix G.3).

Training on more families: To show the framework applies to more families, we trained a 4B model on four families CFL, Max-Cut, bin packing and network flow, with GISP as held out family. Our model writes much harder bin-packing instances than its base: median 2,223 vs 1 node at 351–500, and 337 vs 1 at 171–225. It keeps the Max-Cut gain (5.4–9.8× median paired ratio up to 351–500) and leaves network flow near the root (median 2–6 nodes), although it writes valid instances two to four times as often as its base (74–88 vs 20–35 of 128) for it. The held-out GISP is 1.5–2.0× harder at 171–350 (Appendix G.4)

W4: Novelty beyond GRPO. We agree that we do not propose a new RL algorithm. We use standard GRPO as does recent verifier-in-the-loop works (Section 2.1). As discussed in the manuscript, our contribution is the asymmetric self-play framework and reward function design, not the optimizer. Any policy-gradient method could use the same reward.

Dear Reviewer JUAW,

Since the rebuttal is going to end very soon, we humbly request you to take a look into our rebuttal. Please let us know if you have any further queries.

Thanks and best regards, Authors

Reviewer_PexvOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper asks whether a language model can learn to write hard mixed-integer linear programming (MILP) instances using only solver feedback. Its main contribution is a seed-free asymmetric self-play loop. The language model acts as a challenger and a frozen branch-and-cut solver acts as verifier, so hardness stays on a fixed scale. The reward is read after presolve and root cuts, and it combines branch-and-bound nodes with the post-cut root gap. A validity gate blocks fake hardness, and size and diversity terms prevent gaming through scale or repeated structures. The trained OPTISCRIBE models generate instances directly from text, need no solver call at generation, and keep instruction control over family, size and difficulty. Experiments show OPTISCRIBE-12B and OPTISCRIBE-4B produce harder capacitated facility location and max-cut instances than their base models, with gains that hold under held-out solvers and at larger sizes. Generated instances fill difficulty gaps in public benchmarks and can support solver tuning. Multiple knapsack remains easy, and instances are limited to 500 variables.

Critical strengths
  1. The method is verified across multiple LLMs with difference scales and solvers.
Critical weaknesses
  1. The 3rd paragraph and 4th paragraph in the introduction is a bit hard to understand. I suggest to refine it as simple as possible to facilitate readers' understanding. After reading it, I sitll can not grap the core idea on how the whole method works. You should highlight the principles and brief the details, reduce the using of obscure vocabs and keep the main logic standing out and clear.
  2. I found the introduction is very hard to follow and understand. After reading the introduction, what is left to me is that the paper propose a method to train LLMs to generate hard MILP instances using the branch-and-bound as the feedback reward. But I can not understand how the authors achieved it.
  3. Generally, I found the writing is problematic, very hard to follow and sometimes the grammar issue occurs, for example: "Absolute Zero (Zhao et al., 2025) trains one model to propose and solve code-reasoning tasks, rewarding tasks it solves only some of the time." I can understand the meaning "only some of the time", but it is not academic nor formal written language. You should have better way of expressing it.
  4. The reward design is easily let the model to learn what SCIP verifier lacks, it probably will not learn the true difficulty of the instances. The diffifulty of the instances should not bind to one specific SCIP verifier. I do not think the author's method can find the hard instances as claimed as the core contribution of the paper.
  5. The node term saturates because r_node is clipped at 5,000 nodes, so instances beyond that point receive no additional reward. Training also imposes a 50,000-node cap and a 20-second wall-clock limit, while the validity gate requires a feasible solution and a finite optimum within those limits. This penalizes the hardest instances and biases the reward toward instances that can be solved within the limits.
  6. The reward measures only solver effort and does not measure instance realism or semantic plausibility. The model can therefore generate instances that are mathematically valid but weak in domain meaning. The paper covers only CFL, Max-Cut and multiple knapsack, and knapsack stays easy for every model, which shows that the reward cannot guarantee hardness learning for every family.
  7. Lacks of comparing with other hard instances generation methods
Questions for authors
  1. Why do you choose capacitated facility location (CFL) and max-cut as the target MILPs in this paper?
  2. "Hardness is scored from branch-and-bound nodes and the post-cut root gap", I am not sure this is a valid measure as a sorrogate reward to train the model. What is the relation between these metris and the true hardness of the problem instances?
  3. What do you mean by "which gives difficulty an absolute scale", what is the negative effect with non-absolute scale? What consequences it will cause?
  4. "Most MILP instance generators do not learn what makes an instance hard." This is not true. Some counter examples: [1] https://ieeexplore.ieee.org/document/11684623#1 [2] https://proceedings.iclr.cc/paper_files/paper/2025/hash/dc594b8712f5d3ea1904092d74739d25-Abstract-Conference.html
  5. What do you mean by "Training is also seedfree."
  6. Why use GRPO
4 comments
AuthorsOpenReview ↗

Reply to reviewer Pexv: Intro Updated, Hardness Clarified W1–W5 & Q2

W1–W2: Clarity of the introduction. Following the suggestion, we have improved the readability of specific introduction paragraphs and have done careful reading of the manuscript to iron out such issues elsewhere. The edited changes are given with yellow highlights in the revised manuscript.

W3: Writing and grammar. The sentence now reads: "Absolute Zero (Zhao et al., 2025) trains one model to do both tasks of proposing and solving code-reasoning, and rewards proposed tasks that the model solves at an intermediate rate." We also corrected "Challender" (Figure 1 caption), "wining" (Section 4.6) and "only differ only" (Appendix A.1) and made a full language pass of the manuscript.

W4: Dependence on SCIP. Firstly, we want to note that our existing tests in Section 4.3 and Appendix G.9 of the original paper show that hardness is not training solver dependent. There we solved the instances generated from the SCIP-in-loop model using two independent solvers, HiGHS (open source) and Gurobi 13.0.3 (commercial). There it is clear that a trained model generated problems require significantly more effort by both Gurobi and HiGHS solvers, which was not used in training. Further. we now also compute per-instance agreement between all three solvers: On the paper's instances, the Spearman correlation of node counts is:

-- SCIP vs HiGHS: 0.93–0.95 on CFL and 0.97–0.98 on Max-Cut.

-- SCIP vs Gurobi: 0.64–0.82 on CFL and 0.78–0.95 on Max-Cut.

So the three solvers largely agree on which instances are hard, and the model did not learn what SCIP lacks but learnt what Branch and Bound solvers lacked. We also note that section 4.4 and Figure 3 show exactly the solver specific failure and we designed the reward to avoid solver specific hardness learning by taking post-cut gap and node counts as reward.

The updated manuscript also contains results of a trained 4B model with Gurobi-in-the-loop instead of SCIP, with no other change. We compared the SCIP-trained and Gurobi-trained models under HiGHS, which neither model saw in training i.e. an independent referee. And as expected, the training method works with either solver in the loop: on Max-Cut, the three solvers agree on the new instances (pooled per-instance Spearman ρ 0.95–0.99). Thus, we argue that the proposed method does not bind difficulty to the solver.

Why SCIP: We use SCIP in the training loop because it is a state-of-the-art open-source MILP solver (Apache 2.0) and the standard solver in learning-for-MILP research (Gasse et al., 2019; Prouvost et al., 2020). Its plugin interface exposes every stage of the solve, including the bound after root cuts and the node count that our reward reads. It can also run as many parallel copies as training needs, without license limits. With Gurobi and HiGHS comparison, it is clear that hardness learnt is not solver dependent.

Q2 (Hardness): Firstly, measuring hardness by solver effort is standard with the community. Empirical-hardness research models an instance’s hardness as the running time of a given algorithm (Leyton-Brown et al., 2009). The community built problem set MIPLIB 2017 classifies instances by solver effort (Gleixner et al., 2021) only. Also literature on learning-for-MILP work reports branch-and-bound node counts under SCIP as the hardware-independent measure (Gasse et al., 2019). Similarly, instance generators also use the same quantities like Gurobi solving time and branching nodes in G2MILP (Geng et al., 2023), and solving time and node count in MILP-Evolve (Li et al., 2025). We also note that the paper (along with MILP-Evolve) suggested by the reviewer in Q4 (GAP-Gen) also used the same gap metric to classify hardness.

Therefore, we argue that the proposed method learns hard problems of community/research area standard and the hardness is not training solver dependent.

W5: Node clip and solver limits. From the training logs, we measured how many completions generated during training are affected by these limits and found that the limits almost never bind at the training sizes. In the submitted models, the 20 s kill affected at most 0.31% of solves per model, the 5,000-node clip at most 0.28% of valid instances, and the 50,000-node cap none. The 97.5th percentile of nodes during training was 153–3,309, below the clip. Our original manuscript included results with N_ref = 50000 in Appendix G.11 which shows that a larger reference does not have meaningful impact on the results and two N_ref setting results are similar inside the training range (Figure 2, 7).

AuthorsOpenReview ↗

Reply to reviewer Pexv: Comparison Strengthened with Frontier LLMs, Questions Answered: W6-W7; Q1, Q3

W6: Realism and knapsack.

Instance Realism or Semantic plausibility: We agree that the reward measures solver effort, not domain meaning, and our claims are limited to validity, difficulty and control. To our knowledge, no MILP instance generator measures semantic plausibility automatically. Doing so on a scale would need human judgement, which is an important direction for future work. Our LLM-based proposed generator offers a route to it. Because instances are written from natural-language instructions, a user can state the setting and structure in words. In Section 4.5 and Figure 4, we already show that the trained model follows such instructions. We now add two randomly selected instances in Appendix A.8 so that readers can inspect them directly.

Knapsack: To check this, we went one step further and trained the 4B model on more families to see if it shows the same pattern. We trained a new model using Qwen3.5-4B on four MILP families (Max-Cut, CFL: capacitated facility location, Bin Packing and FCMCNF: fixed-charge multi-commodity network flow). Training on bin packing, another packing family, does raise its hardness well above the base model's (Appendix G.4 in updated manuscript), so the difficulty is specific to knapsack under our prompt rather than to packing problems in general. In this run, the reward makes bin packing much harder than in the base model: a median of 2,223 vs 1 node at 351–500, and 337 vs 1 node at 171–225, where the base's instances are solved at the root.

W7: Comparison with other generators. We would like to guide the reviewer to the original paper where it compares with public collections and generators in section 4.2 and Figure 2. In Appendix G.8 we listed public benchmarks that include MILP-Evolve, D-MIPLIB, DIG-MILP and MIPLIB 2010/2017. In Appendix G.6 we compare it with standard synthetic generators as well.

Following the suggestion of another reviewer we now also compare the instance generation with three frontier models (Claude Opus-5.5, Gemini-4 Argon and Gemini-3.8 Flash) as added in Appendix G.7. OptiScribe-12B's instances need 2.7–7.5× more SCIP nodes than theirs on Max-Cut at every size, and more on CFL at three of four sizes.

Q1: Choice of CFL and Max-Cut. CFL models decisions in logistics, energy and network design. It is also one of MILP-Evolve's eight seed classes, and one of the standard synthetic generators we compare against (Appendix G.6). Max-Cut adds a graph family that MILP-Evolve's seeds do not cover.

Additionally, to address the reviewer's question, we further picked 3 more classes from MILP-Evolve's eight seed classes that our models never saw in training. Three classes are GISP: generalized independent set, Bin packing and FCMCNF: fixed-charge multi-commodity network flow. Our 4B model writes valid GISP and bin-packing instances more often than its base, and harder ones on GISP at every size (1.3–2.8×) and on bin packing at 351–500 (median 184 vs 1 node). It shows no change in network flow.

We also ran a new training run with four training families (CFL, Max-Cut, Bin packing and FCMCNF) added to Appendix G.4. Bin packing becomes much harder (337 vs 1 at 171-225, 25 vs 1 at 226-350 and 1846 vs 142 at 351-500), while network flow stays near the root. The held-out GISP is 1.5–2.0× harder than the base at 171–350.

Q3: Absolute difficulty scale. What we mean by absolute scale of difficulty is that the instance always receives the same difficulty score, because the verifier (which is a solver in our case) never changes during training. The "Difficulty scale" column of Table 1 shows this contrast. In challenger–solver self-play (Absolute Zero, R-Zero), difficulty is measured against a co-trained solver whose skill changes, so the difficulty is relative. A relative scale has three consequences that we avoid:

-- Scores from different training steps cannot be compared. One cannot tell whether the instances became harder or the reference solver changed,

-- The reward target moves during training, and

-- A score relative to other samples can be raised by changing size or format instead of difficulty, since larger instances look harder.

With a fixed verifier, a reported node count means the same at every checkpoint, for every model, and for anyone who resolves our instances.

AuthorsOpenReview ↗

Reply to reviewer Pexv: Q4–Q6

Q4: Learned generators and GAP-Gen. By “do not learn” we meant that these generators do not learn hardness in their model weights from solver feedback directly. Their difficulty comes from seed instances or from search and filtering. We have revised the sentence: “Most MILP instance generators do not train the generator on a hardness signal directly. Their difficulty is set by hand, or inherited from seed instances, or reached by search and filtering after generation.” Reference [1], GAP-Gen (BigDIA 2026, contemporaneous with our submission), fine-tunes a seed-based generator offline on existing instances ranked by root integrality gap. Its own outputs are never scored by a solver. OptiScribe instead scores every instance it generates during training and needs no seed instances. We have added GAP-Gen to Table 1 and Section 2.2.

Q5: Seed-free training. Seed-based generators such as G2MILP, ACM-MILP and MILP-StuDio start from a set of existing instances of the target family and edit them (Table 1, column "Input at generation"). "Seed-free" means we use no such instances. No instance corpus is edited, imitated or used as a hardness target. As the introduction states in paragraph 5, each prompt contains only one short formatting exemplar, drawn from a fixed pool of three per family (Appendix A.6). The exemplar shows the output format and is never edited.

Q6: Choice of GRPO. GRPO is an established technique for reward-based reinforcement learning. We note that GRPO is also the standard choice in recent verifier-in-the-loop work (section 2.1). As discussed in the original manuscript our contribution is the reward and the verifier, not the optimizer, any policy-gradient method could use the same reward.

Reviewer_PexvOpenReview ↗

React to authors response

The response from the authors partially addressed my concerns. I will raise my score to 2.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.