Large Language Model for Combinatorial Optimization by Leveraging Policy Adaptation and Heuristics

Many techniques have been used to elicit reasoning within Large Language Models (LLMs), and several methods have been developed to solve NP-hard combinatorial problems (CPs). Certain methods relies on prompting strategies to sample solutions from the LLM, potentially finetuned on previous problems to improve the quality of the samples. If the budget allows it, multiple independent samples are obtained and the best solution is retained. Larger model correlate with higher quality solutions, but are also more costly to sample. Meanwhile, heuristics exists for many problems that generate good enough solutions for combinatorial problems very quickly. We present a method to progressively sample a solution from a finetuned model distribution via a series of heuristic solutions, each analyzed by the model to lead to the next heuristic solution. Furthermore, we show how to use the constraints of the problem to improve the samples as well as progressively build a policy from the solutions to improve the future samples. We demonstrate on various combinatorial problems (Binpack, Knapsack, Vehicle Routing Problem and Job-shop scheduling) and various models that the method improves the solutions that can be obtained by using simple heuristics, and that the method is superior to using the LLM simply as a sampling tool in terms of processing time, number of samples and solution quality. We also show further improvement obtainable by constructing a policy progressively from the previous samples and a the constraints of the problem. We show that the computed policy converges eventually to a distribution equivalent to the model with the constraints of the Combinatorial problem.