CAFA: Coding as Auto-Formulation Can Boost Large Language Models in Solving Linear Programming Problem

Authors: haoxuan  deng
bohao  zheng
yirui  jiang
hieu  tran
Venue: NeurIPS_cc_2024_Workshop_MATH-AI
Published: 2024-09-20 21:39:14

Abstract: Large language models (LLMs) open new doors for Operations Research (OR). While initial studies explored multi-agent strategies for LLMs in OR, our research challenges the assumption that such complex multi-step pipelines unnecessarily yield superior results for Linear Programming (LP) problems. This paper introduces a streamlined methodology: Coding as Auto-Formulation (CAFA). In comparison, CAFA is only one compact prompt guiding the LLMs to formalize the given problem text into lines of codes. The generated code will be post-processing for execution to get the answer. The proposed methods is tested on the NL4OPT dataset with different LLMs. Results suggest that despite its simplicity, consistently enhances LP problem-solving accuracy across different models. This study aims to shed light on better unleashing LLMs' mathematical reasoning capability with more streamlined prompts.

Main paper: 
 introduction: 
 Large Language Models (LLMs) have transformed natural language processing with their ability to understand, analyze, and generate human-like text. Their success has led to increasing interest in applying LLMs to solve mathematical word problems Cobbe et al. [2021] , drawing attention from the Operations Research (OR) field. Traditionally, solving OR problems like linear programming (LP) involves substantial human expertise to extract and formalize information for establishing optimization models and to use commercial solvers (CPLEX, Gurobi, etc.) to get the solution. The rise of LLMs offers the potential to automate this process, leading to the development of a new research area: LLMs for operations research (LLM4OR). Given that the research on LLM4OR is still in its early stages, this paper will narrow its focus specifically to the LP problem. Mathematically, LP is maximizing or minimizing a linear objective function, subject to linear inequality and equality constraints. It can be expressed as: min or max c T x, where Ax ≤ b, x ≥ 0(1) Where x is the vector of decision variables, c represents the coefficients of the objective function, and A and b define the parameters and limits of constraints.Recent research on this topic has explored various methods. The main idea is to carefully design instructions to guide the LLM to decompose the optimization process into a series of sub-tasks and solve them sequentially to derive the answer. Most of the research follows the abstract workflow illustrated in Figure 1 . Typically, the workflow mainly includes four components: 1). An analyzer for name-entity recognition of variables and relations in the given text for objectives and constraints A coder to compose a code snippet to call external solvers for problem-solving. 4). An executor (usually using a Python interpreter) runs the code to obtain the final solution.Remarkable works include Chain-of-Expert (CoE) Xiao et al. [2023] and OptiMUS AhmadiTeshnizi et al. [2024] . Both of these approaches employ multi-agent systems based on LLM by assigning multiple expert agents with distinct roles to implement the mentioned components of the LP optimization process to get the solution. OptiGuide Li et al. [2023] extends the applications of the proposed method to supply chain optimization, allowing non-technical users in the field of logistic to use optimization packages.Although the effectiveness of these methods have been demonstrated, their implementations rely on autonomous agent workflows that demand extensive prompt engineering and cutting-edge models like GPT-4 or Claude2. This raises two key questions: (1) Is a multi-agent framework with intensive prompt engineering essential for unlocking LLMs' problem-solving potential in LP tasks? (2) How can less-capable LLMs (open source models) be leveraged to reason and solve LP problems with reduced prompt engineering requirements? This paper seeks to address these two challenges.The remainder of this paper is organized as follows. Section 2 presents a probabilistic framework to model the multi-agent water flow diagram used for LP automation and analysis. Section 3 provides an in-depth discussion of the motivation behind and the design details of the CAFA framework.In Section 4, experimental evaluations are conducted on the NL4Opt dataset, with performance comparisons against selected baseline models. Section 5 addresses the limitations of the current approach and discusses potential directions for future research. Finally, the paper concludes with a brief summary of key findings. 
