Graph-Grounded Optimization: Rao-Family Metaheuristics, Classical OR, and SLM-Driven Formulation over Knowledge Graphs
arXiv:2605.12204v1 [cs.DB] 12 May 2026
Madhulatha Mandarapu [email protected]
Sandeep Kunkunuru [email protected]
Abstract We propose graph-grounded optimization: a paradigm in which the decision variables, constraints, and objective coefficients of a real-world optimization problem are sourced from a property knowledge graph (KG) via Cypher queries, rather than supplied as free-form natural-language text or static tabular input. We motivate the paradigm by surveying recent LLM/SLM-driven optimization systems — OptiMUS, Chain-of-Experts, LLMOPT, OPRO, FunSearch, Eureka — none of which consume property graphs as the primary input modality. We instantiate the paradigm in the open-source samyama-graph database and evaluate seven real-world publicdomain KG-backed problems spanning drug repurposing (245K-node biomedical KG), clinical-trial site selection (7.78M-node trial registry), Indian supply-chain rerouting (5.34M-node OSM road graph), healthcare equity allocation (WHO/GAVI/IHME KG), economic–environmental grid dispatch, antimicrobial-resistance stewardship (NCBI AMRFinderPlus, 10.4K resistance genes), and wildfire evacuation routing (OSM Paradise, CA). We compare a portfolio of Rao-family metaheuristics (BMWR, Jaya, SAMP-Jaya, EHR-Jaya, Rao-1) against Google OR-tools (CP-SAT and GLOP) reference solvers. We find that (i) no single Rao variant dominates: BMWR wins on discrete-with-tradeoff and high-dim-with-hard-constraint problems while Rao-1 wins on continuous low-/mid-dim problems, empirically supporting a portfolio approach; (ii) OR-tools dominates on small linear/MILP-friendly sub-problems but cannot encode the non-linear objectives that emerge in several of the real-world settings; (iii) graph-grounded formulations surface data-quality issues (missing properties, degenerate aggregates) that purely text-formulated optimizations would silently mask.
1
Introduction
Real-world optimization problems in healthcare, supply chain, energy, and public health rarely arrive as a clean mathematical statement. The constraints — drug-target interactions, clinical-site capacity profiles, freight network topology, regional health-workforce density — live in operational databases and increasingly in property graphs that integrate heterogeneous data sources. Yet the prevailing modern interface to optimization is still either a domain-specialist hand-written mathematical program or, increasingly, a large language model that ingests a free-form problem description and emits a Mixed-Integer Linear Program (MILP) [AhmadiTeshnizi et al., 2024b, Xiao et al., 2024, Jiang et al., 2025]. The text-to-MILP pipeline has two limitations relevant to industrial deployment. First, the natural-language description is itself a lossy encoding of the underlying data; constraints expressed numerically in the source graph become approximated by phrases that the LLM must disambiguate. Second, when the underlying data changes — a new drug appears in the catalog, a hospital site
1
reports updated capacity — the human-readable description must be re-edited and the formulation re-prompted, breaking the operational loop. Contributions.
This paper makes four contributions:
1. We introduce graph-grounded optimization (Section 3): a paradigm in which the decision variables, constraints, and objective coefficients are sourced from a property graph via Cypher queries. We define two implementation patterns (per-evaluation Cypher and pre-materialized aggregates) and characterize when each applies. 2. We provide an open-source reference implementation in samyama-graph, including a CypherProblem primitive with memoization and a custom-substitution hook for dynamic selection-set semantics. 3. We construct a 7-problem evaluation suite over real public-domain KGs spanning 19.7K to 7.78M nodes (Section 4), including OSM-derived road graphs of 5.34M and 12.6K nodes for India-wide freight routing and Paradise, CA wildfire evacuation respectively. Sources, licenses, scales, and reproduction recipes are documented in the released artifact. 4. We benchmark a portfolio of five Rao-family metaheuristics against Google OR-tools reference solvers (CP-SAT, GLOP) on all seven problems (Section 5). Across these problems no single Rao variant dominates: the winner depends on (problem type, dimensionality, constraint structure) in ways that justify carrying a portfolio.
2
Related Work
LLM- and SLM-driven optimization. OptiMUS [AhmadiTeshnizi et al., 2024b] introduces a modular agentic pipeline (modeler, code-writer, debugger, evaluator) that translates natural-language problem descriptions into MILP formulations solved by Gurobi or CPLEX; subsequent versions [AhmadiTeshnizi et al., 2024a] add a connection graph and improve robustness. Chain-of-Experts [Xiao et al., 2024] uses multi-agent decomposition with terminology / modeling / programming / code-review experts and forward-thought / backward-reflection loops. LLMOPT [Jiang et al., 2025] introduces a five-element formulation, KTO alignment, and self-correction with a fine-tuned Qwen-14B base. A different paradigm uses the LLM as the optimizer itself : OPRO [Yang et al., 2024] prompts the LLM to propose solutions from a meta-prompt of (solution, score) pairs; FunSearch [Romera-Paredes et al., 2024] evolves program code via an LLM-evaluator loop; Eureka [Ma et al., 2024] evolves RL reward functions. The whitespace. Across these systems — and across the LLM4Opt and awesome-fm4co catalogs at the time of writing — no published method consumes a property graph as the primary input modality. KG+LLM systems [Jin et al., 2024, others, 2025] target question answering and graph reasoning, not optimization formulation. This paper fills the intersection. Rao-family metaheuristics. The Rao family [Rao, 2016, 2024, 2025] is a metaphor-free lineage of population-based metaheuristics derived from TLBO [Rao et al., 2011]. We use Jaya, Rao-1, BMR, BWR, BMWR, SAMP-Jaya [Rao and Saroj, 2017], EHR-Jaya [Wang et al., 2022], and
2
QO-Rao [Rao and Saroj, 2020], comparing against Google OR-tools CP-SAT and GLOP [Google] as the classical baseline.
3
User / CLI
1
Loader (Python / Rust)
Public-domain source (OSM PBF, NCBI catalog, WHO TSV, CSV, .sgsnap)
samyama::graph::GraphStore (in-memory property graph)
samyama::query::QueryEngine (Cypher executor)
Problem impl (CypherProblem or custom)
samyama_optimization::*Solver (BMWR / Rao-1 / ...)
OR-tools (Python) CP-SAT / GLOP
spec.json
results.csv
or_tools_result.json
cargo run --release --example <demo>
Phase 1 — KG construction
2
fetch / read primary data rows / records
4
3
create_node(:Label), set_property, create_edge NodeId / EdgeId
5
Phase 2 — KG sanity queries
6
execute("MATCH (n:Label) RETURN count(n)") scan / index lookup
7
RecordBatch
8
counts (drugs, sites, pathogens, ...)
9
Phase 3 — pre-materialise + spec export
10
execute(per-candidate aggregate Cypher) scan + aggregate
12
11
per-(candidate, target) values
aggregate arrays
13
write spec.json (candidates, targets, params)
14
construct (Cypher template OR precomputed arrays)
15
Phase 4 — metaheuristic optimization (5 solvers × N seeds) loop
[for each (solver, seed)] objective(x) per population evaluation
alt
16
[CypherProblem (p1)] execute(template with $x_i substituted) Cypher scan / aggregate
19
17
18
scalar
20
f(x)
[Pre-materialised (p2, p3, p4, p5, p6, p7)] arithmetic over precomputed arrays 21
22
OptimizationResult (best_variables, best_fitness, history)
f(x)
23
write per-(solver, seed) record
24
Phase 5 — OR-tools LP/ILP reference python or_tools_pN_*.py spec.json
25
read
26
build CP-SAT/GLOP model, solve 27
28
User / CLI
Loader (Python / Rust)
Public-domain source (OSM PBF, NCBI catalog, WHO TSV, CSV, .sgsnap)
samyama::graph::GraphStore (in-memory property graph)
samyama::query::QueryEngine (Cypher executor)
Problem impl (CypherProblem or custom)
samyama_optimization::*Solver (BMWR / Rao-1 / ...)
spec.json
OR-tools (Python) CP-SAT / GLOP
write or_tools_result.json (status, optimum, assignment)
results.csv
or_tools_result.json
Figure 1: Generic graph-grounded optimization architecture shared by all seven problems. A loader populates the GraphStore from a public-domain source; the QueryEngine runs Cypher to sanity-check the KG and to pre-materialize aggregates; a Problem implementation (Pattern A or B) exposes the per-evaluation objective to the metaheuristic solver. OR-tools consumes the same spec.json as the LP/ILP reference.
4
3
Method: Graph-Grounded Optimization
3.1
Definition
A graph-grounded optimization instance is a tuple (G, x, c, f, g) where • G is a property graph in samyama-graph (or any Cypher-compliant store); • x is a decision vector (continuous, integer, or mixed) of dimension d; • c : x → R≥0 is a constraint oracle implemented as a parameterized Cypher query returning a violation degree; • f : x → Rk is an objective vector implemented as one or more parameterized Cypher queries returning scalars (k = 1 for single-objective, k > 1 for multi-objective); • g is optional graph-derived metadata (label cardinalities, degree distributions) made available to the solver as a warm-start hint. The decision vector is substituted into the parameterized Cypher at each evaluation. Two patterns implement this:
3.2
Pattern A: CypherProblem per-evaluation
The decision vector is converted, for each evaluation, into a literal substitution of the Cypher template; the modified query is executed against the graph. We provide a custom-substitution hook with_subs for dynamic selection-set semantics (e.g., the decision vector indexes a candidate list and a comma-separated list literal is interpolated into a Cypher IN clause). A 64-bit hash of the quantized decision vector keys a memoization table. Pattern A is required when the constraint or objective depends dynamically on the selected subset — for instance, when a side-effect penalty sums over only those drugs that the optimizer currently selects.
3.3
Pattern B: Pre-materialized aggregates
A single Cypher query at startup pulls per-candidate aggregates (e.g. trial count per site, physician density per country) into Rust-side arrays. The objective then evaluates in pure Rust over the precomputed arrays at microsecond latency per evaluation. Pattern B is the correct engineering choice when the relevant aggregates are static across decision-vector values. Empirically (Section 5) Pattern B is ∼ 350,000× faster per evaluation than Pattern A on a 7.78M-node KG; both are valid graph-grounded since the KG remains the source of truth.
4
Seven Real-World Problems
Table 1 summarizes the seven public-domain KGs used. Detailed schemas, Cypher queries, license terms, and reproduction commands are in the released artifact at git.samyama.ai/Samyama.ai/ samyama-research/papers/paper8-graph-grounded-optimization/.
5
#
Problem
Data source
Scale
P1 P2 P3 P4 P5 P6 P7
Drug repurposing Trial site selection Supply chain rerouting Healthcare allocation Grid dispatch AMR stewardship Wildfire evacuation
DrugBank+ChEMBL+SIDER ClinicalTrials.gov / AACT OSM India + UN/LOCODE WHO/GAVI/IHME smart-grid CSV sample NCBI AMRFinderPlus OSM Paradise CA
245K nodes 7.78M nodes 5.34M-node road graph 19.7K nodes 28 nodes 10.4K resistance genes 12.6K nodes
License CC0 public OSM ODbL open open public domain OSM ODbL
Table 1: Real-world problems used in the evaluation. All KGs are public-domain or open-license; CARD was excluded for license reasons and replaced with NCBI AMRFinderPlus. Each problem is posed in a manner consistent with the way the underlying domain practitioners would frame it. Briefly: P1 Pick k drugs maximizing target-gene coverage minus a SIDER side-effect penalty. Pattern A (dynamic $selected list). P2 Pick k trial sites maximizing total trial throughput plus a WHO-region diversity bonus. Pattern B (precomputed per-site). P3 Allocate fractions of city demand to ports such that total road-distance transport is minimized under port-capacity constraints and synthetic disruption (30% of ports halved). Pattern B with Dijkstra over the OSM road graph at startup. P4 Pick k countries to fund maximizing the deficit of physicians per 10,000 below the WHO threshold of 23, plus regional diversity. Pattern B. P5 Schedule 4 generators over 24 hours minimizing cost plus an emission-weighted penalty plus soft balance and ramp constraints (96-dim continuous). Pattern B. P6 Pick k antibiotic subclasses maximizing pathogen coverage minus a resistance-burden penalty (efficacy proxied by per-pair resistance-gene counts). Pattern B. P7 Allocate fractions of population per centroid to evacuation exits, minimizing total person-hours under exit-capacity constraints, with synthetic disruption (30% of routes inflated). Pattern B.
5
Results
We run each of five Rao-family solvers (BMWR, Jaya, SAMP-Jaya, EHR-Jaya, Rao-1) for three seeds with population size 30–60 and 100–500 iterations, against OR-tools CP-SAT or GLOP as the linear/MILP reference. Table 2 summarizes per-problem outcomes.
6
P Type
Best metaheuristic
P1 P2 P3 P4 P5 P6 P7
BMWR (3/5 hit opt.) BMWR (3/3 hit opt.) BMWR (1.26× LP) BMWR (3/3 hit opt.) Rao-1 (10× over second) BMWR (3/3 hit opt.; 22% gap) Rao-1 (8× over SAMP-Jaya)
disc. + tradeoff discrete cont. hi-dim discrete cont. mid-dim disc. + tradeoff cont. low-dim
Gap to LP OR-tools wall Notes 1.0× 1.0× 1.26× 1.0× 1.97× 1.0× 0.98×*
15 ms 40 ms 8.7 ms 11 ms 2.6 ms 93 ms 0.6 ms
BMWR uniquely explores SIDE BMWR consistent winner 800-dim with hard balance BMWR consistent winner 96-dim continuous LP-feasible Largest discrete gap Soft penalty allows slight relax
Table 2: Solver winners across the seven problems. “Gap to LP” is ratio of best metaheuristic transport / cost to OR-tools LP optimum on the comparable objective. *P7’s metaheuristic fitness falls slightly below the LP because soft balance penalties allow small constraint relaxation; the LP is the correct answer for deployment.
Solver portfolio: best metaheuristic / LP per problem 1.00
1.00
1.26
1.00
34
1.00
1.00
Rao-1
1.00
1.10
9.88
1.04
3.22
1.22
0.98
Jaya
1.10
1.04
13
1.03
63
1.25
1.06
SAMP-Jaya
1.00
1.05
20
1.03
138
1.24
7.79
EHR-Jaya
1.00
1.07
12
1.04
40
1.25
0.99
P1
P2
P3
P4
P5
P6
P7
2.00 1.75 1.50 1.25 1.00 0.75 0.50 0.25 0.00
log10(metaheuristic/LP)
BMWR
Figure 2: Solver portfolio across the seven problems. Each cell is log10 (best metaheuristic / LP optimum). BMWR wins P2/P3/P4/P6; Rao-1 wins P5/P7. SAMP-Jaya catastrophic on continuous (P5, P7). The pattern is not simply "Rao-1 for continuous, BMWR for discrete" — P3 (continuous 800-dim with hard balance constraints) flips back to BMWR.
7
Fitness (lower better)
Coverage (max 10)
P1: BMWR uniquely explores the SIDER tradeoff
10.50 10.25 10.00 9.75 9.50 9.25 9.00 8.75 8.50
BMWR EHR-Jaya Jaya Rao-1 SAMP-Jaya 0.0
0.5
1.0
1.5 2.0 SIDER cost
2.5
3.0
3.5
0.0 2.5 5.0 7.5 10.0 12.5 15.0 17.5 20.0
P6 AMR: BMWR matches OR-tools 3/3 (22% gap) OR-tools = -19.25
BMWR
Rao-1
Jaya
OR-tools GLOP = 221,052
106 BMWR
SAMP-Jaya
P5 grid dispatch: Rao-1 dominates by 10x
OR-tools LP = 546,071 Scalarised fitness
Transport cost (km × mtpa)
P3 supply chain: BMWR within 1.26x LP 107
EHR-Jaya
Rao-1
EHR-Jaya
Jaya
SAMP-Jaya
107
106
Rao-1
BMWR
EHR-Jaya
Jaya
SAMP-Jaya
Figure 3: Per-problem detail. Top-left P1: only BMWR scatters above the zero-SIDER baseline, exploring the tradeoff. Top-right P6: BMWR matches OR-tools CP-SAT exactly (3/3 seeds); other Rao variants ∼22 % short. Bottom-left P3: 800-dim continuous LP, BMWR within 1.26× LP, other variants 10–20×. Bottom-right P5: 96-dim continuous LP, Rao-1 dominates by 10× over second-best. Log scales on the bottom two.
5.1
The portfolio claim
Across the seven problems, BMWR wins four of seven and is in the top two on a fifth (P1, where its unique behavior is exploring the SIDER tradeoff). Rao-1 wins two of seven (P5 and P7, both continuous mid-/low-dim). No single Rao variant dominates; the winning solver depends on (problem type, dimensionality, constraint structure) in ways that match an interpretable pattern: • Discrete (cardinality-constrained) or discrete with a tradeoff term: BMWR. • Continuous, low- to mid-dimensional, no structured hard constraint: Rao-1. • Continuous, high-dimensional, with structured hard constraints (e.g., row-sums-to-1 balance): BMWR. This pattern empirically supports a portfolio approach: a deployment system should carry both BMWR and Rao-1 and select based on a problem classifier rather than commit to one algorithm.
5.2
Statistical significance (30 seeds, Wilcoxon signed-rank, Holm-corrected)
We re-ran every problem with 30 independent seeds on AWS on-demand ($0.18 total). Table 3 summarises per-problem means and the Holm-corrected pairwise Wilcoxon tests.
8
P P1 P2 P3-L P3-N P4 P5 P6 P7
type disc.+tradeoff discrete cont. hi-dim cont. hi-dim discrete cont. mid-dim disc.+tradeoff cont. low-dim
BMWR
Rao-1 EHR-Jaya
-8.94 -9.37 -16639 -15825 1.05M 225M 1.08M 285M -226.6 -224.9 17.2M 2.02M -19.20 -15.91 2290 2405 †
Jaya SAMP-Jaya
-9.66 -9.60 -16048 -16308 295M 298M 385M 419M -225.0 -225.4 14.8M 21.1M -15.76 -15.82 2642 3441
BMWR vs all sig.?
-9.70 only vs SAMP-Jaya -16385 all 4 541M all 4, p ≤ 10−8 726M all 4 -225.5 all 4, p ≤ 5 × 10−5 37.1M Rao-1 wins, p ≤ 2 × 10−8 -15.76 all 4, p ∼ 10−6 25928 tied with Rao-1 (pHolm = 0.088)
Table 3: Mean fitness per (solver, problem) across 30 independent seeds. † P1’s BMWR “higher” mean reflects unique exploration of the SIDER cost–coverage Pareto front rather than worse performance (Figure 3, top-left). Lower is better elsewhere. Updated headline. With 30 seeds and Holm correction, BMWR is statistically dominant on six of seven problems (P2, P3-L, P3-N, P4, P6, and tied with Rao-1 on P7). Rao-1 has a single clear win on P5 (96-dim continuous). The 3-seed pilot had suggested “Rao-1 for continuous, BMWR for discrete”. The 30-seed picture is rather BMWR is the workhorse; Rao-1 is the specialist for mid-dim continuous. Discrete-with-tradeoff problems (P1, P6) remain qualitatively distinct: P1 BMWR’s unique SIDER exploration shows up as a numerically higher mean despite finding the clinically more interesting Pareto point.
5.3
When OR-tools wins
For problems whose objective is linear and constraints are linear and hard, OR-tools dominates the metaheuristics by 2–3× in solution quality and 10–100× in wall time. The metaheuristics’ value emerges on (a) problems with non-linear objectives or constraints that the LP cannot encode (P5 nonlinear mode, P6 efficacy as inverse-of-count) and (b) what-if exploration where the soft-penalty formulation admits solutions that violate hard constraints in a controlled way (P7).
5.4
Phi-4 SLM baseline: zero-shot fails on every problem
We ran Microsoft Phi-4 (14B, December 2024) on a g4dn.xlarge GPU on-demand ($0.06 total) via Ollama, prompting it with each of the seven problems’ natural-language description and asking for self-contained ortools Python that reads our spec.json and emits a structured RESULT={...} line. The prompt deliberately did not include the schema or a sample of the spec — this is the standard OptiMUS / Chain-of-Experts regime where the LLM receives only a problem description, not the operational data structure.
9
P
Phi-4 status
Phi-4 obj
P1 P2 P3 P4 P5 P6 P7
TRIVIAL CRASH CRASH TRIVIAL CRASH CRASH TRIVIAL
0.00 — — 0.00 — — 0.00
wall (gen+exec) 133.5 s 31.6 s 29.8 s 34.3 s 43.1 s 33.0 s 32.7 s
failure mode hallucinated spec[’drugs’] (actual: candidates) wrong type assumption on a spec field KeyError: ’distances’ (actual key: distance_km) hallucinated spec[’countries’] (actual: names, regions, ...) ortools SumArray API misuse ‘list’ object has no attribute ‘get’ hallucinated field names → zero-flow trivially "optimal"
Table 4: Phi-4 zero-shot results across the seven problems. Four runs crash with KeyError / AttributeError on hallucinated field names; three runs report status: OPTIMAL but with objective zero because the loop over a non-existent key iterates zero times. The remaining contrast: BMWR solves 6/7 problems statistically optimally; OR- tools solves 7/7 exactly; Phi-4 zero-shot solves 0/7. Phi-4 produces fluent, syntactically valid ortools Python — it picks the right solver class, defines variables, sets up the objective and constraints, calls Solve(). The pathology is in the data-binding step: without seeing the actual schema, it invents plausible-sounding JSON key names that don’t exist in our spec, and neither the model nor the runtime surfaces a useful error: four runs crash on the first missing key, three look successful because the missing key just means an empty loop and a trivially feasible zero-objective solution. This is the central failure mode our paper argues against. Cypher-grounded optimization (BMWR, Rao-1, OR-tools-on-the-spec) reads the actual schema and so it solves; a purely text-based SLM pipeline does not have access to the schema and so the resulting code is silently mis-bound to the data. The conservative answer to “what does text-to-ortools cost when the data shape isn’t in the prompt?” is: every problem fails, half of them silently. Caveat. Providing Phi-4 a sample of the spec JSON would significantly improve its hit rate, but that step is precisely the graph-grounded discovery step our pipeline contributes. The paper’s claim is that this discovery step is required; the experiment confirms that without it, the SLM baseline is uncompetitive with both Rao-family metaheuristics and classical OR.
5.5
GPT-4.1 SLM baseline: succeeds only when naming aligns
We ran the same prompt against OpenAI gpt-4.1 (frontier model at the time of the run) over HTTPS. Cost: $0.05 total for all seven problems (2,761 prompt tokens + 5,732 completion tokens). Walltime: 90 s total.
10
P
GPT-4.1 status
obj
P1 P2 P3 P4 P5 P6 P7
OPTIMAL (trivial) OPTIMAL (exact) CRASH OPTIMAL (trivial) OPTIMAL (trivial) OPTIMAL (partial) OPTIMAL (exact)
0.0 16,639 — 0.0 0.0 20.0 2,215.752
True optimum –10.0 16,639 546,071 –226.6 221,052 –19.25 2,215.752
notes
hallucinated keys drugs, target_genes (real: candidates, ✓NL used canonical keys facilities, countries, trial_c TypeError: unhashable type: ’dict’ on schema assum hallucinated countries field hallucinated schema solved coverage exactly, omitted resistance penalty term ✓NL used canonical keys pop, capacity, travel_time
Table 5: GPT-4.1 zero-shot results. 2/7 problems solved exactly to the OR-tools LP optimum, 1/7 partial, 4/7 fail. Success on P2 and P7 is exact because the NL description coincidentally used the same key names as the JSON spec; failure on P1/P3/P4/P5 is because the description used narrative names that didn’t match. The pattern, not the score, is the finding. GPT-4.1 reliably produces compilable Python — no syntax errors, no garbled output, only one runtime crash — and when it succeeds, it succeeds exactly to the LP optimum. But its success rate is exactly the rate at which the NL description happens to use the canonical JSON key names. P2 and P7 use a list of named arrays in the description (“facilities, countries, trial_counts” and “n_centroids, n_exits, pop, capacity, travel_time”); both succeed exactly. P1 uses prose (“a list of (drug_id, side_effect_count) for 100 drugs”); GPT-4.1 invents spec[’drugs’] and silently returns objective zero. A description-writer aware of this could of course just hand-list the schema in the prompt — but that hand-listing step is precisely the graph-grounded schema-discovery step we contribute. The paper’s claim is sharpened by this: even a frontier SLM is gambling on naming conventions when forced to extract structure from prose, and the gamble is silent (a TRIVIAL OPTIMAL solution gives no signal that anything went wrong).
5.6
Reasoning + frontier SLMs (o3, gpt-5.5)
We ran the same prompt against OpenAI o3 (purpose-built reasoning) and gpt-5.5 (frontier general, April 2026). Combined cost $0.60. • o3 (2/7 exact). Same hit rate as gpt-4.1, with 3-5× the generation latency due to reasoning trace. 2 silent-trivial, 1 falsely declared INFEASIBLE, 2 runtime crashes. Reasoning depth does not close the data-binding gap when the failure mode is schema mis-binding. • gpt-5.5 (4/7 exact + 1 partial + 2 fail). Solves P2, P4, P6, P7 to the exact OR-tools optimum; gets P1’s coverage right but omits the SIDER penalty term; falsely declares P3 INFEASIBLE; gets P5 off by approximately 100× (likely missing the emission-weight scalar). Model capacity helps; the data-binding pathology is mitigated, not eliminated.
11
5.7
SLM-family summary
Solver
Correct
Spend
7/7 exact 6/7 statistically dom.
— —
SLM baselines (zero-shot, no schema in prompt): gpt-5.5 (frontier) 4/7 exact + 1 partial o3 (reasoning) 2/7 exact gpt-4.1 (frontier) 2/7 exact + 1 partial Phi-4 14B plain 0/7 Phi-4-mini-reasoning 3.8B 0/7
$0.47 $0.13 $0.05 $0.06 $0.37
OR-tools LP/CP-SAT BMWR (Rao family, 30 seeds)
Failure m
1 false INFEASIBLE; 1 off by ∼100×; 1 partia 2 trivial obj=0; 1 false INFEASIBLE; 2 cr 3 trivial obj=0; 1 crash; 1 partia 4 crashes + 3 trivial o 3 timeouts + 2 syntax + 1 garbled + 1 unclosed <th
Table 6: Cross-SLM summary. Both Phi-4 variants fail completely; GPT-4.1 succeeds only when the NL description happens to use the canonical schema names. The data-binding pathology is robust across model strength and reasoning capability.
5.8
Graph-grounding surfaces data-quality issues
In P4 we observed that the who_region property is missing from many :Country nodes in the loaded snapshot; consequently the diversity term |distinct regions in selected| is identically 1 across all candidate portfolios. This is detectable immediately by inspection of the Cypher result and shows up as a degenerate constant in the objective decomposition. An LLM-formulated optimization from a free-text description would silently encode “maximize diversity across regions” without surfacing that the data does not support the constraint. We argue this property — that data-quality issues become first-class signals — is a substantive advantage of the graph-grounded paradigm.
6
Discussion and Limitations
Limitations. (1) Seed counts in this report are small (2–3 per cell); a full Wilcoxon signed-rank evaluation with 30 seeds is ongoing. (2) We did not yet wire OptiMUS / Chain-of-Experts / LLMOPT as direct comparators; they consume natural-language descriptions and we report only OR-tools as the classical baseline. (3) For P3 the metaheuristic balance-penalty formulation does not exactly match the LP formulation; an augmented-Lagrangian outer loop would close this gap and is left for future work. Threats to validity. The hardcoded port and city lists in P3, and the centroid/exit selection heuristic in P7, are domain-reasonable but not the only choices. Robustness to alternative candidate selection rules is a natural extension.
7
Conclusion
We propose graph-grounded optimization, instantiate it in samyama-graph, and evaluate seven real-world public-domain KG-backed problems against Google OR-tools. The Rao-family metaheuristics, no single variant dominates: the portfolio claim is empirically supported. Graph-grounded formulations naturally surface data-quality issues that purely text-based formulations mask. All
12
KGs, loaders, and OR-tools baseline scripts are released under their respective open licenses at the project repository.
References Ali AhmadiTeshnizi, Wenzhi Gao, Lorenzo Brusca, and Madeleine Udell. OptiMUS-0.3: Connectiongraph guided multi-agent optimization-modeling. In arXiv preprint arXiv:2407.19633, 2024a. Ali AhmadiTeshnizi, Wenzhi Gao, and Madeleine Udell. OptiMUS: Optimization modeling using MIP solvers and large language models. arXiv preprint arXiv:2402.10172, 2024b. Google. OR-Tools: Google’s operations research tools. optimization. Accessed 2026-05-12.
https://developers.google.com/
Caigao Jiang, Xiang Shu, Hong Qian, et al. LLMOPT: Learning to define and solve general optimization problems from scratch. In International Conference on Learning Representations (ICLR), 2025. Weizhe Jin et al. Graph-constrained reasoning over knowledge graphs. 2024. Yecheng Jason Ma, William Liang, Guanzhi Wang, et al. Eureka: Human-level reward design via coding large language models. In International Conference on Learning Representations (ICLR), 2024. others. AGENTiGraph: An interactive agentic system for knowledge-graph-driven reasoning. arXiv preprint arXiv:2508.02999, 2025. R. Venkata Rao. Jaya: A simple and new optimization algorithm for solving constrained and unconstrained optimization problems. International Journal of Industrial Engineering Computations, 2016. R. Venkata Rao. BMR and BWR: Two simple metaphor-free optimization algorithms. arXiv preprint arXiv:2407.11149, 2024. R. Venkata Rao. Optimization of different metal casting processes using three simple and efficient advanced algorithms. Metals (MDPI), 15(9):1057, 2025. R. Venkata Rao and Anand Saroj. A self-adaptive multi-population based jaya algorithm for engineering optimization. Swarm and Evolutionary Computation, 2017. R. Venkata Rao and Anand Saroj. Quasi-oppositional based rao algorithms for multi-objective design optimization of selected heat sinks. Journal of Computational Design and Engineering, 2020. R. Venkata Rao, Vimal J. Savsani, and D. P. Vakharia. Teaching-learning-based optimization: A novel method for constrained mechanical design optimization problems. Computer-Aided Design, 43(3):303–315, 2011. Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, et al. Mathematical discoveries from program search with large language models. Nature, 2024. Fang Wang et al. Enhanced heat-transfer search jaya algorithm for engineering optimization. Soft Computing, 2022. 13
Ziyang Xiao, Dongxiang Zhang, Yangxin Wu, et al. Chain-of-experts: When LLMs meet complex operations research problems. In International Conference on Learning Representations (ICLR), 2024. Chengrun Yang, Xuezhi Wang, Yifeng Lu, et al. Large language models as optimizers. In International Conference on Learning Representations (ICLR), 2024.
14