Autoformulation of Mathematical Optimization Models Using LLMs

Authors: Nicolás Astorga, Tennison Liu, Yuanzhang Xiao, Mihaela van der Schaar
Primary area: applications to robotics, autonomy, planning
Keywords: Large Language Models, optimization modeling

Abstract:
Mathematical optimization is fundamental to decision-making across diverse domains, from operations research to healthcare. Yet, translating real-world problems into optimization models remains a formidable challenge, often demanding specialized expertise. This paper formally introduces the concept of *autoformulation*---an automated approach to creating optimization models from natural language descriptions for commercial solvers.
We identify the three core challenges of autoformulation: (1) defining the vast, problem-dependent hypothesis space, (2) efficiently searching this space under uncertainty, and (3) evaluating formulation correctness (ensuring a formulation accurately represents the problem).
To address these challenges, we introduce a novel method leveraging *Large Language Models* (LLMs) within a *Monte-Carlo Tree Search* framework. This approach systematically explores the space of possible formulations by exploiting the hierarchical nature of optimization modeling.  LLMs serve two key roles: as dynamic formulation hypothesis generators and as evaluators of formulation correctness. To enhance search efficiency, we introduce a pruning technique to remove trivially equivalent formulations. 
Empirical evaluations across benchmarks containing linear and mixed-integer programming problems demonstrate our method's superior performance. Additionally, we observe significant efficiency gains from employing LLMs for correctness evaluation and from our pruning techniques.

Decision: reject
Reviewer scores: 5, 6, 6, 5

Reviews and discussion:
<thread>
creation date:
1729794106544

thread_type:
official_review

<thread_object>
creator: reviewer_mbtn

<content>
summary:
This paper proposed a MCTS-enhanced LLM approach, to transform descriptions of certain types of optimization problems into formal optimization models consisting of (1) variables, (2) objective, (3) equality constraints and (4) inequality constraints. The MCTS has a depth of 4 corresponding to the four components of an optimization model. When expanding a node, LLMs are used to generate a set of candidate formulations, and trivally identical formulations are pruned by SMT solvers to improve efficiency. The expanded nodes will be assigned a prior by an LLM-based ranking evaluation. The reward at the terminal node is a combination of LLM evaluation and whether optimality is reached from solvers. Experimental results show that the proposed approach outperforms other non-MCTS approaches.

strengths:
1. Good writing, easy to follow.
2. Specific improvements on MCTS to fit the optimization scenario (merging trivially equivalent formulations, including solver signals to rewards, etc.)
3. Sufficient experimental details.

weaknesses:
1. The rationality of the definition of "autoformulation" is not sufficiently backed by the main part of the paper. The connection between the problem setting and the proposed method is not very clear. For the definition, two transformations are highlighted (mathematical formulation model $p_\phi$ and computational representation model $p_\psi$), and "autoformulation" is defined to jointly optimize $(\phi, \psi)$ so that the expection of a quality function $Q$ is maximized. This problem setting is a bit different from other "LLM+OR" papers.  However, in the main part of the paper, no clear effort is paid on optimizing parameters, neither $\phi$ nor $\psi$ (GPT-4 is used without fine-tuning). I feel that the main objective of this paper is still the same as other papers, proposing a $P_{\phi\text{-LLM}}^\text{improved}$ that empirically performs better than a vanilla use of $P_{\phi\text{-LLM}}$. So I am a bit confused why bother to propose such a definition. Specifically, it seems unneeded to have a probabilistic model $p_\psi$ with complex joint optimization, if the computational representation step can be simply done by a deterministic parser (line 241) or commertial packages (line 194).
2. There are already lots of literatures working on combining LLMs with MCTS to solve general or domain-specific problems (see arXiv:2309.17179, arXiv:2402.03289, arXiv:2409.09584, arXiv:2406.07394, arXiv:2402.08147 for some examples), in both training and inference stage, which may unfortunately raise the bar for another "LLM+MCTS" paper to appear on top conferences. It is good to have LLM+MCTS applied on OR problems, but more unique features might be required to distinguish this paper. This paper has paid some effort on it (see Strength 2), but apart from these adaptations, the whole LLM+MCTS pipeline seems quite standard, and only applied at the inference stage.
3. While LLM contains general knowledge of optimization, the proposed method is limited to (reformulated) convex problems (type I and II in this paper).