problem formulation and analysis: 
 Consider a Linear Programming (LP) problem presented in text, denoted as Q, and a language model L θ tasked with generating the correct answer A, where θ represents the fixed parameters of the pretrained model. The probability of obtaining the correct answer A, given the question Q, is expressed as P θ (A|Q). For simplicity, when using a single model L θ in a multi-step process, this probability can be abbreviated as P (A|Q).In a multi-agent framework, the final answer A is produced over n steps, resulting in A = A n . At each step i, an intermediate result A i is generated based on the corresponding prompt p i . Applying the chain rule, the probability of the final answer is decomposed as follows:EQUATIONIn a multi-agent system, it is often the case that the prompt p i is explicitly predefined and remains unchanged regardless of the answers generated in previous steps. Consequently, it is reasonable to assume that p i is independent of prior answers A i-1 , A i-2 , ..., A 1 . At each step, the answer A i depends solely on the current prompt p i , eliminating the need to track the entire history of previous answers. Thus, the probability expression simplifies asP (A i |A i-1 , p i ) = P (A i |p i ),allowing for a more streamlined version of the equation.EQUATIONSinceEQUATIONIn summary, the initial prompt p 1 is crucial in determining the correctness of the final answer. Moreover, the multi-step workflow does not always enhance performance, as subsequent steps may introduce error accumulation, which can degrade the overall accuracy of the solution. This thus answer the first question: chunking the LP solving procedure into multiple sequential steps and solve them one-by-one is not always lead to a better performance in the LP task.It is a note that equation 4 is not conflict to the main idea of Chain-of-Through (CoT), since equation 4 demonstrates the contribution of various prompts across sequential tasks, while CoT is only one prompt for a single task.3 Code as Auto-Formulation Prompting with Code Post-ProcessingAccording to the equation 4, the key lies in shrinking the problem-solving process into one step with well-design first prompt to obtain a better performance. For the LP problem-solving, it is unrealistic to enable the LLM to obtain correct answer directly by just zero-shot prompting. An alternative way is to let the LLM to generate an intermediate presentation (IR) of the text to disambiguate the problem for processing. According to Ramamonjison et al. [2022] , they use two-stages approach to convert the text into a context-free expression, specifically, a matrix representation of the constraints and objectives reported in the text. Then, the matrix is used to parse code to call solver to obtain the answer. Notice that the code is the expected output from the LLMs in the final step in all mentioned framework, to reduce the number of reasoning steps, we can instruct the LLM to generate the code in the one step as the formal representation. This idea is similar to Program-of-Through (PoT) Chen et al. [2023] , which also use code during reasoning instead of text. In our work, we want the LLMs to only generate code that can capture the constraints, parameters, limits, and objectives mentioned in the text.The complete LP-solving process is illustrated in Figure 2 . Initially, the problem text, along with the CAFA prompt, is input into the LLM for code generation. Additionally, a Pydantic parser is employed to ensure that the LLM generates code adhering to the specified format, thus enhancing consistency and reducing the likelihood of extraneous or incorrect string generation. The generated code represents a formal translation of the textual problem using the Python syntax of the Guribo  
experiment and results: 
 To evaluate the proposed methods, we utilize NL4Opt dataset originally introduced by Ramamonjison et al. [2022] . The baseline methods selected for comparison include Chain-of-Expert and OptiMUS.To assess the generalization of the approach across different models, we conduct experiments using GPT-4, GPT-3.5-turbo, deepseek-coder-v2-16B, and Llama3.1-8B.For performance evaluation, we employ Accuracy as the primary metric. If the output matches the correct answer provided in the dataset, the result is marked as correct for that specific question. Otherwise, it is considered incorrect. Accuracy is calculated as the ratio of correct solutions to the total number of questions.Table 1 demonstrate that the proposed method enhances performance in solving LP problems across various models. For GPT-3.5-Turbo and GPT-4, the CAFA method enables them to achieve competitive results compared to state-of-the-art approaches. Specifically, GPT-3.5-Turbo achieves 59% accuracy, outperforming both the Chain-of-Expert (CoE) and OptiMUS methods when using the same model. GPT-4 attains 70.1% accuracy, surpassing the CoE method, though lower than OptiMUS. However, unlike OptiMUS, CAFA requires only a single prompt, making system management, tuning, and optimization more straightforward for further improvement.For smaller LLMs, such as DeepSeek-Coder 16B and Llama 3.1 8B, the CAFA method significantly improves performance. Notably, DeepSeek-Coder achieves a performance level similar to GPT-3.5-Turbo, with 60% accuracy. This suggests that LLMs with strong coding capabilities can yield better results, as the formal translation of problem text into executable code is closely tied to the model's coding proficiency. This step is crucial in the proposed method.Based on this idea and Equation 4, the capability to solve mathematical problems may be strongly correlated with the model's ability to generate code for formal problem representation. Future research could explore how to further leverage LLMs' coding capabilities to enhance performance. Additionally, investigating alternative representations beyond code formatting, such as relation triples, graphs or symbolic equation, could offer insights into improving the quality of auto-formulation and achieving higher accuracy. 
