Do Language Models Know Which Constraints Belong Together?
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 ·
Abstract
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 of families, methods that observe only bounds need of order evaluations to find a hidden group of families in the worst case. A prediction missing members reduces this to through a staged search that need not know . 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
| Collection | Instances | 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 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 |
| 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 |
| Order | |||
|---|---|---|---|
| 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 |
| 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 |
Appendix figures & tables27 assets
Supplementary material from the paper’s appendix.
Appendix
| Class and families | Instance | LP gap (%) | Zero-marginal group | Gap closed (%) | |
| Lot sizing | LS | 3 | 32.4 | BS | 63 |
| B balance, S setup, C capacity | CS | 63 | |||
| LS b | 3 | 34.6 | BS | 60 | |
| CS | 57 | ||||
| LS | 3 | 22.0 | BS | 100 | |
| CS | 17 |
| Class | rows columns | LP gap (%) | best sets | groups | |
|---|---|---|---|---|---|
| Lot sizing | 9 | 15.2–51.7 | BS (4), BCS (3), BST (1), BSY (2) | 2–4 | |
| Network design | 7 | , | 2.8–30.1 | FU (8) | 1 |
| Facility location | 7 | , | 5.5–28.5 | AP (8) | 1–2 |
| Class | rows | columns | LP gap (%) | groups | positive gain, | |
|---|---|---|---|---|---|---|
| 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 |
| Class | Data | Instances | rows columns | LP gap (%) | Best pair |
|---|---|---|---|---|---|
| Lot sizing | Trigeiro et al. (1989) | 20 | 63.9–74.4 | balance, setup linking | |
| Network design | R set ( Crainic et al., 2001 ) | 20 | to | 0.05–10.6 | flow balance, arc capacity |
| Facility location | OR-Library cap ( Beasley, 1990 ) | 19 | to | 0.006–0.42 | assignment, capacity |
| 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 |
| 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 |
| 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 | ||
| 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 |
| 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 |
| 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 | ||||
| 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 |
| JointDW minus five-dual | Interleaved minus five-dual | ||||
| Configuration | names | ||||
| 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 ∗ |
| hit@1 | evaluations | ||||||
| Instances | learned | five duals | learned order | staged | labeling cost | ||
| Within class, structural features | |||||||
| Templates | 0.81 0.11 | 0.92 0.08 | 1.25 0.20 | 1.21 0.15 | 19.7 | 14 | |
| Templates | 0.86 0.10 | 1.00 0.00 | 1.33 0.28 | 1.19 0.14 | 28.5 | 15 | |
| Rich models | 0.96 0.03 | 0.96 0.04 | 1.11 0.05 | 2.38 0.74 | 235.7 | 24 | |
| Rich models | 0.42 0.13 | 0.04 0.05 | 1.90 0.59 | 3.23 1.36 | 595.0 | 24 | |
| training instances | ||||||
|---|---|---|---|---|---|---|
| Class | features, | 1 | 2 | 4 | 7 | labeling cost |
| Facility location | structural, | 6.05 1.32 | 3.30 1.14 | 1.11 0.03 | 1.05 0.03 | 28, 56, 112, 196 |
| structural, | 1.60 0.14 | 1.52 0.17 | 1.10 0.07 | 1.00 0.00 | 63, 126, 252, 441 | |
| structural and lookahead, | 11.16 1.15 | 6.78 1.27 | 4.40 1.21 | 1.10 0.07 | 28, 56, 112, 196 | |
| structural and lookahead, | 1.06 0.03 | 1.05 0.04 | 1.00 0.00 | 1.00 0.00 | 63, 126, 252, 441 | |
| Lot sizing | structural, | 1.40 0.02 | 1.31 0.02 | 1.25 0.02 | 1.34 0.06 | 45, 90, 180, 315 |
| 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 ∗ |
| 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 | |
| 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 | |
| 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 | |||||
| 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 |
| 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 |
| 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 |
| Class | 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 |
| Class | 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 |
| 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 |
| 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 |
| JointDW minus | Interleaved minus | |||
| Configuration | covering | lookahead | covering | lookahead |
| Templates, | ||||
| 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 ∗ |
| Configuration | hit@1 | only language model | only lookahead | at least one |
|---|---|---|---|---|
| MIPLIB-NL, 17 models; five-dual lookahead 0.53 0.12 | ||||
| Claude Sonnet 5.5 | 0.57 0.10 | 0.20 0.09 | 0.16 0.07 | 0.73 0.11 |
| GPT-6.1 Sol | 0.53 0.12 | 0.12 0.08 | 0.12 0.08 | 0.65 0.12 |
| Grok 4.20 (Reasoning) | 0.55 0.11 | 0.14 0.07 | 0.12 0.08 | 0.67 0.11 |
| Grok 4.20 (Non-Reasoning) | 0.29 0.10 | 0.06 0.04 | 0.29 0.11 | 0.59 0.11 |
| DeepSeek-V4-Pro (Non-Thinking) | 0.27 0.08 | 0.02 0.02 | 0.27 0.08 | 0.55 0.12 |
Mixed-Integer Linear Programming
Mixed-integer linear programming (MILP) optimizes linear objectives and constraints when some decisions must be integer-valued.
See all 53 papers