@inproceedings{jiang-etal-2026-reasoning-combinatorial,
    title = "Reasoning in a Combinatorial and Constrained World: Benchmarking {LLM}s on Natural-Language Combinatorial Optimization",
    author = "Jiang, Xia  and
      Chen, Jing  and
      Zhang, Cong  and
      Gao, Jie  and
      Hu, Chengpeng  and
      Zhang, Chenhao  and
      Wu, Yaoxin  and
      Zhang, Yingqian",
    editor = "Liakata, Maria  and
      Moreira, Viviane P.  and
      Zhang, Jiajun  and
      Jurgens, David",
    booktitle = "Findings of the {A}ssociation for {C}omputational {L}inguistics: {ACL} 2026",
    month = jul,
    year = "2026",
    address = "San Diego, California, United States",
    publisher = "Association for Computational Linguistics",
    url = "https://preview.aclanthology.org/ingest-acl/2026.findings-acl.1529/",
    pages = "30592--30648",
    ISBN = "979-8-89176-395-1",
    abstract = "While large language models (LLMs) have shown strong performance in math and logic reasoning, their ability to handle combinatorial optimization (CO){---}searching high-dimensional solution spaces under hard constraints{---}remains underexplored. To bridge the gap, we introduce NLCO, a **N**atural **L**anguage **C**ombinatorial **O**ptimization benchmark that evaluates LLMs on end-to-end CO reasoning: given a language-described decision-making scenario, the model must output a discrete solution without writing code or calling external solvers. NLCO covers 43 CO problems and is organized using a four-layer taxonomy of variable types, constraint families, global patterns, and objective classes, enabling fine-grained evaluation. We provide solver-annotated solutions and comprehensively evaluate LLMs by feasibility, solution optimality, and reasoning efficiency. Experiments across a wide range of modern LLMs show that high-performing models achieve strong feasibility and solution quality on small instances, but both degrade as instance size grows, even if more tokens are used for reasoning. We also observe systematic effects across the taxonomy: set-based tasks are relatively easy, whereas graph-structured problems and bottleneck objectives lead to more frequent failures. The benchmark dataset and code for data generation and evaluation are publicly available."
}