Do Language Models Know Which Constraints Belong Together?

원문 초록

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; 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. A prediction that misses $e$ members reduces the cost to $\Theta(k^e)$ by a staged search, so the evaluations a prediction saves measure what the predictor knows. We study two sources of predictions: a lookahead at an optimal LP dual, blind to groups whose families share no variable, and a language model that reads the model, which JointDW verifies with the staged search and interleaves with the lookahead at a bounded loss. Zero-marginal groups appear in three of ten MIPLIB-NL models with an improvable bound and in all 59 standard lot-sizing, network-design and facility-location instances, where GCG's detector convexifies a set with no gain on 38 of them. On MIPLIB-NL the strongest language models find the groups about as often as the lookahead, and on textbook models their predictions rest on the names. Given every coefficient of a larger model, one reasoning model names the classical group in all but one answer, also with the names permuted or removed, and needs fewer evaluations than the lookahead for pairs of families; a predictor trained on the same class matches this only after hundreds of labeled evaluations. On the benchmark instances the language models name the best pair more often than the lookahead and the detector, and the sets of GPT-6.1 Sol come closest to the branch-and-price time of the best set.