Research Paper: Graph-Grounded Optimization

Title: Graph-Grounded Optimization: Rao-Family Metaheuristics, Classical OR, and SLM-Driven Formulation over Knowledge Graphs

Authors: Madhulatha Mandarapu (madhulatha@samyama.ai), Sandeep Kunkunuru (sandeep@samyama.ai)

arxiv:2605.12204 · Published 2026-05-15

Keywords: Knowledge Graphs, Optimization, Rao-Family Metaheuristics, OR-Tools, Small Language Models, Cypher, Property Graph Databases.

Abstract

What if optimization problems were sourced from a knowledge graph instead of a paragraph of English? We introduce graph-grounded optimization: a paradigm where the objective, decision variables, and constraints of an optimization problem are sourced from a property knowledge graph via Cypher queries, rather than from a natural-language description.

We evaluate seven real-world problems — drug repurposing, clinical-trial site selection, supply-chain rerouting, healthcare allocation, grid dispatch, antimicrobial-resistance stewardship, and wildfire evacuation — over public knowledge graphs ranging from 19.7K to 7.78M nodes, all expressed as Cypher against Samyama. We benchmark five Rao-family metaheuristics (BMWR, Jaya, SAMP-Jaya, EHR-Jaya, Rao-1) against Google OR-tools (CP-SAT, GLOP) and SLM baselines (Phi-4, GPT-4.1, o3, gpt-5.5, OptiMind-SFT) in schema-aware and blind settings.

Key Findings

• No single Rao variant dominates across problems. BMWR wins 4/7; Rao-1 wins 2/7. Variant choice is problem-dependent.
• Classical OR is still the right tool for linear/MILP-shaped problems, beating metaheuristics by 2–3× in solution quality where structure permits.
• Zero-shot SLMs collapse on real formulations. Phi-4: 0/7 exact. GPT-4.1: 2/7. The failures are schema-alignment failures, not reasoning failures — a model that never sees the KG cannot formulate against it.
• Graph-grounding surfaces data-quality issues that text-based formulation quietly hides.

Architecture: Two Invocation Paths

The same samyama-optimization crate is used in two distinct invocation patterns:

1. In-database stored procedure — production path. Cypher CALL algo.or.solve({...}) dispatches into the executor (see samyama-graph/src/query/executor/operator.rs and ADR-026), which constructs a Problem from a Cypher-projected table and runs the chosen solver.
2. Standalone Rust harness — paper-8 benchmarks. Each problem (p1…p7) is an independent Rust binary that links the same crate directly, loads a .sgsnap snapshot, builds the Problem in-process, and runs the solver per seed. This is the path used for the published benchmark numbers.

Both paths exercise the same solver code; the harness path adds per-seed reproducibility and avoids the protocol round-trip overhead that would dominate small-N benchmarks.

Solver Inventory (crates/samyama-optimization)

Single-objective: JayaSolver, RaoSolver (with RaoVariant), TLBOSolver, FireflySolver, CuckooSolver, GWOSolver, GASolver, SASolver, BatSolver, ABCSolver, GSASolver, HSSolver, FPASolver. Multi-objective: NSGA2Solver, MOTLBOSolver, plus the BMWR / MO-BMR / MO-BWR / MO-BMWR / SAMP-Jaya / SAPHR / EHR-Jaya / QO-Rao extensions covered in ADR-026.

Why It Matters for Samyama

Graph-grounded optimization is the prescriptive endgame of BI: descriptive dashboards say what happened, predictive models say what’s likely, but the actual decision — what should we do about it — is an optimization problem. By making that step a first-class CALL algo.or.solve operation over the same graph that holds the entities and relationships, Samyama removes the export/import seam that normally separates analytics from optimization.

Artifacts

• Paper: arxiv:2605.12204
• Optimization crate: samyama-graph/crates/samyama-optimization/
• ADR-026: Rao-Family Optimization Crate (docs/ADR/ADR-026-rao-optimization-crate.md)
• Paper-8 standalone harnesses: samyama-research/papers/paper8-graph-grounded-optimization/06-aws-cycles/p{1..7}/src/main.rs
• SLM baseline harness: samyama-research/papers/paper8-graph-grounded-optimization/05-baselines/slm/optimind/