limitations and future works: 
 Iterative Correction Mechanisms. Based on the experimental results conducted on the NL4Opt dataset, while the CAFA framework demonstrates competitive performance, it falls short of achieving the state-of-the-art results demonstrated by GPT-4. This discrepancy can be mainly attributed to the simplified independent assumption used to derive the equations referenced in Equation 3. As widely observed in multi-agent systems, problem-solving processes do not follow a straightforward, onepass pipeline but rather involve more complex, iterative network architectures. Such systems allow for iterative tracking, refinement, and correction of errors throughout the problem-solving process, leading to an information dependence across multiple steps. A promising direction for future research would involve the introduction of iterative correction mechanisms within the intermediate code representations of problems, potentially offering improved performance over one-pass translation approaches.Automatic Prompt Engineering and Exemplars Selection. Handcrafting instructions within the CAFA prompt remains necessary to achieve satisfactory results. This presents a limitation to the generalizability of the CAFA when applied to other types of optimization problems, such as mixed integer linear programming (MILP) or quadratic programming (QP). A key challenge is how to enable automatic prompt engineering (APE) to accommodate various optimization problems with minimal human intervention. In addition, identifying optimal examples used as few-shot demonstrations in the prompt represents another critical area of exploration. While there has been groundbreaking research in APE for arithmetic problems Yang et al. [2023] , Khattab et al. [2023] , investigations into its application in the domain of operations research (OR) remain scarce. This gap highlights an important opportunity for future research direction.Various Optimization Problems and Multi-modality Support. The CAFA prompt presented in this paper is designed specifically for linear programming problems with no more than three variables. This is too simplified and limits its applicability to many real-world scenarios. To meet the diverse demands and objectives of various applications, it is necessary to extend the capabilities of the proposed CAFA prompt. An initial extension involves adapting it to handle other types of optimization problems, such as mixed integer linear programming (MILP) and quadratic programming (QP). This also call for curating datasets of multiple types of OR problems. Furthermore, the current CAFA prompt processes only text input, whereas future research could explore a multimodal CAFA capable of supporting diverse or mixed input formats, including text, images, and tabular data. Such advancements would enable CAFA to address a broader range of needs across various use cases. 
