Organizations: Institute of Operations Research and Analytics, National University of Singapore, Singapore · Wenzhou Buyi Pharmacy, Wenzhou, China · McCormick School of Engineering, Northwestern University, Evanston, IL 60208, USA · College of Computer Science and Artificial Intelligence, Wenzhou University, Wenzhou, China · Department of Decision Analytics and Operations, City University of Hong Kong, Hong Kong, China
Dantzig--Wolfe reformulation strengthens the linear relaxation of a mixed-integer program by convexifying constraint families, and each candidate costs a column generation run. The choice is hard when families strengthen the bound only together, as in classical lot-sizing, network-design, and facility-location formulations. We prove that when an evaluation convexifies at most s of k families, methods that observe only bounds need of order kw evaluations to find a hidden group of w families in the worst case. A prediction missing e members reduces this to Θ(ke) through a staged search that need not know e. The orders extend to several groups, prices, and growing evaluation costs. We study two predictors: a lookahead at an optimal LP dual, which vanishes on groups whose families share no variable, and language models reading the model, verified by the staged search in JointDW. Such groups appear in three of ten MIPLIB-NL models whose bound can be improved and in all 59 benchmark instances. Given the coefficients of models with up to 16 families, one language model names a true group first in 249 of 252 answers. On the benchmark instances, decompositions chosen by language models from the text solve faster than those of GCG's detector.
Figures & tables
Figure 1: Share of the integrality gap closed by every family-level DW relaxation of a lot-sizing instance with two items and two periods, with B, S, and C the balance, setup, and capacity families. Edge width is proportional to the increase of the bound when one family is added, and gray edges add nothing. The shaded sets have gain zero, so a search that adds one family at a time while the bound improves never leaves ∅ . The pairs BS and CS are zero-marginal groups.
Figure 2: (a) Queries of the staged search of Theorem 2 (a), from top to bottom, for k=6 , s=3 , w=2 , and the prediction P={1,2} (shaded columns): one query per row, with its families in dark cells. The queries of stage e contain every hidden group with e members outside P , so a correct prediction is confirmed by the first query. (b) Evaluations to find a hidden group of w=3 families with s=6 . Solid lines: for predictions that miss e members, the queries in the stages of the staged search built from greedy coverings and, in each stage, from the cover of P with the fewest queries among those with members of one size; without a prediction, the worst case of a greedy covering. Dashed lines of the same color: the lower bounds Le of Theorem 2 (b) and (3k)/(36) of Theorem 1 .
Collection
Instances
k
Gains
Measures
Templates
15
2–6
exact, every set
accuracy of a prediction
MIPLIB-NL
108
2–6
column generation
census, accuracy, search cost
Rich models
24
7–9
exact, sets of at most three
search cost as k grows
60
12–16
exact, sets of at most three
Benchmark instances
59
3
column generation
solve time
Without a joint support
76
2–3
column generation
false alarms, solve time
Table 1: Instance collections. k : number of constraint families. Gains are exact, from explicit LPs solved in rational arithmetic, or come from column generation with GCG at the root node for the sets of at most k−1 families. On the network-design rich models with 14 families, the exact gains cover the sets of at most two families.
Templates
MIPLIB-NL
False
Configuration
hit@1
recall
hit@1
recall
alarms
Claude Sonnet 5.5
0.70
0.74
0.57
0.56
0.17
GPT-6.1 Sol
1.00
0.96
0.53
0.53
0.00
Grok 4.20 (Reasoning)
0.67
0.67
0.55
0.55
0.00
Grok 4.20 (Non-Reasoning)
0.33
0.17
0.29
0.29
0.00
DeepSeek-V4-Pro (Non-Thinking)
0.30
0.26
0.27
0.37
0.33
Table 2: Prediction of joint supports in the original presentation. Templates: the nine lot-sizing, network-design, and facility-location instances. MIPLIB-NL: the 17 scored models with a certain joint group. False alarms: the share of answers that name a joint support on the two generalized assignment instances, which have none. Standard errors, the other presentations, and the five-dual lookahead order: Appendix J .
Order
s=2
s=3
s=k−1
Templates
Random (expected)
4.57 ± 0.77
4.56 ± 0.82
3.82 ± 0.37
Covering
2.86 ± 0.61
2.33 ± 0.31
1.82 ± 0.08
Lookahead
2.00 ± 0.76
1.92 ± 0.71
1.92 ± 0.71
JointDW with Claude Sonnet 5.5
2.47 ± 0.67
2.11 ± 0.41
1.71 ± 0.22
JointDW with GPT-6.1 Sol
2.07 ± 0.67
1.72 ± 0.47
1.16 ± 0.14
Table 3: Number of evaluations until a best decomposition is evaluated when each evaluation may convexify at most s families, on the instances with a true joint support and a positive gain within the budget, mean ± standard error. The lowest mean of each column is in bold. Greedy selection stops at the LP relaxation on every template and on most MIPLIB-NL models and is not shown. The five-dual lookahead order and the interleaved orders: Appendix J .
Figure 3: (a) Census of MIPLIB-NL: for each model with a positive gain, the largest gain of a single family against the largest gain of a set of families, both as shares of the LP gap; marks on the vertical axis have no family that strengthens the bound alone. Blue marks have a zero-marginal group at ∅ , certain (filled) or possible (open); gray marks have none. (b, c) Recall of joint supports under the four presentations, with the recall of the lookahead order as a dashed line. Solid lines: configurations with reasoning; dashed lines: without.
Figure 4: Rich models with 7 to 16 families. (a) hit@1 of GPT-6.1 Sol (circles) and Claude Sonnet 5.5 (squares) given the text (open) and every coefficient (filled), on the models with 7 to 9 and with 12 to 16 families. (b) Mean number of evaluations until a best set is evaluated for s=2 against the number of families k , by class, with JointDW using GPT-6.1 Sol given every coefficient. Bars: one standard error. Every configuration and s=3 : Tables 14 and 25 .
Figure 5: Search cost on the rich models for s=2 , by the number e of members of a best pair that the anchor misses, with one mark per class and number of families k . (a) The staged order O1 alone. Dashed lines of the same color: the number of queries of stages 0 to e of Theorem 2 (a). (b) JointDW and the covering order. Predictions of GPT-6.1 Sol and Claude Sonnet 5.5 under both presentations whose anchor has at most two families. Bars: one standard error.
first set is the best pair
time-optimal set
no joint support
Method
LS
ND
FL
all
hit
time ratio
hit
time ratio
Lookahead (HiGHS dual)
1.00
0.35
0.68
0.68
0.56
2.03 ± 0.86 ∗
0.76
2.58 ± 1.16 ∗
Lookahead (five duals)
1.00
0.35
0.95
0.76
0.61
1.71 ± 0.62 ∗
0.79
2.56 ± 1.15 ∗
GCG’s detector
1.00
0.00
0.00
0.34
0.32
2.30 ± 0.81 ∗
0.79
1.18 ± 0.13 ∗
JointDW with
GPT-6.1 Sol
1.00
0.67
1.00
0.89
0.75
1.29 ± 0.20 ∗
0.96
1.00 ± 0.00
Table 4: Benchmark instances. Left: share of the 59 instances on which the first set of a method is the best pair, for lot sizing (LS), network design (ND), facility location (FL), and all instances. Middle: share of the 59 instances on which it is the time-optimal set, and its time ratio. Right: the same two quantities on the 76 generalized assignment and bin-packing instances, which have no joint support within the budget. JointDW uses the original presentation. Time ratios: geometric mean ± standard error, with an asterisk when the 95 percent interval of the mean log ratio excludes zero. Per class and paired differences: Tables 19 , 20 and 24 .
Appendix figures & tables27 assets
Supplementary material from the paper’s appendix.
Appendix
Class and families
Instance
k
LP gap (%)
Zero-marginal group
Gap closed (%)
Lot sizing
LS 2×2
3
32.4
BS
63
B balance, S setup, C capacity
CS
63
LS 2×2 b
3
34.6
BS
60
CS
57
LS 3×2
3
22.0
BS
100
CS
17
Appendix
Table 5: Instances with exact ground truth. LP gap: (zIP−zLP)/∣zIP∣ . Gap closed: the share of the LP gap that convexifying the group closes, computed in exact rational arithmetic and rounded. Every group of order two or three is polyhedral. The generalized assignment instances have no joint support, and their best decomposition convexifies the capacity family alone.
Class
k
rows × columns
LP gap (%)
best sets
groups
Lot sizing
9
35×21
15.2–51.7
BS (4), BCS (3), BST (1), BSY (2)
2–4
Network design
7
37×21 , 43×24
2.8–30.1
FU (8)
1
Facility location
7
21×12 , 25×15
5.5–28.5
AP (8)
1–2
Appendix
Table 6: Rich models: number of families k , size, LP gap, the minimal best sets among the sets of at most three families with the number of instances in parentheses, two lot-sizing instances having two such sets, and the number of zero-marginal groups per instance. B: Balance, S: SetupLink, C: Capacity, T: StorageCap, Y: SafetyStock; F: FlowBalance, U: ArcCapacity; A: Assign, P: Capacity.
Class
k
rows
columns
LP gap (%)
groups
positive gain, s=2
Lot sizing
12
48
21
26.5–54.5
3.4
10
16
58
21
34.3–53.2
5.6
10
Network design
12
61–71
21–24
7.5–36.1
3.5
10
14
65–77
21–24
2.5–23.5
3.2
10
Facility location
12
29–34
12–15
2.1–11.4
2.9
7
16
42–50
12–15
2.5–17.0
9.7
8
Appendix
Table 7: Rich models with 12 to 16 families: number of families k , rows, columns, LP gap, mean number of zero-marginal groups per instance, and number of instances on which some set of at most two families has a positive gain.
Class
Data
Instances
rows × columns
LP gap (%)
Best pair
Lot sizing
Trigeiro et al. (1989)
20
195×270
63.9–74.4
balance, setup linking
Network design
R set ( Crainic et al., 2001 )
20
485×385 to 1160×910
0.05–10.6
flow balance, arc capacity
Facility location
OR-Library cap ( Beasley, 1990 )
19
866×816 to 2600×2550
0.006–0.42
assignment, capacity
Appendix
Table 8: Benchmark instances: number of instances, size, LP gap as (zIP−zLP)/∣zIP∣ , and the best pair of families, which is a certain zero-marginal group at ∅ in every instance.
Configuration
Original
Names only
Permuted
Anonymized
Templates
Claude Sonnet 5.5
0.74 ± 0.07
0.78 ± 0.11
0.39 ± 0.14
0.48 ± 0.14
GPT-6.1 Sol
0.96 ± 0.03
0.33 ± 0.18
0.00 ± 0.00
0.00 ± 0.00
Grok 4.20 (Reasoning)
0.67 ± 0.08
0.81 ± 0.08
0.22 ± 0.07
0.30 ± 0.13
Grok 4.20 (Non-Reasoning)
0.17 ± 0.10
0.37 ± 0.15
0.26 ± 0.08
0.26 ± 0.12
DeepSeek-V4-Pro (Non-Thinking)
0.26 ± 0.12
0.33 ± 0.06
0.28 ± 0.06
0.30 ± 0.13
Appendix
Table 9: Recall of joint supports by presentation, mean ± standard error.
Configuration
Names only − permuted
Names only − anonymized
Original − anonymized
Templates
Claude Sonnet 5.5
0.39 ± 0.18 ∗
0.30 ± 0.14 ∗
0.26 ± 0.20
GPT-6.1 Sol
0.33 ± 0.18 ∗
0.33 ± 0.18 ∗
0.96 ± 0.03 ∗
Grok 4.20 (Reasoning)
0.59 ± 0.06 ∗
0.52 ± 0.18 ∗
0.37 ± 0.15 ∗
Grok 4.20 (Non-Reasoning)
0.11 ± 0.16
0.11 ± 0.12
− 0.09 ± 0.08
DeepSeek-V4-Pro (Non-Thinking)
0.06 ± 0.05
0.04 ± 0.11
− 0.04 ± 0.03
Appendix
Table 10: Paired differences in recall between presentations, mean ± standard error. An asterisk marks a difference whose 95 percent bootstrap interval excludes zero.
Presentation
hit@1
recall
Templates
Original
0.33 ± 0.13 ∗
0.50 ± 0.12 ∗
Names only
0.37 ± 0.24
0.44 ± 0.23
Permuted
− 0.15 ± 0.15
− 0.04 ± 0.07
Anonymized
− 0.11 ± 0.11
0.04 ± 0.11
MIPLIB-NL
Appendix
Table 11: Grok 4.20 (Reasoning) minus Grok 4.20 (Non-Reasoning), paired over instances, hit@1 and recall, mean ± standard error. An asterisk marks a difference whose 95 percent bootstrap interval excludes zero.
Templates
MIPLIB-NL
Rich models
First set
hit@1
recall
hit@1
recall
hit@1
recall
Lookahead (HiGHS dual)
0.67 ± 0.24
0.44 ± 0.17
0.53 ± 0.12
0.44 ± 0.11
0.21 ± 0.10
0.19 ± 0.10
Lookahead (five duals)
1.00 ± 0.00
0.78 ± 0.11
0.53 ± 0.12
0.44 ± 0.11
0.04 ± 0.05
0.04 ± 0.05
Appendix
Table 12: Five-dual lookahead. Top: hit@1 and recall of the first set of the lookahead order at the HiGHS dual and with five optimal duals, mean ± standard error, on the nine structured templates, the 17 MIPLIB-NL models with a certain joint group, and the 24 rich models. Bottom: number of evaluations until a best set is evaluated, by size limit s , for the two lookahead orders and for JointDW interleaved with the five-dual order, on the 13 templates with a positive gain for some set, the 17 MIPLIB-NL models, and the 24 rich models; JointDW uses the original presentation, which shows no coefficients. One of these templates has no positive gain for s=2 , where every order costs one evaluation on it.
hit@1
recall
Configuration
text
coefficients
text
coefficients
Claude Sonnet 5.5
0.32 ± 0.06
0.47 ± 0.08
0.44 ± 0.11
0.50 ± 0.06
GPT-6.1 Sol
0.22 ± 0.06
0.99 ± 0.01
0.24 ± 0.08
0.91 ± 0.03
Grok 4.20 (Reasoning)
0.17 ± 0.07
0.11 ± 0.04
0.17 ± 0.07
0.08 ± 0.03
Grok 4.20 (Non-Reasoning)
0.00 ± 0.00
0.00 ± 0.00
0.00 ± 0.00
0.00 ± 0.00
DeepSeek-V4-Pro (Non-Thinking)
0.00 ± 0.00
0.00 ± 0.00
0.02 ± 0.02
0.01 ± 0.01
Appendix
Table 13: Rich models: hit@1 and recall given the text and given every coefficient, mean ± standard error over 24 instances.
s=2
s=3
Order
text
coefficients
text
coefficients
Random order
17.33 ± 1.31
17.53 ± 4.83
Covering order
13.56 ± 1.19
10.45 ± 3.30
Lookahead order
3.87 ± 1.48
1.00 ± 0.00
GCG anchor (16 instances)
15.23 ± 1.72
15.80 ± 4.70
JointDW
Appendix
Table 14: Rich models: number of evaluations until a best set is evaluated, mean ± standard error over 24 instances. The GCG anchor exists on the lot-sizing and facility-location models.
names as given
names permuted
names anonymized
Configuration
hit@1
recall
hit@1
recall
hit@1
recall
Pooled
GPT-6.1 Sol
0.99 ± 0.01
0.91 ± 0.03
0.99 ± 0.01
0.83 ± 0.04
1.00 ± 0.00
0.86 ± 0.04
Claude Sonnet 5.5
0.47 ± 0.08
0.50 ± 0.06
0.11 ± 0.04
0.15 ± 0.05
0.28 ± 0.06
0.40 ± 0.05
Lot sizing
GPT-6.1 Sol
1.00 ± 0.00
0.84 ± 0.06
1.00 ± 0.00
0.71 ± 0.07
1.00 ± 0.00
0.75 ± 0.07
Appendix
Table 15: Control presentations with every coefficient on the 24 rich models. Top: hit@1 and recall, mean ± standard error, when the family names are shown as given, permuted among the families, or replaced by labels, pooled and by class. Bottom: number of evaluations until a best set is evaluated for JointDW and for its interleaving with the lookahead order at the HiGHS dual, pooled over the 24 instances.
JointDW minus five-dual
Interleaved minus five-dual
Configuration
names
s=2
s=3
s=2
s=3
Pooled
Claude Sonnet 5.5
as given
3.96 ± 0.95 ∗
3.53 ± 0.51 ∗
0.18 ± 0.32
0.62 ± 0.08 ∗
permuted
9.02 ± 1.06 ∗
9.18 ± 2.04 ∗
0.76 ± 0.10 ∗
0.86 ± 0.05 ∗
anonymized
6.72 ± 1.10 ∗
6.56 ± 1.31 ∗
0.17 ± 0.54
0.72 ± 0.06 ∗
GPT-6.1 Sol
as given
− 0.56 ± 0.74
1.10 ± 0.46 ∗
− 0.71 ± 0.71
0.18 ± 0.08 ∗
Appendix
Table 16: Rich models with every coefficient: paired differences in the number of evaluations until a best set is evaluated, JointDW and its interleaving with the five-dual lookahead order minus the five-dual lookahead order, for s=2 and s=3 , pooled over the 24 instances and by class, with every coefficient shown, with the family names as given and, for two configurations, permuted or anonymized. Mean ± standard error of the cluster bootstrap over prompt groups, with an asterisk when the 95 percent interval excludes zero.
hit@1
evaluations
Instances
s
learned
five duals
learned order
staged
labeling cost
n
Within class, structural features
Templates
2
0.81 ± 0.11
0.92 ± 0.08
1.25 ± 0.20
1.21 ± 0.15
19.7
14
Templates
3
0.86 ± 0.10
1.00 ± 0.00
1.33 ± 0.28
1.19 ± 0.14
28.5
15
Rich models
2
0.96 ± 0.03
0.96 ± 0.04
1.11 ± 0.05
2.38 ± 0.74
235.7
24
Rich models
3
0.42 ± 0.13
0.04 ± 0.05
1.90 ± 0.59
3.23 ± 1.36
595.0
24
Appendix
Table 17: Learned predictor: hit@1 of its first set and of the five-dual lookahead order, number of evaluations until a best set is evaluated for the learned order and for the staged search anchored at its first set, mean ± standard error, the mean labeling cost of the training set in evaluations, and the number of test instances, by split and variant, for s=2 and s=3 . Templates: the instances with a positive gain at s for the within-class split, and the nine structured templates for the leave-one-class-out split.
training instances
Class
features, s
1
2
4
7
labeling cost
Facility location
structural, 2
6.05 ± 1.32
3.30 ± 1.14
1.11 ± 0.03
1.05 ± 0.03
28, 56, 112, 196
structural, 3
1.60 ± 0.14
1.52 ± 0.17
1.10 ± 0.07
1.00 ± 0.00
63, 126, 252, 441
structural and lookahead, 2
11.16 ± 1.15
6.78 ± 1.27
4.40 ± 1.21
1.10 ± 0.07
28, 56, 112, 196
structural and lookahead, 3
1.06 ± 0.03
1.05 ± 0.04
1.00 ± 0.00
1.00 ± 0.00
63, 126, 252, 441
Lot sizing
structural, 2
1.40 ± 0.02
1.31 ± 0.02
1.25 ± 0.02
1.34 ± 0.06
45, 90, 180, 315
Appendix
Table 18: Learned predictor against the number of training instances of the same class on the rich models: number of evaluations until a best set is evaluated for the learned order, mean ± standard error over 20 random draws of the training set, with the labeling cost of each training set in evaluations.
first set and the best pair
first set and the time-optimal set
Method
is best
gain
zero gain
is time-optimal
within 10%
time ratio
Lot sizing, 20 instances
Best pair
1.00 ± 0.00
0.964 ± 0.005
0
0.95 ± 0.05
1.00 ± 0.00
1.000 ± 0.000
Lookahead (HiGHS dual)
1.00 ± 0.00
0.964 ± 0.005
0
0.95 ± 0.05
1.00 ± 0.00
1.000 ± 0.000
Lookahead (five duals)
1.00 ± 0.00
0.964 ± 0.005
0
0.95 ± 0.05
1.00 ± 0.00
1.000 ± 0.000
GCG’s detector
1.00 ± 0.00
0.964 ± 0.005
0
0.95 ± 0.05
1.00 ± 0.00
0.882 ± 0.040 ∗
Appendix
Table 19: Benchmark instances, per class and method: share of instances on which the first set is the best pair, gain of the first set as a share of the LP gap, number of instances on which this gain is zero, share on which the first set is the time-optimal set, strictly and within the tolerance (as many solved seeds and at most 1.1 times its time statistic), and time ratio. Mean ± standard error of the two-stage bootstrap; time ratios as geometric means, with an asterisk when the 95 percent interval of the mean log ratio excludes zero. The best pair is a reference. JointDW uses the original presentation with three samples per instance, averaged within an instance.
difference in the log time ratio
time-optimal
Method
minus
LS
ND
FL
all
all
JointDW with GPT-6.1 Sol
Lookahead (HiGHS dual)
0.00 ± 0.00
− 0.90 ± 0.82
− 0.46 ± 0.56
− 0.45 ± 0.39
0.19 ± 0.12
Lookahead (five duals)
0.00 ± 0.00
− 0.82 ± 0.83
− 0.02 ± 0.03
− 0.29 ± 0.34
0.14 ± 0.11
GCG’s detector
0.13 ± 0.05 ∗
− 0.75 ± 0.34 ∗
− 1.15 ± 0.12 ∗
− 0.58 ± 0.29 ∗
0.42 ± 0.17 ∗
JointDW with Claude Sonnet 5.5
Lookahead (HiGHS dual)
0.00 ± 0.00
− 0.99 ± 0.63
− 0.20 ± 0.53
− 0.40 ± 0.36
0.17 ± 0.15
Lookahead (five duals)
0.00 ± 0.00
− 0.90 ± 0.59
0.24 ± 0.10 ∗
− 0.23 ± 0.29
0.12 ± 0.15
Appendix
Table 20: Benchmark instances: paired differences in the share of instances on which the first set is the time-optimal set (all instances) and in the logarithm of the time ratio (per class and all instances), JointDW under the original presentation minus a baseline, and the five-dual lookahead minus GCG’s detector. Mean ± standard error of the two-stage bootstrap, with an asterisk when the 95 percent interval excludes zero. Negative log ratios favor the first method.
difference in hit@1
difference in gain
Method
minus
ND
FL
all
ND
FL
all
JointDW with GPT-6.1 Sol
Lookahead (HiGHS dual)
0.32 ± 0.24
0.32 ± 0.24
0.21 ± 0.14
0.18 ± 0.15
0.32 ± 0.24
0.16 ± 0.11
Lookahead (five duals)
0.32 ± 0.24
0.05 ± 0.07
0.12 ± 0.11
0.17 ± 0.14
0.05 ± 0.07
0.07 ± 0.06
GCG’s detector
0.67 ± 0.16 ∗
1.00 ± 0.00 ∗
0.55 ± 0.21 ∗
0.80 ± 0.11 ∗
1.00 ± 0.00 ∗
0.59 ± 0.22 ∗
JointDW with Claude Sonnet 5.5
Lookahead (HiGHS dual)
0.40 ± 0.25
0.00 ± 0.26
0.14 ± 0.15
0.20 ± 0.17
0.00 ± 0.26
0.07 ± 0.11
Lookahead (five duals)
0.40 ± 0.25
− 0.26 ± 0.10 ∗
0.05 ± 0.14
0.19 ± 0.16
− 0.26 ± 0.10 ∗
− 0.02 ± 0.10
Appendix
Table 21: Benchmark instances: paired differences in hit@1 and in the gain of the first set as a share of the LP gap, JointDW under the original presentation minus a baseline, and the five-dual lookahead minus GCG’s detector, on network design (ND, 20 instances), facility location (FL, 19), and all 59 instances; on lot sizing, every difference is zero. Mean ± standard error of the two-stage bootstrap, with an asterisk when the 95 percent interval excludes zero.
Sets
number
solved
time statistic (s)
pricing share
nodes
Lot sizing, 20 instances
Best pair
20
0.85
571.6
0.78
13913
Other pairs
40
0.00
1801.0
0.25
12269
Single families
60
0.11
1665.1
0.17
23232
All three families
20
1.00
6.7
–
–
Network design, 20 instances
Appendix
Table 22: Benchmark instances, branch-and-price on the sets of at most two families and on all three, per class: number of sets, share of runs solved within 1800 seconds, mean time statistic in seconds, mean share of the solve time spent in pricing, and mean number of nodes. The set of all three families leaves an empty master; its pricing share and nodes are not comparable and are omitted.
JointDW with
hit@1
gain of first set
time-optimal
time ratio
no joint support
Lot sizing, 20 instances
GPT-6.1 Sol
1.00 ± 0.00
0.964 ± 0.005
0.95 ± 0.05
1.000 ± 0.000
0
Claude Sonnet 5.5
0.95 ± 0.03
0.934 ± 0.020
0.90 ± 0.05
0.994 ± 0.076
1
Network design, 20 instances
GPT-6.1 Sol
0.40 ± 0.07
0.688 ± 0.049
0.37 ± 0.07
7.658 ± 3.665 ∗
0
Claude Sonnet 5.5
0.17 ± 0.06
0.514 ± 0.065
0.13 ± 0.04
10.777 ± 5.153 ∗
0
Appendix
Table 23: Benchmark instances with every coefficient shown, JointDW with three samples per instance, averaged within an instance. Top: hit@1, gain of the first set as a share of the LP gap, share of instances on which the first set is the time-optimal set, time ratio, and number of answers without a joint support. Bottom: paired differences, JointDW with every coefficient shown minus a baseline or minus the same configuration in the original presentation, in hit@1, in the gain, and in the logarithm of the time ratio. Mean ± standard error of the bootstrap over instances, with an asterisk when the 95 percent interval excludes zero (time ratio: of the mean log ratio).
hit@1 against
time ratio to
false
outside
Method
best bound
time-optimal
time-optimal
GCG as shipped
alarms
budget
Generalized assignment, 60 instances
Best set
1.00 ± 0.00
1.00 ± 0.00
1.00 ± 0.00
1.01 ± 0.02
–
0
Lookahead (HiGHS dual)
0.97 ± 0.03
0.97 ± 0.03
1.01 ± 0.01
1.02 ± 0.03
–
0
Lookahead (five duals)
1.00 ± 0.00
1.00 ± 0.00
1.00 ± 0.00
1.01 ± 0.02
–
0
GCG’s detector
1.00 ± 0.00
1.00 ± 0.00
0.99 ± 0.02
1.00 ± 0.00
–
0
Appendix
Table 24: Instances without a joint support, per class and method: hit@1 against the set with the best bound (bin packing: the 12 instances where some set within the budget has a positive gain) and against the time-optimal set, time ratio to the time-optimal set and to GCG as shipped, false alarms (answers that name a joint support on an instance where the capacity family alone closes the whole gap), and samples or instances whose set lies outside the budget. Mean ± standard error of the two-stage bootstrap; time ratios as geometric means, with an asterisk when the 95 percent interval of the mean log ratio excludes zero.
hit@1
recall
Configuration
12
16
all
12
16
all
GPT-6.1 Sol, text
0.09 ± 0.04
0.07 ± 0.03
0.07 ± 0.02
0.06 ± 0.03
0.02 ± 0.01
0.04 ± 0.02
GPT-6.1 Sol, coefficients
0.99 ± 0.01
1.00 ± 0.00
0.99 ± 0.01
0.85 ± 0.03
0.56 ± 0.06
0.75 ± 0.03
Claude Sonnet 5.5, text
0.18 ± 0.06
0.10 ± 0.05
0.13 ± 0.04
0.11 ± 0.03
0.03 ± 0.01
0.08 ± 0.02
Claude Sonnet 5.5, coefficients
0.28 ± 0.06
0.37 ± 0.08
0.27 ± 0.04
0.14 ± 0.03
0.07 ± 0.02
0.11 ± 0.02
Appendix
Table 25: Rich models with 12 to 16 families, pooled over the classes. Top: hit@1 and recall given the text and given every coefficient. Bottom: number of evaluations until a best set is evaluated for s=2 and s=3 . Columns 12: the 30 models with 12 families; 16: the 20 lot-sizing and facility-location models with 16 families; all: the 60 models, including the network-design models with 14 families, which enter only for s=2 . Mean ± standard error of the two-stage bootstrap.
Class
k
e
predictions
staged order
JointDW
stage queries
covering
Lot sizing
9
0
62
1.00 ± 0.00
1.00 ± 0.00
1
18.7
1
4
8.57 ± 0.08
12.25 ± 0.14
15
18.9
2
3
26.00 ± 0.11
23.44 ± 0.16
36
18.4
cut (0.91)
27
10.54 ± 0.84
12.47 ± 0.67
–
–
12
0
72
1.00 ± 0.00
1.00 ± 0.00
1
33.7
1
5
11.47 ± 0.09
17.79 ± 0.12
21
33.8
Appendix
Table 26: Rich models, s=2 : number of evaluations until a best pair is evaluated, by the number e of its members that the anchor misses, for the staged order O1 alone and for JointDW, with the number of queries of stages 0 to e of Theorem 2 (a) and the mean cost of the covering order on the same instances. Rows marked cut: anchors with more than two families, with their mean number of misses after the cut in parentheses. Predictions of GPT-6.1 Sol and Claude Sonnet 5.5 under both presentations. Mean ± standard error of the two-stage bootstrap.
Class
k
predictions
share of orders
JointDW
covering
Lot sizing
9
32
0.89
11.01 ± 0.75
36.0
12
43
0.93
18.70 ± 3.62
106.1
16
24
0.96
14.66 ± 7.35
160.9
Network design
12
37
0.98
10.91 ± 2.10
56.2
Facility location
12
19
0.45
64.07 ± 2.15
91.5
16
38
0.67
77.29 ± 15.05
160.3
Appendix
Table 27: Rich models, s=3 : predictions whose anchor has two families while the best set has three. Share of the orders of the families in which the staged order O1 alone reaches a best set, number of evaluations of JointDW as mean ± standard error, and mean cost of the covering order on the same instances.
evaluations saved against
net time saved against
Configuration
latency
cost
covering
five duals
covering
five duals
break-even
Templates; one evaluation 0.094 s
GPT-6.1 Sol, text
34.9
0.011
1.53 ± 0.48 ∗
− 0.19 ± 0.11
− 34.8 ± 2.3 ∗
− 34.9 ± 2.3 ∗
22.9
Claude Sonnet 5.5, text
157.2
0.212
1.30 ± 0.52 ∗
− 0.41 ± 0.14 ∗
− 157.0 ± 18.4 ∗
− 157.2 ± 18.4 ∗
120.5
MIPLIB-NL; one evaluation 43.3 s
GPT-6.1 Sol, text
35.8
0.012
1.74 ± 0.43 ∗
− 0.17 ± 0.17
39.6 ± 18.0 ∗
− 42.9 ± 7.5 ∗
20.5
Appendix
Table 28: Cost of a prediction for JointDW interleaved with the five-dual lookahead order, s=2 : latency (s) and cost (USD) of one prediction at list prices, evaluations saved against the covering order and against the five-dual order, net time saved (s) against both, and break-even time of one evaluation (s) against the covering order. Mean ± standard error of the two-stage bootstrap, with an asterisk when the 95 percent interval excludes zero.
families convexified
slope
Collection
1
2
3
4
5
models
median
25%
75%
MIPLIB-NL, census time
1.53
4.24
16.9
18.3
17.8
41
1.65
0.66
2.26
Templates, census time
0.0900
0.0900
0.0890
0.0890
0.0930
4
0.02
0.02
0.03
Templates, GCG time
0.0145
0.0126
0.0134
0.0128
0.0133
4
0.22
0.15
0.29
Rich models, census time
0.0880
0.100
0.105
–
–
24
0.14
0.07
0.17
Rich models, GCG time
0.0158
0.0243
0.0291
–
–
24
0.50
0.33
0.62
Appendix
Table 29: Median time of one evaluation in seconds by the number of convexified families, over the sets that finish within the time limit, and the slope of the logarithm of the median time against the logarithm of the number of families: number of models with at least three sizes, median and quartiles of their slopes. Census time: the time of the census evaluation; GCG time: the time that GCG reports.
JointDW minus
Interleaved minus
Configuration
covering
lookahead
covering
lookahead
Templates, s=2
Claude Sonnet 5.5
− 0.38 ± 0.19 ∗
0.47 ± 1.06
− 0.90 ± 0.84
− 0.04 ± 0.32
GPT-6.1 Sol
− 0.79 ± 0.10 ∗
0.07 ± 1.19
− 1.65 ± 0.51 ∗
− 0.79 ± 0.82
Grok 4.20 (Reasoning)
− 0.38 ± 0.15 ∗
0.48 ± 1.10
− 0.98 ± 0.77
− 0.12 ± 0.38
Grok 4.20 (Non-Reasoning)
0.06 ± 0.20
0.92 ± 1.06
− 0.45 ± 0.94
0.41 ± 0.23 ∗
Appendix
Table 30: Paired differences in the number of evaluations: JointDW or its interleaving with the lookahead order minus the covering or the lookahead order, mean ± standard error. Negative values favor JointDW or the interleaved order, and an asterisk marks a difference whose 95 percent bootstrap interval excludes zero, with each cell tested separately.
Table 31: First set of a language model and first set of the five-dual lookahead order on the instances with a true joint support and, for the benchmark instances, with a best pair: hit@1 of the language model, share of instances on which only the language model, only the lookahead, and at least one of the two names a true group first, mean ± standard error. The outcome of a sample is averaged over the samples of an instance and then over the instances. On the nine structured templates, the five-dual lookahead names a true group first on every instance.
Mixed-Integer Linear Programming (MILP) is a fundamental tool for combinatorial optimization with extensive real-world applications. A central challenge is designing computationally efficient MILP formulations. Large Language Models (LLMs) offer new opportunities to automate the modeling process, from deriving formulations to strengthening them. Reliable automation requires robust methods for verifying that proposed formulations preserve the underlying optimization problem. However, existing approaches evaluate formulations numerically and fail to reason about general problem instances. We resolve this limitation by introducing a constructive definition of MILP reformulation that can be formalized in Lean and machine-checked. We develop FLARE (Formulation-Level Automated Reformulation Evaluation), a method that uses an LLM-based agent and the Lean proof assistant to verify proposed reformulations against a reference formulation. To evaluate our approach, we introduce FormulationBench, a challenging dataset of 20 problems and 109 formulations. FLARE outperforms existing methods, with 100% accuracy on the NP-hard subset of FormulationBench. Furthermore, FLARE produces a machine-checkable certificate for every reformulation it accepts. For cases where formal guarantees are not necessary, we introduce FLARE-NL, a fast and cheap LLM proxy that matches FLARE's accuracy but produces no certificate. These methods enable reliable verification in automated optimization modeling.
Large language models are increasingly applied to operational decision-making where the underlying structure is constrained optimization. Existing benchmarks evaluate whether LLMs can formulate optimization problems as solver code, but leave open a complementary question. Can LLMs directly produce correct solutions to fully specified constrained optimization problems without access to a solver? We introduce ConstraintBench, a benchmark for evaluating LLMs on direct constrained optimization across 10 operations research domains, with all ground-truth solutions verified by the Gurobi solver. Each task presents a natural-language scenario with entities, constraints, and an optimization objective; the model must return a structured solution that a deterministic verifier checks against every constraint and the solver-proven optimum. We evaluate six frontier models on 200 tasks and find that feasibility, not optimality, is the primary bottleneck. The best model achieves only 65.0% feasibility, yet feasible solutions average 89 to 96% of the Gurobi-optimal objective. No model exceeds 30.5% on joint feasibility and optimality within 0.1% of the solver reference. Per-domain analysis shows large variation in difficulty, with average feasibility spanning from 85.0% in the facility location domain to 0.8% in the crew assignment domain. Further, systematic failure modes include duration constraint misunderstanding, entity hallucination, and a feasibility-optimality decoupling in facility location and vehicle routing where models achieve high feasibility but 0% optimality. ConstraintBench and all evaluation infrastructure will be publicly released.
Optimization problems are pervasive in sectors from manufacturing and distribution to healthcare. However, most such problems are still solved heuristically by hand rather than optimally by state-of-the-art solvers because the expertise required to formulate and solve these problems limits the widespread adoption of optimization tools and techniques. We introduce a Large Language Model (LLM)-based system designed to formulate and solve (mixed integer) linear programming problems from their natural language descriptions. Our system can develop mathematical models, write and debug solver code, evaluate the generated solutions, and improve efficiency and correctness of its model and code based on these evaluations. OptiMUS is designed as a productivity tool for optimization practitioners who understand the problem domain and can describe it precisely, but seek to accelerate the modeling and implementation workflow. OptiMUS-0.3 utilizes a modular structure to process problems, allowing it to handle problems with long descriptions and complex data without long prompts. Experiments demonstrate that OptiMUS-0.3 outperforms direct-prompting baselines by over 43% on easy and 18% on hard instances. It remains competitive with fine-tuned specialist models on benchmark problems, and outperforms them on real-world case studies (28.6% vs. 0%) where fine-tuned models fail to generalize. Ablation studies show that modular architecture with error correction is central to these gains. A key finding is that system architecture is a stronger driver of performance than model capability. Structured decomposition with targeted error correction enables weaker models to match stronger models under naive prompting, and remains competitive with fine-tuned specialist models without retraining costs.
Ali AhmadiTeshnizi, Wenzhi Gao, Herman Brunborg +3
a School of Management Science and Engineering, Stanford University, Stanford, California 94305 · b Institute for Computational and Mathematical Engineering, Stanford University, Stanford, California 94305