跳转至

文章背景与核心概要

大型邻域搜索（LNS）传统上依赖于随机选择决策变量子集来进行迭代优化。尽管该方法在某些场景下表现有效，但要高效解决复杂的组合优化问题，通常需要领域特定的结构洞察来指导变量的选择。为了克服传统方法对人工设计启发式算法的依赖，本文提出了一种针对 MiniZinc 格式问题的领域无关（problem-agnostic）自动化流水线。

通过精心设计的语义准则引导大语言模型（LLM），作者成功让大模型自动生成图生成器。这些生成器能够将任意问题实例映射为统一的加权图，其中节点表示决策变量，边表示约束关系。这些通用的图结构随后驱动了基于结构的局部改进（SLIM）框架，实现了智能的变量选择。由于所有实例共享通用的图表示，系统能够可靠地提取一致的图特征以进行配置选择。在 20 个 MiniZinc 竞赛问题上的实验表明，该算法选择方法实现了 39.6% 的平均问题加权胜率，相比 Gurobi 基线或单一最优配置（19.3%）实现了显著性能翻倍，展示了 LLM 在约束优化自动化结构和特征提取方面的巨大潜力。

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

Authors: Hai Xia, Vaidyanathan Peruvemba Ramaswamy, Stefan Szeider
Categories: Computer Science > Artificial Intelligence (cs.AI)
arXiv Identifier: arXiv:2608.13333 [cs.AI]
Dates: Submitted on 13 Aug 2026; Last revised 17 Aug 2026 (v3)

摘要与总结

大邻域搜索通常选择决策变量的随机子集进行迭代优化。为了高效解决各种问题，研究人员倾向于设计考虑不同领域结构特征的变量选择策略。在本文中，我们构建了一个对 MiniZinc 格式中所有问题都具备领域无关性的自动化流水线。通过利用我们的语义准则提示 LLM，我们引导 LLM 生成一个图 generator，该 generator 将任何问题类型的实例映射到一个统一的加权图中，其中节点代表决策变量，边代表约束关系。这些领域无关的图引导了我们用于变量选择的基于结构的局部改进（SLIM）框架。同时，加权图使所有问题实例能够共享相同的通用图表示，从中可以提取相同的图特征并用于配置选择。我们在 20 个 MiniZinc 竞赛问题的实例上评估了我们的流水线，发现与单次 Gurobi 基线相比，算法选择实现了 39.6% 的平均问题加权胜率，是最佳单一配置（19.3%）的两倍多。事后配置和特征消融表明性能提升空间高达 44.0%，这证明了基于 LLM 的语义生成能够为约束优化实现有效的自动化结构和特征提取。

Large Neighborhood Search (LNS) traditionally relies on selecting random subsets of decision variables for iterative optimization. While effective in some contexts, more efficient problem-solving often requires domain-specific structural insights to guide variable selection.

本文引入了一个针对 MiniZinc 格式问题的领域无关自动化流水线。通过利用语义准则，作者提示大语言模型（LLM）自动生成图生成器。这些生成器将问题类型的任何实例映射到统一的加权图中，其中： * 节点代表决策变量。 * 边代表约束关系。

This paper introduces a problem-agnostic automated pipeline tailored for problems formatted in MiniZinc. By leveraging semantic guidelines, the authors prompt Large Language Models (LLMs) to automatically generate graph generators. These generators map any instance of a problem type into a uniform weighted graph where: * Nodes represent decision variables. * Edges represent constraint relationships.

这些领域无关的图支持了用于智能变量选择的基于结构的局部改进（SLIM）框架。由于所有实例共享通用的图表示，因此可以可靠地提取一致的图特征来优化配置选择。

These problem-agnostic graphs power a Structure-Based Local Improvement (SLIM) framework for intelligent variable selection. Because all instances share a generic graph representation, consistent graph features can be reliably extracted to optimize configuration selection.

核心结果

  • 性能表现： 在 20 个 MiniZinc 竞赛问题上进行评估，与单次 Gurobi 基线相比，该算法选择方法实现了 39.6% 的平均问题加权胜率。
  • 基线对比： 这一性能表现达到了最佳单一配置（19.3%）的两倍以上。
  • 性能上限分析： 事后配置和特征消融研究表明，其性能上限可达 44.0%，突显了基于 LLM 的语义生成在约束优化中实现自动化结构和特征提取的有效性。

Key Results

  • Performance: Evaluated across 20 MiniZinc competition problems, the algorithm selection approach achieved a 39.6% average problem-weighted win rate against a one-shot Gurobi baseline.
  • Baseline Comparison: This performance more than doubles the win rate of the best single configuration (19.3%).
  • Headroom Analysis: A post-hoc configuration and feature ablation study indicate an upper performance headroom of up to 44.0%, highlighting the efficacy of LLM-based semantic generation for automated structure and feature extraction in constraint optimization.

摘要 (Abstract)

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.