conclusion: 
 This paper reviews several LLM4OR approaches that utilize a multi-agent framework with large language models (LLMs). An analysis of multi-step water flow pipelines using probabilistic modeling highlights the pivotal role of the initial prompt in achieving accurate solutions. It underscores that increasing the number of steps can negatively impact final performance in Linear Programming (LP) tasks. Based on this analysis, we introduce the CAFA (Code-as-Auto-Formulation) prompting method, which formalizes problem text into executable code in a single step. Ben is growing apples and pears on his orchard . He has 50 acres available on which he must grow a minimum of 5 acres of apples and a minimum of 10 acres of pears to meet demands . The profit per apple is $2 and the profit per pear is $4 . He prefers to grow more pears than apples but limitations in his workforce allow him to grow at most twice the amount of pears as apples . How many of each fruit should Ben grow in order to maximize his profit ? What is that profit ? CODE : x = m . addVar ( name =" apples " , vtype = gp .  
 
 Appendix: The code post-processing includes using regular expression to check, filter and correct the generated code from the LLM, simplfied inequalities in the code, and complement to piece of for execution. The following code snippet is the regex function. The final answer can be run by the following code ans = execute_code ( complement_code ( simplify_code ( clean_code ( code_str ) ) ) )37th Conference on Neural Information Processing Systems (NeurIPS 2023) Workshop on MATH-AI. 



Reviews: review: title: title: This paper introduces CAFA (Coding as Auto-Formulation), a simplified approach for using large language models (LLMs) to solve linear programming (LP) problems.
main_review: main_review: The key contributions are:

A theoretical analysis showing that multi-step pipelines do not necessarily improve performance over single-step approaches for LP tasks.
A streamlined prompting method that guides LLMs to directly generate code representing the LP problem formulation in one step.
Experimental results demonstrating CAFA's effectiveness across different LLM sizes, including open-source models.

Pros:

The theoretical analysis provides valuable insights into the limitations of multi-step approaches.
CAFA achieves competitive performance with a much simpler prompting strategy compared to prior work.
The method generalizes well to smaller open-source models, expanding potential applications.
The approach of using code generation as an intermediate representation is novel and promising.

Cons:

The theoretical analysis, while insightful, makes some simplifying assumptions that may not fully capture real-world scenarios.
Performance on GPT-4 is lower than the state-of-the-art OptiMUS method, though with less complexity.
Limited exploration of alternative intermediate representations beyond code.
The paper could benefit from more in-depth error analysis and discussion of limitations.

The paper is clearly written and well-structured. The motivation and approach are described logically, and the experimental results are presented clearly. The work makes a meaningful contribution to the growing field of using LLMs for operations research tasks.
The CAFA method's simplicity and generalizability are particularly noteworthy. By reducing the problem to a single code generation step, it avoids error accumulation issues inherent in multi-step approaches. The strong performance on smaller models like DeepSeek-Coder is especially promising for practical applications.

However, there are some limitations to consider. The theoretical analysis, while providing useful insights, relies on some simplifying assumptions. A more nuanced discussion of when these assumptions may break down would strengthen the paper. Additionally, while CAFA performs well, it does not surpass state-of-the-art performance on GPT-4. A more detailed comparison and discussion of trade-offs with methods like OptiMUS would be valuable.

The paper opens up interesting directions for future work, particularly in exploring alternative intermediate representations and further leveraging LLMs' coding capabilities for mathematical reasoning tasks.

Overall, this is a solid contribution that introduces a simple yet effective approach for LP problem-solving with LLMs. The method's generalizability and the insights provided by the theoretical analysis make it a valuable addition to the literature.
title: title: Review of paper 37 - CAFA: Coding as Auto-Formulation Can Boost Large Language Models in Solving Linear Programming Problem
main_review: main_review: **Summary of contributions:** 

This paper brings in Coding as Auto-Formulation (CAFA) with the objective of enhancing LLMs’ mathematical cognitive capability with more streamlined prompts. The study focusses on the fact that instead of complex multi-step pipelines, CAFA allows LLMs to formalize problem text into lines of code through a single concise prompt.

**Relevance and Clarity:** 

Relevant to the guiding theme of the proposed workshop as the authors explore to add new capabilities to the LLMs used for Operations Research. 

**Originality:**

 The authors come up with a streamlined methodology to transform error prone multi-step strategies to a single step framework to tackle Linear Programming problems and report performances which are comparable or even better than that of SotA techniques like Chain-of-Expert and OptiMUS.

**Strengths** 

1. *Research Questions:* The research questions are well framed and should succeed to generate interest among the audience. Particularly, the second research question “How can less-capable LLMs be leveraged to reason and solve LP problems with reduced prompt engineering requirements?” appears appealing as many open source LLMs have actually opened up exciting possibilities for solving Linear Programming problems in Operations Research. 


2. *Problem mitigation:* Problem formulation and mitigation are well explained through diagrams and equations. Instead of using a two-stage approach, the idea to enable the LLMs to generate code in one step can go a long way in improving performance of LLMs in Operations Research. 

 **Weakness** 

1. The accuracies reported by the authors are on NL4Opt dataset. The authors should also test their method on multiple diverse datasets to prove its generalizability. 

2. Sentence construction and grammatical correctness have avenues for improvement. This is important as it will help to convey precise meaning and engage the readers, leaving a positive impression.

**Significance** 

The authors report significant improvement in accuracy for the smaller LLMs through CAFA and hence this research can play a significant role in context with limited resources for Operations Research like using open source LLMs.
title: title: A Simplified Approach for LP Problem-Solving with LLMs
main_review: main_review: ## Summary

This study introduces CAFA (Coding as Auto-Formulation), a streamlined approach for solving Linear Programming (LP) problems using Large Language Models (LLMs). CAFA uses a single prompt to guide LLMs in formalizing problem text into executable code, followed by code post-processing and execution to obtain the solution.

## Pros

1. CAFA simplifies the LP problem-solving process by reducing it to a single-step formalization, achieving competitive or superior performance compared to more complex multi-agent approaches across various LLMs, including smaller open-source models.

## Cons

1. While CAFA demonstrates improvements across multiple models, it still falls short of the best-performing multi-agent method (OptiMUS) when using GPT-4.
2. The paper primarily focuses on linear programming problems, leaving the applicability and effectiveness for more complex optimization problem types (such as non-linear programming, integer programming, etc.) unexplored.
3. The study lacks comparison with the latest software agents, such as SWE-Agent and Data Interpreter.