cs.LGNov 3, 2026

Do Language Models Know Which Constraints Belong Together?

Authors: Junbo Jacob Lian, Kaixuan Chen, Hanzhang Qin, Huiling Chen, Chaoyu Zhang, Chung-Piaw Teo

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 ss of kk families, methods that observe only bounds need of order kwk^w evaluations to find a hidden group of ww families in the worst case. A prediction missing ee members reduces this to Θ(ke)Θ(k^e) through a staged search that need not know ee. 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

Appendix figures & tables27 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. FLARE: Verifying MILP Reformulations with LLM-Based Theorem Proving

    Aug 25, 2026Henry Robbins, Connor Lawless, Madeleine Udell +1Mixed-Integer Linear ProgrammingFormal Verification

  2. OptiMUS-0.3: Using Large Language Models to Model and Solve Optimization Problems at Scale

    Jul 29, 2024Ali AhmadiTeshnizi, Wenzhi Gao, Herman Brunborg +3Mixed-Integer Linear ProgrammingLarge Language Model-Guided Optimization