Introduction to Optimization Problems
Imagine a coffee company trying to optimize its supply chain. The company sources beans from three suppliers, roasts them at two facilities into either dark or light coffee, and then ships the roasted coffee to three retail locations. The suppliers have different fixed capacity, and roasting costs and shipping costs vary from place to place. The company seeks to minimize costs while meeting a 23 percent increase in demand.
The Challenge with Large Language Models
Wouldn’t it be easier for the company to just ask ChatGPT to come up with an optimal plan? In fact, for all their incredible capabilities, large language models (LLMs) often perform poorly when tasked with directly solving such complicated planning problems on their own. Rather than trying to change the model to make an LLM a better planner, MIT researchers took a different approach. They introduced a framework that guides an LLM to break down the problem like a human would, and then automatically solve it using a powerful software tool.
How the Framework Works
A user only needs to describe the problem in natural language — no task-specific examples are needed to train or prompt the LLM. The model encodes a user’s text prompt into a format that can be unraveled by an optimization solver designed to efficiently crack extremely tough planning challenges. During the formulation process, the LLM checks its work at multiple intermediate steps to make sure the plan is described correctly to the solver. If it spots an error, rather than giving up, the LLM tries to fix the broken part of the formulation.
Applications and Success Rate
When the researchers tested their framework on nine complex challenges, such as minimizing the distance warehouse robots must travel to complete tasks, it achieved an 85 percent success rate, whereas the best baseline only achieved a 39 percent success rate. The versatile framework could be applied to a range of multistep planning tasks, such as scheduling airline crews or managing machine time in a factory.
Expert Opinion
“Our research introduces a framework that essentially acts as a smart assistant for planning problems. It can figure out the best plan that meets all the needs you have, even if the rules are complicated or unusual,” says Yilun Hao, a graduate student in the MIT Laboratory for Information and Decision Systems (LIDS) and lead author of a paper on this research.
Optimization 101
The Fan group develops algorithms that automatically solve what are known as combinatorial optimization problems. These vast problems have many interrelated decision variables, each with multiple options that rapidly add up to billions of potential choices. Humans solve such problems by narrowing them down to a few options and then determining which one leads to the best overall plan. The researchers’ algorithmic solvers apply the same principles to optimization problems that are far too complex for a human to crack.
LLM-Based Formalized Programming (LLMFP)
Using the framework the researchers developed, called LLM-Based Formalized Programming (LLMFP), a person provides a natural language description of the problem, background information on the task, and a query that describes their goal. Then LLMFP prompts an LLM to reason about the problem and determine the decision variables and key constraints that will shape the optimal solution.
Perfecting the Plan
This self-assessment module also allows the LLM to add any implicit constraints it missed the first time around. For instance, if the framework is optimizing a supply chain to minimize costs for a coffeeshop, a human knows the coffeeshop can’t ship a negative amount of roasted beans, but an LLM might not realize that. The self-assessment step would flag that error and prompt the model to fix it.
Conclusion
The researchers’ framework achieved an average success rate between 83 and 87 percent across nine diverse planning problems using several LLMs. While some baseline models were better at certain problems, LLMFP achieved an overall success rate about twice as high as the baseline techniques. Unlike these other approaches, LLMFP does not require domain-specific examples for training. It can find the optimal solution to a planning problem right out of the box.
FAQs
- Q: What is the main challenge with large language models when solving optimization problems?
A: Large language models often perform poorly when tasked with directly solving complicated planning problems on their own. - Q: How does the LLM-Based Formalized Programming (LLMFP) framework work?
A: LLMFP prompts an LLM to reason about the problem and determine the decision variables and key constraints that will shape the optimal solution, and then uses an optimization solver to find the ideal solution. - Q: What is the success rate of the LLMFP framework?
A: The framework achieved an average success rate between 83 and 87 percent across nine diverse planning problems using several LLMs. - Q: Can the LLMFP framework be applied to different optimization solvers?
A: Yes, the user can adapt LLMFP for different optimization solvers by adjusting the prompts fed to the LLM.
