Envision a coffee corporation attempting to enhance its supply chain. This corporation acquires beans from three different vendors, roasts them at two sites into either dark or light coffee, and subsequently delivers the roasted coffee to three retail outlets. The suppliers possess varying fixed capacities, and both roasting and shipping expenses differ across locations.
The corporation aims to reduce expenditures while accommodating a 23 percent rise in demand.
Wouldn’t it be simpler for the corporation to merely request ChatGPT to devise an optimal strategy? Indeed, despite their remarkable capabilities, large language models (LLMs) frequently struggle when assigned the task of directly addressing such intricate planning issues independently.
Instead of attempting to modify the model to enhance the planning abilities of an LLM, MIT researchers opted for an alternative strategy. They established a framework that instructs an LLM to decompose the issue as a human would, and then automatically resolve it using a powerful software application.
A user needs only to articulate the problem in natural language — no specific examples are needed to train or prompt the LLM. The model translates a user’s textual prompt into a format that can be deciphered by an optimization solver designed to adeptly tackle extremely challenging planning problems.
Throughout the formulation phase, the LLM verifies its progress at various intermediate stages to ensure the plan is accurately articulated to the solver. If it detects an error, instead of conceding defeat, the LLM attempts to correct the faulty aspect of the formulation.
When the researchers evaluated their framework on nine intricate challenges, such as reducing the distance that warehouse robots must traverse to complete tasks, it attained an 85 percent success rate, while the best baseline only reached a 39 percent success rate.
The adaptable framework could be utilized for a variety of multistep planning tasks, including scheduling airline crews or overseeing machine usage in a factory.
“Our research presents a framework that essentially serves as an intelligent assistant for planning issues. It can determine the optimal plan that fulfills all your requirements, even if the parameters are complex or unusual,” states Yilun Hao, a graduate student in the MIT Laboratory for Information and Decision Systems (LIDS) and lead author of a paper on this research.
She collaborates on the paper with Yang Zhang, a research scientist at the MIT-IBM Watson AI Lab; and senior author Chuchu Fan, an associate professor of aeronautics and astronautics and LIDS principal investigator. The research will be presented at the International Conference on Learning Representations.
Optimization 101
The Fan group develops algorithms that automatically resolve what are termed combinatorial optimization dilemmas. These extensive problems encompass numerous interconnected decision variables, each with various options that swiftly accumulate to billions of potential choices.
Humans approach these problems by condensing them to a limited number of options and then discerning which one yields the best overall plan. The researchers’ algorithmic solvers employ the same principles to tackle optimization problems that are far too intricate for any individual to resolve.
However, the solvers they create tend to involve steep learning curves and are generally utilized solely by specialists.
“We believed that LLMs could enable nonexperts to leverage these solving algorithms. In our lab, we take a domain expert’s problem and formalize it into a format our solver can address. Could we train an LLM to accomplish the same task?” Fan explains.
Using the framework the researchers designed, termed LLM-Based Formalized Programming (LLMFP), an individual provides a natural language outline of the issue, contextual information about the task, and a query that articulates their objective.
Then LLMFP prompts an LLM to consider the problem and identify the decision variables and essential constraints that will shape the optimal solution.
LLMFP instructs the LLM to specify the requirements of each variable before translating the information into a mathematical representation of an optimization issue. It generates code that encapsulates the problem and invokes the accompanying optimization solver, which arrives at an ideal resolution.
“It parallels how we educate undergraduates about optimization challenges at MIT. We don’t instruct them in just one field. We educate them on the methodology,” Fan adds.
As long as the inputs to the solver are accurate, it will yield the correct outcome. Any errors in the solution arise from inaccuracies in the formulation process.
To ensure it has devised a viable plan, LLMFP evaluates the solution and adjusts any erroneous steps in the problem formulation. Once the plan passes this self-evaluation, the solution is communicated to the user in natural language.
Perfecting the plan
This self-evaluation module also allows the LLM to incorporate any implicit constraints it may have overlooked initially, Hao indicates.
For example, if the framework is optimizing a supply chain to minimize costs for a coffee shop, a human recognizes that the coffee shop cannot ship a negative number of roasted beans, whereas an LLM might not comprehend this.
The self-assessment phase would identify that error and prompt the model to rectify it.
“Furthermore, an LLM can adjust to the preferences of the user. If the model recognizes that a particular user does not prefer to alter the timing or budget of their travel plans, it can propose alterations that align with the user’s requirements,” Fan states.
In a series of evaluations, their framework achieved an average success rate between 83 and 87 percent across nine varied planning problems utilizing several LLMs. Although some baseline models performed better on specific problems, LLMFP attained an overall success rate roughly double that of the baseline techniques.
Unlike these other methodologies, LLMFP does not require domain-specific examples for training. It can identify the optimal solution to a planning issue immediately upon deployment.
Additionally, the user can modify LLMFP for different optimization solvers by adjusting the prompts provided to the LLM.
“With LLMs, we have a chance to create an interface that empowers individuals to utilize tools from other fields to resolve issues in innovative ways they may not have previously considered,” Fan concludes.
In the future, the researchers aspire to enable LLMFP to accept images as input to augment the descriptions of a planning problem. This would assist the framework in addressing tasks that are particularly challenging to fully articulate in natural language.
This research was funded, in part, by the Office of Naval Research and the MIT-IBM Watson AI Lab.