让大模型学会识别组合优化中的无解问题并辅助求解，提升准确率和效率。
Infeasibility Aware Large Language Models for Combinatorial Optimization
- 构建可验证的训练数据集，让模型同时学习找解与判无解。
- 微调后模型准确率比GPT-5.2高30%，且加速下游搜索达2倍。
- 适合需要高效求解复杂优化问题的研究者或工业应用。
大语言模型（LLM）在求解NP难组合优化问题方面日益受到关注，但现有方法多聚焦于可行实例的解生成，缺乏对不可行性的显式处理。本文提出一种无解感知框架，结合可验证数据集构建、监督微调及模型辅助的下游搜索。针对最小嵌入问题，提出新的数学规划形式，并实现可证明的零相位无解筛查，支持大规模生成带有结构化证明的可行或确证不可行实例。基于此精确优化流程生成的训练数据，我们展示了80亿参数的LLM可被微调以联合完成解生成与无解检测。进一步利用模型输出作为下游局部搜索的热启动，即使模型输出不完美也能有效加速优化。实验表明，微调模型整体准确率较GPT-5.2提升最高30%；而模型引导的热启动使局部搜索速度最高提升2倍。
原文摘要 · Abstract (English)
Large language models (LLMs) are increasingly explored for NP-hard combinatorial optimization problems, but most existing methods emphasize feasible-instance solution generation and do not explicitly address infeasibility detection. We propose an infeasibility-aware framework that combines certifiable dataset construction, supervised fine-tuning, and LLM-assisted downstream search. For the minor-embedding problem, we introduce a new mathematical programming formulation together with provable zero-phase infeasibility screening, which enables scalable construction of training instances labeled either as feasible with structured certificates or as certifiably infeasible. Using training data generated through this exact optimization pipeline, we show that an 8B-parameter LLM can be fine-tuned to jointly perform solution generation and infeasibility detection. We further utilize LLM outputs as warm starts for downstream local search, providing a practical way to accelerate optimization even when the LLM outputs are imperfect. Experiments show that our fine-tuned model improves overall accuracy by up to 30\% over GPT-5.2; meanwhile LLM-guided warm starts provide up to $2\times$ speedup compared with starting from scratch in downstream local search.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。