- 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 has many parameters (weights, the 0.25/0.75 split between the post-cut gap and the number of nodes explored, , , ) 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
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
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.