LLM-Guided Graph Generation for Structure-Based Local Improvement Methods

This paper presents an automatic pipeline that uses Large Language Models (LLMs) to generate problem-agnostic graph representations for structure-based local improvement methods (SLIM) in combinatorial optimization. The key contributions are:

1. LLM-guided graph generation: The authors prompt an LLM (Claude Opus 4.5) with semantic guidelines to produce a Python program (a graph generator) for each MiniZinc constraint model. This generator maps any instance of a problem type to a uniform weighted graph where nodes represent decision variables and edges represent constraint relationships. Each node has a weight (importance to objective) and domain size, while each edge has a weight indicating coupling strength.

2. Problem-agnostic SLIM: Using these uniform graphs, the authors build a generic SLIM framework that works across different problems without domain-specific engineering. The framework uses two extraction methods: BFS extraction (which captures locality via weight-ordered edges) and LNS extraction (random variable collection with node weights). Both operate on the generic graph representation.

3. Cross-problem algorithm selection: Since all instances share the same uniform graph format, the authors extract 54 graph features (topology statistics, weight distributions, domain size statistics, etc.) and train machine learning models to select among 30 SLIM configurations. They evaluate five selection approaches (regression, ensemble, binary, classification, two-stage) across three random seeds.

The generation guidelines for the LLM include: objective-related components get higher weights (≥0.6), large global constraints use weight max(0.1, 1/n) to prevent clique domination, no isolated nodes, and bounded weights with aggregation formula W = 1 - ∏(1 - wi).

Experimental results: The pipeline was evaluated on instances from 20 MiniZinc competition problems (2008–2025). The key findings are:

• SLIM with the best configuration per problem type achieves a 39.5% average problem-weighted win rate against a one-shot Gurobi baseline (60-minute timeout), more than doubling the best single configuration (19.3%).

• On specific problems like tdtsp, spot5, community-detection, triangular, and opd, SLIM wins over 75% of instances. Only two problems (rectangle-packing and VRP) show SLIM losing on more than 50% of instances.

• Algorithm selection approaches all significantly outperform the best single configuration baseline (17.8–22.3% depending on seed), with every selection approach exceeding 31% win rate. The best-performing approaches achieve 37.9–40.6% win rates with positive net scores.

• Configuration and feature ablation boost performance further to 44.0% average problem-weighted win rate.

The authors note limitations: SLIM cannot outperform one-shot Gurobi on some specific problems, likely due to LLM-produced graph generators being approximations of true constraint semantics, and the evaluation covers only MiniZinc competition benchmarks. Future work includes more targeted prompts, dynamic weight updates during search, and tabu search to escape repetitive optimization.

Improvements to AI Systems:

1. Automatic Problem-to-Graph Translation for Combinatorial Optimization: The AI system can now take any combinatorial optimization problem (expressed in a constraint modeling language like MiniZinc) and automatically generate a problem-agnostic weighted graph representation via LLM-driven code synthesis. This eliminates the need for human experts to hand-craft graph encodings for each new problem type, enabling rapid deployment of local search heuristics on unseen problem classes.

2. Cross-Problem Local Search with Zero Domain Engineering: The improved system can apply a single, generic SLIM framework (using BFS and LNS extraction) to any optimization problem without requiring problem-specific algorithmic tweaks. This means the system can switch between problems like vehicle routing, scheduling, or community detection with no manual adaptation, achieving a 39.5% average win rate against a commercial solver (Gurobi) with a 60-minute timeout—more than doubling the best single-configuration baseline.

3. Meta-Learning for Algorithm Configuration Selection: The system now uses 54 automatically extracted graph features (topology, weight distributions, domain sizes) to train machine learning models that select the best SLIM configuration (out of 30) for a given instance. This enables the AI to predict which local search strategy will work best before solving, improving win rates from 19.3% (best single config) to 37.9–40.6% across different selection approaches—a capability that previously required extensive per-problem tuning.

4. LLM-Guided Heuristic Design with Semantic Weighting: The AI system can now generate graph generators that encode problem semantics into edge and node weights (e.g., objective-critical variables get weights ≥0.6, large global constraints are down-weighted to avoid clique domination). This allows the system to produce high-quality search neighborhoods that prioritize the most impactful decisions, leading to >75% win rates on problems like tdtsp, spot5, and community-detection.

5. Ablation-Driven Performance Boosting: The system can automatically refine its configuration and feature set (via ablation studies) to push average problem-weighted win rates to 44.0%. This means the AI can self-optimize its own algorithm selection pipeline, identifying which graph features and SLIM parameters matter most for a given problem family—enabling continuous improvement without human intervention.

6. Robustness Across Diverse Problem Instances: The improved system can handle a wide range of problem types (20 MiniZinc competition problems from 2008–2025) with a single unified representation, demonstrating generalization beyond narrow benchmarks. It can also identify its own limitations (e.g., losing on rectangle-packing and VRP) and flag cases where one-shot exact solvers are superior, allowing hybrid systems to fall back to Gurobi when local search is unlikely to win.

What the Improved AI System Can Do:

• Instant Deployment: Given a new optimization problem description, the system can generate a working local search solver within minutes (via LLM-generated graph code) without human feature engineering.

• Adaptive Strategy Selection: It can analyze the structure of any problem instance and choose the most promising local search configuration from a pre-trained portfolio, achieving near-optimal performance without trial-and-error.

• Explainable Graph Semantics: The system produces interpretable weighted graphs that reveal which variables and constraints are most critical, aiding debugging and human understanding of the problem's structure.

• Scalable Local Improvement: It can improve partial solutions from any initial solver (e.g., greedy or exact) by exploring neighborhoods defined by the generated graphs, making it a plug-and-play enhancement module for existing optimization pipelines.

• Self-Improving Performance: Through feature ablation and configuration tuning, the system can iteratively refine its own selection models and graph generation prompts, learning from past successes and failures across problem families.