When optimization constraints only work together, can AI spot the group?

A planning model can contain rules for inventory balance, production setups and machine capacity. Testing each group of rules separately may suggest that none helps strengthen the model’s mathematical bound. Yet handling two groups together can make a substantial difference. That creates a trap for a search that accepts only immediately useful additions.

In the November 3 preprint Do Language Models Know Which Constraints Belong Together?, Junbo Jacob Lian and colleagues study this problem through mathematical proofs and controlled language-model experiments. Their central question is not whether AI can produce a plausible explanation, but whether its suggestions reduce the computation needed to find a strong reformulation.

Why combinations matter

Mixed-integer linear programs combine linear constraints with variables that must take integer values. Their linear programming relaxation permits fractional values, providing a bound on the integer optimum. Dantzig–Wolfe reformulation can strengthen that bound by representing selected constraints through the convex hull of their integer-feasible solutions.

The choice of constraints matters. Evaluating a candidate reformulation requires a column-generation run, while combining too many constraint families can make the underlying subproblems difficult.

The authors call a combination a “zero-marginal group” when it improves the bound but none of its proper subsets does. In one small lot-sizing example, inventory-balance and setup constraints together close about 63 percent of the gap between the linear relaxation and the integer optimum, although neither family improves the bound alone.

This is not confined to that example. The study reports certain zero-marginal groups in roughly a quarter of the MIPLIB-NL models whose bounds improved under the evaluated decompositions. Time-limited evaluations leave additional groups classified as possible rather than certain.

Putting a computational price on a prediction

The theoretical analysis considers methods that learn about candidates only by evaluating their bounds, with each evaluation allowed to combine at most a specified number of families.

For constructed problems containing a hidden group of size w among k families, the authors prove that the worst-case evaluation count grows on the order of k to the power w, when the group size and evaluation budget are fixed. They also construct actual Dantzig–Wolfe relaxations exhibiting this behavior. The restriction matters: this is a result about bound-only access, not every algorithm that can inspect a formulation.

A prediction changes the search. If a proposed group misses e true members, a staged search reduces the asymptotic cost to the order of k to the power e without needing to know e beforehand. A correct prediction takes one evaluation to confirm on these constructed problems. Entirely wrong predictions add only lower-order asymptotic overhead, although finite examples can still incur appreciable extra work.

JointDW uses a language model’s proposed group to anchor this search and alternates it with prediction-free search. The authors also combine it with a mathematical lookahead derived from an optimal linear-programming dual solution. Alternating two orders bounds the evaluation count by twice that of the better order; it does not establish an equivalent guarantee for elapsed time.

Familiar names help—but coefficients can change the result

The experiments test five configurations from four model providers on small templates, MIPLIB-NL models and 24 richer constructed instances. Models receive no bounds or solver answers. Different presentations withhold descriptions, permute family names or replace names with anonymous labels.

On nine textbook-style templates, GPT-6.1 Sol’s first predicted group was correct in every sampled answer under the original presentation. Its recall fell to zero when family names were permuted or anonymized. That supports a narrower interpretation than general structural understanding: familiar terminology was crucial in this setting.

On the scored MIPLIB-NL models with certain joint groups, the strongest language-model configurations performed roughly comparably to the mathematical lookahead. They succeeded on partly different instances, but none demonstrated a statistically distinguishable reduction in evaluation count against lookahead there.

The richer instances exposed another distinction. Given descriptions and family summaries without complete numerical data, no configuration’s first-group accuracy exceeded one third. Supplying every coefficient raised GPT-6.1 Sol’s first-group accuracy from about 22 percent to 99 percent. With evaluations restricted to pairs, its JointDW search averaged 1.17 evaluations, compared with 3.87 for lookahead. When triples were allowed, lookahead found a best set in its first evaluation on every instance and remained better.

What remains unproven

These are preprint findings from small, selected experimental sets. The richer instances retain recognizable classical groups, so success need not demonstrate instance-specific reasoning. Training familiarity with textbooks or benchmark models also cannot be excluded.

The result is therefore conditional: language-model suggestions can save verified search work, but their value depends on presentation, numerical information and the allowed reformulation size. Solver checks—not confidence in the generated explanation—determine whether a suggestion actually helps.