面向组合优化的不可行性感知大语言模型

大语言模型（LLM）在NP难组合优化问题上的探索日益增多，但多数现有方法侧重可行实例的解生成，并未显式处理不可行性检测。我们提出一个不可行性感知框架，结合可认证的数据集构建、监督微调与LLM辅助的下游搜索。针对minor-embedding问题，我们提出一种新的数学规划表述以及可证明的零阶段不可行性筛查，从而能够可扩展地构建训练实例，其标签要么是带结构化证书的可行，要么是可认证的不可行。利用这一精确优化流程生成的训练数据，我们证明8B参数的LLM可经微调后联合执行解生成与不可行性检测。我们进一步将LLM输出用作下游局部搜索的暖启动，即使LLM输出并不完美，也提供了一条切实可行的加速优化途径。实验表明，我们的微调模型总体准确率比GPT-5.2最多提升30%；同时，LLM引导的暖启动与下游局部搜索从零开始相比最多带来2×加速。