questions:
Questions:
1. Why having a probabilistic model $p_\psi$ with complex joint optimization in Section 2.1? (See Weaknesses 1 for details)

Suggestions:
1. Highlight the relation and difference between this paper and other works combining LLMs with MCTS.
2. Align the problem definition and the methods. If the quality of computational representation is not sufficiently addressed in this paper, the problem definition may not be so complex. (In my opinion, a method which fit the current problem definition will be, for example, bi-level finetuning of two LLMs $p_\phi$ and $p_\psi$ to maximize $Q$)
3. It may worth fine-tuning the model with MCTS-based self enhancement in the future (check arXiv:2309.17179 for an example).
</content>
</thread_object>

</thread>
<thread>
creation date:
1730009681223

thread_type:
official_review

<thread_object>
creator: reviewer_utyj

<content>
summary:
This paper identifies three core challenges: defining the vast, problem-dependent hypothesis space, efficiently searching this space under uncertainty, and evaluating the correctness of formulations. 

To tackle these issues, the authors propose a novel method that leverages Large Language Models (LLMs) within a Monte-Carlo Tree Search framework. LLMs function as both hypothesis generators and evaluators of formulation correctness, while a pruning technique is employed to eliminate trivial equivalent formulations. 

Empirical evaluations demonstrate that this approach significantly improves the efficiency and accuracy of formulating optimization models for linear and mixed-integer programming problems, making it accessible to users without deep optimization expertise.

strengths:
- The paper provides a clear and compelling description of the motivation behind the research, along with a well-articulated explanation of the proposed method.
- It includes an extensive experimental comparison that effectively demonstrates the performance and advantages of the proposed approach relative to existing methods.

weaknesses:
- In my experience with Operations Research, many papers focus on formulating new problems into linear programming or mixed-integer linear programming. These papers typically begin with a clear textual definition of the problem, followed by rigorous proofs, given the critical applications involved. However, I find that this work may not be particularly useful for practitioners in the field, as they still need to undertake similar formulation efforts themselves. The primary benefit seems to lie in providing students with examples for their coursework rather than advancing practical applications for researchers and professionals.

- In line 128, the quote from the textbook stating, "Once this formulation is done, solving the problem is ... (almost) technology," highlights a distinction from the problem formulation presented in this paper. The textbook emphasizes identifying the context of the problem, extracting the decision variables, and compiling all relevant real-world constraints, which cannot be adequately captured through mere textual descriptions.

questions:
Could you clarify how the developed system will be utilized by domain scientists or in other potential use cases?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730648867779

thread_type:
official_review

<thread_object>
creator: reviewer_u3rw

<content>
summary:
This paper introduces a framework to automate the creation of mathematical optimization models from natural language descriptions. This process is essential in operations research but traditionally requires significant expertise. There are three main challenges for autoformulation: defining a vast hypothesis space, navigating this space efficiently, and ensuring formulation correctness. To address these, the authors integrate LLMs within an MCTS framework, using LLMs to generate potential formulations and evaluate correctness. They also apply a pruning technique with SMT solvers to eliminate redundant formulations. Experiments on benchmarks for linear and mixed-integer programming show this approach is both accurate and efficient, potentially making optimization modeling more accessible.

strengths:
1. Leveraging LLMs for both hypothesis generation and evaluation enables verification of partial problems.
2. Using MCTS to efficiently navigate the large hypothesis space, along with introducing the SMT pruning procedure, saves computational resources and focuses on unique, meaningful formulations.
3. Strong experimental results compared to baselines.

weaknesses:
1. The same LLM is used for both hypothesis generation and verification, which introduces a high correlation between generation and evaluation stages. This could limit the objectivity and diversity of the verification.

2. Lacks a clear explanation of how the LLM is guided to explore the hypothesis space with sufficient diversity.

3. It would be beneficial to provide more insight into partial problem formulation at intermediate steps. Improved verification of partial models could enhance accuracy and reduce runtime for complex problems.


Minor issue: The font size in the figures is too small

questions:
1. In Section 5.2, paragraph (2) ‘Getting Local Scores,’ how does the DFS expand the tree? Does it expand the child with the highest prior score first, or does it expand a random model generated by the LLM?

2. How should Figure 5 be interpreted? Section 5.4 doesn’t seem directly related.

