Research map / Large language models / Agents, code and math
$\texttt{STRCMP}$: Integrating Graph Structural Priors with Language Models for Combinatorial Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes STRCMP, a structure-aware LLM algorithm-discovery framework that prepends frozen GNN embeddings of bipartite CO graphs to a fine-tuned Qwen2.5-Coder-7B and embeds it in an evolutionary code-refinement loop for MILP and SAT solvers.
Problem
LLM-based approaches for combinatorial optimization ignore the topological structure of CO problems, requiring many iterations and yielding suboptimal solver code for NP-hard MILP and SAT problems.
Approach
Condition an LLM's code generation on GNN-extracted structural embeddings of the problem's bipartite graph (prepended as a token-like vector), post-train it with SFT then DPO on solver-validated code, and run it inside an evolutionary refinement loop.
Key results
- On SAT, STRCMP reduces timeouts on Zamkeller from 18 (AutoSAT) to 4 and on PRP from 9 to 3 for the DPO-only/SFT-only variants, with solving time on PRP falling from 22967 s to 21146 s.
- STRCMP converges faster than AutoSAT and LLM4Solver in evolutionary search, and avoids the persistent oscillations seen in AutoSAT.
- On MILP, STRCMP is reported to maintain parity with L2B/HEM and LLM4Solver rather than clearly outperforming them.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace AutoSAT with STRCMP | SAT solver evaluation · CNP, CoinsGrid, PRP, and Zamkeller | number of timeouts: 32 -> 31 (CNP); 16 -> 17 (CoinsGrid); 9 -> 44 (PRP); 18 -> 5 (Zamkeller) | Mixed |
| add the GNN structural prior (ablation) | STRCMP · Zamkeller | number of timeouts: 14 -> 5 | Helped |
| add the GNN structural prior (ablation) | STRCMP · CNP | number of timeouts: 32 -> 31 | Helped |
| add the GNN structural prior (ablation) | STRCMP · CoinsGrid and PRP | number of timeouts: 16 -> 16 (CoinsGrid); 44 -> 44 (PRP) | No clear effect |
| use DPO-only post-training rather than the full post-training configuration (ablation) | STRCMP · PRP | number of timeouts: 44 -> 3 | Helped |
| use DPO-only post-training rather than the full post-training configuration (ablation) | STRCMP · CNP and CoinsGrid | number of timeouts: 31 -> 32 (CNP); 17 -> 16 (CoinsGrid) | Hurt |
| use DPO-only post-training rather than the full post-training configuration (ablation) | STRCMP · Zamkeller | number of timeouts: 5 -> 5 | No clear effect |
| use SFT-only post-training rather than the full post-training configuration (ablation) | STRCMP · Zamkeller | number of timeouts: 5 -> 4 | Helped |
| use SFT-only post-training rather than the full post-training configuration (ablation) | STRCMP · CNP and CoinsGrid | number of timeouts: 31 -> 33 (CNP); 17 -> 16 (CoinsGrid) | Mixed |
| use SFT-only post-training rather than the full post-training configuration (ablation) | STRCMP · PRP | number of timeouts: 44 -> 45 | No clear effect |
| remove the GNN structural prior (ablation) | STRCMP algorithm search · SAT benchmarks | optimization performance | Hurt |
| remove the GNN structural prior (ablation) | STRCMP algorithm search · SAT benchmarks | solution variability | Hurt |
Surprising findings
- The full STRCMP model (SFT+DPO) does not uniformly outperform its SFT-only and DPO-only ablations across all benchmarks, which the authors attribute to conflicts in post-training data.
- On MILP, STRCMP only matches rather than surpasses the NCO methods and LLM4Solver.
Limitations
- Full model does not uniformly beat its SFT-only or DPO-only ablations, suggesting post-training data conflicts.
- Structural prior gains on MILP are only parity with baselines.
- Theoretical results (information-theoretic upper-bound argument) are loosely connected to the empirical claims.
Experimental setup
Datasets: Set Covering Maximum Independent Set Multiple Knapsack MIK CORLAT Load Balancing Anonymous MILP SAT Competition PRP SAT Competition CNP CoinsGrid (Picat) Zamkeller (Picat)
Benchmarks: Set Covering Maximum Independent Set Multiple Knapsack MIK CORLAT Load Balancing Anonymous MILP SAT Competition PRP SAT Competition CNP CoinsGrid Zamkeller
Metrics: solving time primal-dual integral PAR-2 number of timeouts iterations to convergence
Baselines: L2B HEM NeuroSAT AutoSAT LLM4Solver
Builds on: FunSearch Evolution of Heuristics (EoH) DPO AutoSAT LLM4Solver
Closest papers by meaning
- CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization (AAAI 2026 · similarity 0.89)
- Structure-Aware Cooperative Ensemble Evolutionary Optimization on Combinatorial Problems with Multimodal Large Language Models (NeurIPS 2025 · similarity 0.88)
- EvoOptiGraph: Weakness-Driven Coevolution via Graph-Based Structural Generation for Optimization Modeling (NeurIPS 2026 · similarity 0.87)
- Large Language Models as End-to-end Combinatorial Optimization Solvers (NeurIPS 2025 · similarity 0.87)
- Towards General Algorithm Discovery for Combinatorial Optimization: Learning Symbolic Branching Policy from Bipartite Graph (ICML 2024 · similarity 0.87)
- ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.