arXiv:2608.13333cs.AI2026-08

用大模型生成统一图结构,提升约束优化变量选择效率。

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

论文配图:LLM-Guided Graph Generation for Structure-Based Local Improvement Methods
图 1 · 摘自论文原文
  • 用大模型根据语义生成问题无关的加权图,节点为变量,边为约束关系。
  • 在20个MiniZinc问题上,算法选择胜率达39.6%,超基线一倍以上。
  • 适用于各类约束优化问题,尤其适合自动化配置与特征提取场景。

大型邻域搜索通常随机选取决策变量进行迭代优化。为高效解决各类问题,研究者倾向于设计考虑跨领域结构特征的变量选择策略。本文构建了一个对所有MiniZinc格式问题均适用的自动化流程。通过向大语言模型(LLM)提示语义指引,引导其生成图生成器,将任意问题实例映射为统一的加权图:节点代表决策变量,边代表约束关系。这些问题无关的图结构指导基于结构的局部改进(SLIM)框架进行变量选择。同时,加权图使所有问题实例共享相同通用图表示,可提取一致图特征用于配置选择。我们在20个MiniZinc竞赛问题实例上评估该流程,发现算法选择在问题加权平均胜率达39.6%,超过单次调用Gurobi基线,且是最佳单一配置(19.3%)的两倍以上。事后配置分析与特征消融实验表明,性能提升空间高达44.0%,证明基于大模型的语义生成能有效实现约束优化中结构与特征的自动提取。

原文摘要 · Abstract (English)

Large neighborhood search normally selects a random subset of decision variables for iterative optimization. To efficiently solve various problems, researchers tend to design variable selection strategies that take into account structural features across different domains. In this paper, we build an automatic pipeline that is problem-agnostic to all problems in the MiniZinc format. By prompting an LLM with our semantic guidelines, we guide the LLM to produce a graph generator that maps any instance of a problem type to a uniform weighted graph, where nodes represent decision variables and edges represent constraint relationships. These problem-agnostic graphs guide our structure-based local improvement (SLIM) framework for variable selection. Meanwhile, the weighted graph enables all problem instances to share the same generic graph representation, from which the same graph features can be extracted and used for configuration selection. We evaluated our pipeline on instances across 20 MiniZinc competition problems, finding that algorithm selection achieves a 39.6% average problem-weighted win rate against a one-shot Gurobi baseline, more than doubling the best single configuration (19.3%). A post-hoc configuration and a feature ablation indicate a headroom of up to 44.0%, demonstrating that LLM-based semantic generation enables effective automated structure and feature extraction for constraint optimization.

约束优化大模型图生成自动化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。