3. How is exploration of the hypothesis space ensured? Figure 4 shows that pruning is effective, but does this imply that the LLM fails to generate diverse partial formulations?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731124125383

thread_type:
official_review

<thread_object>
creator: reviewer_e8hb

<content>
summary:
This paper is along the popular direction of using LLM to automatically fomulate mathematical optimization problems. It introduces a formal definition of autoformulation and identifies three main challenages. To address these challenges, the authors propose a method using large language models (LLMs) within a Monte-Carlo Tree Search (MCTS) framework. LLMs are utilized both as hypothesis generators and evaluators, while MCTS incrementally explores the formulation space. Additionally, a pruning technique based on Satisfiability Modulo Theories (SMT) solvers is introduced to eliminate redundant, trivially equivalent formulations. The method was tested on benchmarks (NL4OPT and IndustryOR) and show superior results.

strengths:
1. The approach to utilize LLM both as hypothesis generators and evaluators seems novel.  
2. A pruning technique based on Satisfiability Modulo Theories (SMT) solvers is introduced to eliminate redundant, trivially equivalent formulations, which can improve the search efficiency in my understanding.

weaknesses:
1. The concept of autoformulation defined in this paper is broad, including mathematical formulation and computational formulation, and optimality gap and computational efficiency. However, the main contribution of this paper is on mathematical formulation if I understand correctly. The rest in the proposed concept is not addressed in this paper.
2. I do not see why adding optimality gap and computational efficiency to the evaluation metric. They're solver dependent and is not the responsbility of formulation.
3. The authors defined Types I to Types III problems, but I do not see how they are related to the main contribution of this paper.
Overall, I feel like the concept proposed in this paper is too broad and distract readers from the main contribution of this paper.

questions:
1. Can you justify why optimality gap and computational efficiency, which depends on solver, are also included in the evalutation metric?
2. What is the relationship of Types I to Types III problems with the rest of this paper?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732185102183

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Response

comment:
_We thank the reviewers for their constructive comments and their commitment to the review process._

---

We are encouraged that reviewers found our methodology novel, particularly in "utilizing LLM both as hypothesis generators and evaluators" (**e8hb**, **U3Rw**), enabling crucial "verification of partial problems" (**U3Rw**). The integration of MCTS with LLMs was recognized for its specific improvements "to fit the optimization scenario" (**mbTn**), while our SMT-based pruning technique was highlighted for its ability to "eliminate redundant, trivially equivalent formulations" and "improve search efficiency" (**e8hb**, **U3Rw**).

Reviewers appreciated the paper's clarity, noting its "good writing, easy to follow" presentation (**mbTn**) with a "clear and compelling description of the motivation" (**Utyj**). The technical contribution was strengthened by "sufficient experimental details" (**mbTn**) and "extensive experimental comparison" (**Utyj**), demonstrating "strong experimental results compared to baselines" (**U3Rw**).

We have also taken the reviewers’ feedback into account and made the following key changes to improve the paper:

* Relocated `Sec 2.2 Categorization of Problem Difficulty` to `App E` to improve flow and presentation
* Extended analysis of partial formulation evaluations (`App D.5`)
* Included empirical investigation on the impact of formulation and solver configuration on optimality gap and solution time (`App G`)

We have also uploaded a revised manuscript, where these changes are highlighted in teal for easier identification. We sincerely thank the reviewers for their valuable feedback on strengthening our work and remain open to further suggestions.

---
With thanks,

The Authors of #10599
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper considers a relevant problem of autoformalization but currently falls below par for ICLR conference because of following reasons:

- The paper uses a straightforward combination of existing ideas, each of which are widely studied in the literature now. For example, there is a lot of work on combining tree search with LLMs. This paper is mostly about applying existing techniques to a new problem. This is not necessarily bad because applying existing methods to new domains can be valuable, particularly when addressing real-world challenges but the current work primarily demonstrates these techniques on standard benchmarks. The broader claims about presenting a general framework lack enough technical validation.

- It would have been interesting to see any challenges that arise when applying these existing techniques to this problem and how they are addressed. For example, evaluating candidate formulations using LLMs is widely studied as “LLM-as-a-Judge”. It is presented as a gold standard solution but that is far from true.

- The paper has a disconnect between the problem formulation and actual implementation. Reviewer mbTn and e8hb have similar points in their review.

Please consider incorporating comments from the reviewers in the next cycle to improve the paper.