arXiv cs.AI· Junbo Jacob Lian, Kaixuan Chen, Hanzhang Qin, Huiling Chen, Chaoyu Zhang, Chung-Piaw Teo·· 3 小时前AI 评分40
语言模型知道哪些约束该归为一组吗？——arXiv 论文研究 Dantzig-Wolfe 重构中的约束族分组预测
Do Language Models Know Which Constraints Belong Together?
AI 导读
一篇 arXiv 论文研究语言模型能否识别混合整数规划中只有联合起来才能加强线性松弛界的约束族组合。论文提出 JointDW 框架，用语言模型的预测配合分阶段搜索验证，并与 LP 对偶 lookahead 交错使用；证明仅观察界值的方法需要约 k^w 次评估才能找到 w 个族组成的隐藏组。
正文 · 原文
Abstract:Dantzig-Wolfe reformulation strengthens the linear relaxation of a mixed-integer program by convexifying a chosen set of constraint families, and every candidate costs a column generation run. The choice is hard when families strengthen the bound only together, because a search that adds one family at a time then stops at the linear relaxation. The classical inequalities of lot sizing, network design and facility location rest on such zero-marginal groups. We prove that when each evaluation convexifies at most $s$ of $k$ families, any method that observes only bounds needs a covering number of evaluations, of order $k^w$, to find a hidden group of $w$ families, also on actual Dantzig-Wolfe relaxations. A prediction that misses $e$ members reduces the cost to $\Theta(k^e)$, through one staged search that does not need to know $e$, so the evaluations a prediction saves measure what the predictor knows. We study two sources of predictions. A one-pass lookahead at an optimal LP dual is provably blind to groups whose families share no variable, and a language model reads the names and text of the model. JointDW verifies the prediction of the language model with the staged search and interleaves it with the lookahead at a bounded loss. Groups that strengthen the bound only jointly appear in a quarter of the MIPLIB-NL models whose bound can be improved. There the strongest language models identify them about as often as the lookahead, their predictions rest on the names for textbook models, and reasoning about doubles the accuracy of the same model. On larger models with distracting families, the lookahead finds the group in one evaluation of three families. Language models given only the text seldom name it, while one reasoning model given every coefficient names it in all but one answer and then needs fewer evaluations than the lookahead for pairs of families.
| Comments: | 23 pages, 4 figures, 15 tables. Code and data: this https URL |
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC) |
| Cite as: | arXiv:2611.05726 [cs.LG] |
| (or arXiv:2611.05726v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2611.05726 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Junbo Jacob Lian [view email]
[v1]
Tue, 3 Nov 2026 22:55:13 UTC (253 KB)
来源：arXiv cs.AI · arxiv.org