Reusable Solver Synthesis with Reinforcement Learning

Research output: · arXiv preprint

Comparison of incorrect global-best acceptance logic with the corrected current-state rule in generated simulated annealing code

RolePostdoctoral researcher and first author

Background

Code language models usually solve optimization problems one instance at a time. This work asks whether reinforcement learning can instead train a model to generate a standalone solver that is reused across a family of problems.

The main test bed is Synergistic Dependency Selection (SDS), a constrained combinatorial optimization problem designed so that plausible greedy strategies and superficially correct solver templates often fail.

Method

We fine-tuned Qwen2.5-Coder-14B-Instruct with Group Relative Policy Optimization (GRPO), a feasibility-gated reward, and light structural scaffolding. The model generates executable Python solvers rather than direct solutions. Training used 12 NVIDIA GH200 GPUs on the CSCS Alps supercomputer.

The work was developed with Gabriel Apaza, Milad Habibi, and Mark Fuge.

Semantic repair

The base model compares a proposed score with the global best score, while the RL-trained policy compares it with the current score and uses a constraint guard.
Adapted from Figure 4 of the paper. The base model often retrieves simulated annealing but misimplements its acceptance rule; the trained policy repairs that logic and adds active constraint handling.

Results

  • Best-of-64 base-model sampling reached a 28.7% mean gap to the global Virtual Best Solver on SDS; the trained policy reached 5.0%.
  • 99.8% of feasible outputs from the trained policy matched a constraint-aware simulated annealing structure.
  • A compile-once test reused one fixed generated solver per training seed across the full test split, reaching a 97.87% pass rate and a 4.34% mean gap.
  • Post-generation execution and search cost was 91 times lower than cumulative Best-of-64 evaluation in the reported comparison.

Limits

SDS is a controlled test bed rather than a replacement for established operations-research benchmarks. Results on Job Shop Scheduling provide narrower evidence beyond SDS, but the method still requires domain-specific solver contracts and reward design. Ablations also show sensitivity to feasibility scaffolding and reward normalization.

Open artifacts