arXiv cs.AI· Junbo Jacob Lian, Kaixuan Chen, Hanzhang Qin, Huiling Chen, Chaoyu Zhang, Chung-Piaw Teo·· 10 小时前AI 评分31
语言模型知道哪些约束该放在一起吗？JointDW 用 LLM 预测 Dantzig-Wolfe 重构造的约束分组
Do Language Models Know Which Constraints Belong Together?
AI 导读
研究提出 JointDW，用语言模型读取模型中的约束名称与文本，预测 Dantzig-Wolfe 重构造中哪些约束族需联合凸化才能收紧线性松弛，并用分阶段搜索验证预测、与最优 LP 对偶的前瞻方法交错执行。
正文 · AI 翻译
摘要：Dantzig-Wolfe 重构通过凸化一组选定的约束族来增强混合整数规划的线性松弛，而每个候选方案都需要运行一次列生成。当各约束族只有联合起来才能增强下界时，选择就很困难，因为一次只添加一个约束族的搜索会停在某个线性松弛处。批量生产、网络设计和设施选址中的经典不等式就建立在这样的零边际群组之上。我们证明，当每次评估最多凸化 k 个约束族中的 s 个时，任何只观察下界的方法都需要一个覆盖数量的评估次数，量级为 k^w，才能找到一个隐藏的 w 个约束族的群组，在实际的 Dantzig-Wolfe 松弛上也是如此。一个漏掉 e 个成员的预测通过一次不需要知道 e 的分阶段搜索将成本降低到 Θ(k^e)，因此预测所节省的评估次数衡量了预测器所知道的信息。我们研究了两种预测来源。对最优 LP 对偶的一次性前瞻可证明对约束族之间不共享变量的群组是盲的，而语言模型会读取模型的名称和文本。JointDW 用分阶段搜索验证语言模型的预测，并以有界损失将其与前瞻交错进行。在能够改进下界的 MIPLIB-NL 模型中，有四分之一会出现仅联合起来才能增强下界的群组。在这些模型上，最强的语言模型识别它们的频率与前瞻大致相当，其预测依赖于教科书模型的名称，而推理使同一模型的准确率翻倍。在带有干扰约束族的较大模型上，前瞻在一次对三个约束族的评估中就能找到该群组。仅给定文本的语言模型很少能说出它，而一个给定所有系数的推理模型在除一个答案外的所有答案中都能说出它，并且对于约束族对，随后需要的评估次数比前瞻更少。
| 评论： | 23 页，4 幅图，15 张表。代码和数据：此 https URL |
| 主题： | 机器学习（cs.LG）；人工智能（cs.AI）；数据结构与算法（cs.DS）；优化与控制（math.OC） |
| 引用为： | arXiv:2611.05726 [cs.LG] |
| （或 arXiv:2611.05726v1 [cs.LG] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2611.05726 由 DataCite 颁发的 arXiv DOI（待注册） |
提交历史
来自：Junbo Jacob Lian [查看电子邮件]
[v1]
2026 年 11 月 3 日星期二 22:55:13 UTC（253 KB）
来源：arXiv cs.AI · arxiv.org