Solving General Natural-Language-Description Optimization Problems with Large Language Models (2024)

Abstract: Optimization problems seek to find the best solution to an objective under a set of constraints, and have been widely investigated in real-world applications. Modeling and solving optimization problems in a specific domain typically require a combination of domain knowledge, mathematical skills, and programming ability, making it difficult for general users and even domain professionals. In this paper, we propose a novel framework called OptLLM that augments LLMs with external solvers. Specifically, OptLLM accepts user queries in natural language, convert them into mathematical formulations and programming codes, and calls the solvers to calculate the results for decision-making. In addition, OptLLM supports multi-round dialogues to gradually refine the modeling and solving of optimization problems. To illustrate the effectiveness of OptLLM, we provide tutorials on three typical optimization applications and conduct experiments on both prompt-based GPT models and a fine-tuned Qwen model using a large-scale self-developed optimization dataset. Experimental results show that OptLLM works with various LLMs, and the fine-tuned model achieves an accuracy boost compared to the prompt-based models. Some features of OptLLM framework have been available for trial since June 2023 (https://opt.alibabacloud.com/chat or https://opt.aliyun.com/chat).

## introduction optimization problems have been widely investigated in real-world domains including financial investment @xcite , supply chain management @xcite , logistics transportation @xcite and competitive strategy @xcite . such ubiquitous optimization problems raise critical demands for efficient modeling and solving methods. currently, modeling and solving optimization problems in a specific domain usually involves three steps @xcite . first, based on domain knowledge, experts summarize the application scenarios into problem descriptions using natural language or mathematical formulas, with clear indication of variables, objectives, constraints, and parameters. second, experts extract and encode critical information from the problem descriptions with modeling languages such as python, r or ampl. finally, the optimization process is carried out by experts or solvers to obtain the final decision-making results. meanwhile, the entire process calls for a combination of domain knowledge, mathematical skills, and programming ability, which is unfriendly to beginners or even professionals in that domain. recently, large language models (llms) have demonstrated strong capabilities in natural language understanding and generation @xcite . however, despite llms' strong performance across a range of nlp tasks (e.g., content generation and q&a dialogue) @xcite , their ability in arithmetic and logical reasoning may be insufficient and unfaithful @xcite . on the other hand, data privacy remains one concern for online services like @xcite . that is, inclusion of domain-specific information in prompts may cause data breach at the llm service provider side or during transmission in public networks, even under the service level agreements for privacy @xcite . hence, deployment of openresourced llms (e.g., llama @xcite , palm @xcite , and qwen foot_0 ) is preferred for privacy-sensitive applications. in light of these above, we propose optllm, a framework unifying either open-sourced llms or online llm services, and external solvers for automated modeling and solving of optimization problems. specifically, optllm consists of three modules. first, the interaction refinement module interacts with users to complete problem descriptions and ensures the input is a valid optimization problem. second, the converter module converts problem descriptions to mathematical formulations and programming codes, and ensures the codes are correct. last, the responser module sends the code to an external optimization solver, receives the results and interprets them. optllm allows users to iteratively refine any stage outputs through chatting or direct editing, until satisfactory results are obtained. in this way, optllm aims to make it significantly easier for users to model and solve optimization problems. ## related work llms, or large language models, are predominantly transformers @xcite trained on extensive text corpus from various sources (e.g., webs and books @xcite ). they are trained to predict the next token in a given context, and could generate coherent responses after finetuning and alignment (openai, 2023). below we briefly cover applications and techniques related to automated optimization problem modeling and solving using llms. ## proposed framework: optllm we propose optllm that unifies llms and external solvers for automated modeling and solving of optimization problems. by designing optllm to interact with domain users via natural language, we hope to reduce the need for specialized knowledge on optimization or coding, and improve the experience for end-users. optllm primarily consists of three modules: interaction refinement module, converter module, and responser module. ## applications our framework can solve generic optimization problems based on their natural language description. in this part, we introduce three basic applications, including single-round qa with complete description, multi-round conversations with missing information detection, and optimization problem solving with external data. ## experiments 6.1 datasets we focus primarily on linear programming (lp) and mixed integer linear programming (milp) problems, which may be of strong interests in industrial applications. to the best of our knowledge, there is currently no publicly available datasets on general optimization problems except the data from nl4opt competition foot_2 @xcite . few additional problems can be crawled from websites, but they may still not be sufficient for fine-tuning the llms. thus, we constructed our own fine-tuning and test datasets. we ensure that qwen model has not seen the test datasets during the pre-training phase. fine-tuning dataset. figure 5 shows the data collection process. to build a large-scale dataset, we start with seed optimization problems manually designed by experts, followed by designing prompts and calling llms to generate more problems. we then manually label the data and select prompts that perform well. the resultant prompts are used to generate more data, which are again manually labelled. the labeled data can be used as seeds for the next round of data generation. this process is repeated several times. finally, we collected a high-quality optimization training dataset with total 15k instances in english and chinese. test dataset. we select 100 optimization problems with natural language description in english, called en100, part of which are from the dev dataset of nl4opt competition. besides, we also prepare another 100 chinese optimization problems, called cn100. all test data are manually checked to ensure correctness. ## path to deployment the proposed optllm framework can be deployed on the cloud. we take alibaba cloud foot_3 as an example to illustrate the deployment of optllm. as shown in figure 7 , the infrastructure includes: i) the oss provides data storage for user data that may be used in application 3; ii) redis is used for recording online conversation context; iii) odps is used for logging historical logs. dashscope foot_4 is an inference platform that supports both existing llm apis (e.g., gpt-3.5 and gpt-4) or self-built llms (e.g., qwn-sft and llama2-sft). external tools include solver, such as mindopt, and chimp, a testing platform for the entire framework. once deployed on the cloud, the proposed optllm framework has the potential to support applications in various domains, such as educational services, financial investment and supply chain management. in june 2023, we have deployed the first version on alibaba cloud, which includes some of the features introduced in this paper, with more features currently under development. ## limitation although our system is capable of handling singleround optimization problems, as well as multiround addition, deletion, and modification operations for some optimization problems, our model's effectiveness will be somewhat affected when dealing with incomplete issues that require additional knowledge for certain parts. this is because this extra knowledge may not be possessed by our large model due to certain reasons, such as our model's knowledge base being up-to-date only until 2023, meaning it wouldn't be aware of knowledge from 2024. there are two ways to address this issue: one is to update the underlying large model in real-time, but this would entail significant financial and material costs. the other option involves using methods related to retriever-augmented generation (rag). these are aspects we plan to explore in our future work. ## conclusion in this paper, we propose optllm, an effective framework that augments llms (such as qwen model and gpt-4) with external solvers for automated modeling and solving of optimization problems. specifically, optllm comprises three modules: the interaction module for completing the problem description, the converter for translating the description into code, and the responser for calling solvers and interpreting the results, respectively. by iterating the above steps through chatting with users, optllm has the potential to assist both beginners and domain professionals to achieve faithful decision-making for optimization problems. we illustrate the effectiveness of optllm with three proof-of-concept applications and experiments. in the future, we will focus on promoting the diversity of optimization problems by including more real-world cases from various domains and scenarios. we will also explore methods to enhance arithmetic and logical reasoning, as well as more open-sourced llms and evaluation methods.