Astor improves translation of soft-constraint problems into optimization code
ASTOR: Benchmarking and Improving Autoformulation for Soft-Constraint Optimization with a Formal Grammar
Computation and Language
Summary
Many real-world decisions have two kinds of rules: hard rules that must be followed and soft preferences that can be bent. The authors show how large language models can help turn natural language problem descriptions into computer code that solves these mixed-rule decision problems. They introduce ASTOR, a method that uses a structured grammar approach to create better and more reliable optimization programs, especially for soft constraints. They also create a new benchmark, SoftOR, to test models on problems with soft constraints, where ASTOR performs well.
What this means in practice
- •For operations planners: Automatically create optimization models from natural language descriptions that include flexible preferences to support realistic decision-making.
- •For product managers: Incorporate customer or stakeholder soft preferences into automated resource allocation or scheduling software through natural language inputs.
Authors
Amer Goel, Yeganeh Alimohammadi, Andrew Daw
Abstract
Real-world decision problems combine two qualitatively different kinds of constraints: requirements that must be satisfied, called hard constraints, and preferences that can be violated, called soft constraints. Because these problems are often posed to decision-makers in natural language, large language models offer a natural tool for assisting with their solution. This has given rise to autoformulation, which focuses on using LLMs to translate natural-language descriptions of decision problems into executable mathematical optimization models. However, this research often neglects soft constraints like those proposed by consumers, managers, and planners, despite the fact that many practical problems require modeling them explicitly. We introduce ASTOR, an inference-time framework that maps a natural-language decision problem to a grammar-guided abstract syntax tree (AST) before deterministically compiling the resulting representation into executable optimization code. We also introduce SoftOR, a unified benchmark of natural language problems which focuses on soft constraint formulations. On SoftOR, ASTOR achieves the best aggregate accuracy among comparable single-request and multi-agent LLM methods while remaining competitive on standard autoformulation benchmarks that include only hard constraints. Code and data are available at https://anonymous.4open.science/r/astor-softor-iclr-E34C/README.md.