Self-Guiding Exploration for Combinatorial Problems

Authors: zangir  iklassov
yali  du
farkhad  akimov
martin  takáč
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 12:58:10

Abstract: Large Language Models (LLMs) have become pivotal in addressing reasoning tasks across diverse domains, including arithmetic, commonsense, and symbolic reasoning. They utilize prompting techniques such as Exploration-of-Thought, Decomposition, and Refinement to effectively navigate and solve intricate tasks. Despite these advancements, the application of LLMs to Combinatorial Problems (CPs), known for their NP-hardness and critical roles in logistics and resource management remains underexplored. To address this gap, we introduce a novel prompting strategy: Self-Guiding Exploration (SGE), designed to enhance the performance of solving CPs. SGE operates autonomously, generating multiple thought trajectories for each CP task. It then breaks these trajectories down into actionable subtasks, executes them sequentially, and refines the results to ensure optimal outcomes. We present our research as the first to apply LLMs to a broad range of CPs and demonstrate that SGE outperforms existing prompting strategies by over 27.84% in CP optimization performance. Additionally, SGE achieves a 2.46% higher accuracy over the best existing results in other reasoning tasks (arithmetic, commonsense, and symbolic).

Main paper: 
 introduction: 
 Large Language Models (LLMs) have emerged as powerful tools capable of executing reasoning tasks across various domains, including arithmetic, commonsense, and symbolic reasoning [4, 33, 5, 27] . These models may leverage prompting techniques such as Exploration-of-Thought [39, 13, 42] , Decomposition [49, 12] , and Refinement [19] to break down and solve various tasks in a step-bystep manner. Recent research has been directed towards extending these techniques to tackle more sophisticated optimization challenges [41] . Combinatorial problems (CPs) may represent a category of these complex optimization tasks, associated with intricate computational challenges.Combinatorial Problems are characterized by their NP-hardness and inherent complexity, which result in an exponential growth in the number of potential solutions. This complexity presents substantial challenges in the research [26, 25, 11, 10] . CPs are especially crucial in sectors that require efficient logistics, planning, and scheduling. Currently, the dominant approach in these industries involves metaheuristic methods. These methods combine various simple but fast heuristics to effectively tackle CPs within specific constraints. Nonetheless, the effectiveness of these heuristics can vary significantly depending on the CP task and its associated constraints, necessitating a customized selection of heuristics to achieve optimal performance.In the meantime, research on exploring LLMs to solve CPs reveals substantial gaps. While recent advancements indicate the effectiveness of LLMs in various reasoning tasks [38, 47, 32, 49] , their application to CPs has been minimal. The literature indicates that existing generative models can address smaller instances of the Traveling Salesman Problem (TSP) [16, 23, 41] . However, as problem sizes increase, existing prompting strategies begin to yield inadequate responses, underscoring the need for more sophisticated prompting methods. Moreover, there is a notable scarcity of research addressing other complex CPs, particularly the Vehicle Routing and Job Scheduling Problems, which pose significant challenges in logistics, planning industries, and operations research.In this work, we introduce a novel prompting strategy: self-guiding exploration (SGE), designed to enhance the problem-solving process for CPs. This algorithm works as a combination of explorationof-thought, decomposition, and refinement prompting methods. The SGE approach autonomously generates multiple thought trajectories for a given CP, each trajectory representing a specific heuristic to tackle the given task. Each trajectory is then decomposed into subtasks, which are executed one by one, and their outputs are refined and combined into a final solution. Unlike the task-specific prompts utilized in other methods, SGE employs general-purpose prompts, allowing for the adaptive use of specific heuristic solutions tailored to various CPs, such as the Hungarian heuristic for the assignment problem and the Nearest Neighbor heuristic for the vehicle routing problem. Essentially, SGE acts as a versatile metaheuristic capable of identifying, combining, and refining task-specific heuristics for individual CP tasks.Our work makes following contributions. Firstly, we present a novel investigation into the application of large language models for solving combinatorial problems. Secondly, we introduce a new prompting strategy, SGE, that autonomosly generates thought trajectories, splits them into subtasks and refines the answers. Thirdly, we demonstrate that SGE outperforms existing prompting strategies such as Chain-of-Thought, Decomposition, and Self-Refinement, improving CP optimization performance by 27.84%. Lastly, we validate the applicability of SGE across other reasoning tasks, including arithmetic, commonsense, and symbolic tasks, where our method achieves a 2.46% higher accuracy than the best existing results.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: The method, problem description, and key results are outlined in the abstract and introduction sections.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
related work: 
 CP via classical approach. In classical research, combinatorial problems are predominantly tackled using heuristic and metaheuristic methods specifically crafted for particular tasks. Notable examples include the Ant-Colony Optimization and Tabu Search methods for addressing the Vehicle Routing Problem [28, 8, 15] , the Shortest Processing Time and Most Work Remaining Heuristics for Job Scheduling Problems [30] , and the Hungarian Algorithm for the Assignment Problem [1] . These approaches are favored in industrial settings due to their simplicity and speed. However, they need to be individually tailored to each task and its constraints' setting. In contrast, exact solvers such as Google-OR-Tools [9] offer general and precise solutions, but their applicability is often limited to smaller-scale problems due to the inherent NP-hardness of combinatorial problems.CP via learning-based approach. In AI literature, Reinforcement Learning (RL) has been a prominent approach for tackling combinatorial problems since the 1990s [21, 20, 45, 7, 2] . The integration of deep learning, particularly through innovations like Pointer Networks, has significantly enhanced RL's capability to handle more complex combinatorial tasks [35, 3] . Further advancements involve the use of Transformer networks [6, 34, 14] , with notable applications in solving the Vehicle Routing Problem [25, 11] . Despite these advances, RL-based methods often still do not exceed the performance of traditional heuristics, especially when scalability and accurate state representation are required [36, 22, 44, 31] . CP with LLMs. Recent studies have leveraged large language models (LLMs), such as GPT-3.5 and GPT-4, to tackle combinatorial problems like the Traveling Salesman Problem using iterative prompting, where solutions are refined incrementally [23, 41] . Other works employ LLMs to autonomously generate executable code as novel heuristics for problems like the knapsack and traveling salesman [29, 17, 43, 18] . This promising approach enhances task-specific heuristics, potentially improving performance on specialized combinatorial tasks. In contrast, our focus is on leveraging LLMs to directly solve combinatorial problems in a generalizable manner, enabling a versatile approach applicable across a wide range of complex tasks.Prompting strategies. The expressive capabilities of direct prompting in Large Language Models are theoretically limited to the complexity class TC 0 [24] . To effectively address combinatorial problems with LLMs, sophisticated prompting strategies are required. One basic approach is the Chain-of-Thought (CoT) prompting, introduced in [40] , which encourages LLMs to articulate intermediate "thoughts" that inform the generation of the final output. This technique has given rise to advanced variations, including Self-consistency with CoT (CoT-SC), Tree-of-Thoughts (ToT), and Graph-of-Thought methods [37, 42, 46] . Additionally, decomposition prompting strategies can be employed [48, 12] , since they simplify complex tasks into smaller, manageable subtasks via symbolic programs or structured algorithms, thus improving the performance of LLMs. In our experiments, we found these techniques to be insufficient, leading us to propose the Self-Guiding Exploration method as a more effective solution for tackling combinatorial problem tasks.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: We examine the trade-off between higher costs and enhanced performance, as well as the dependency of the method's effectiveness on the choice of LLM model.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
preliminaries: 
 We provide an overview of combinatorial problems, highlighting their inherent complexity with the classic example of the Traveling Salesman Problem (TSP) and an example of a combinatorial problem formulation in a prompt for use by a Large Language Model (LLM).Combinatorial problems. Combinatorial problems involve decision-making processes where the goal is to assign binary decision variables x ∈ 0, 1 in order to optimize a cost function g(x 1 , ..., x n ), subject to task-specific constraints. A classic example of such a problem is the TSP. In the TSP, given a list of n cities and the distances d ij between cities i, j, the objective is to determine the shortest possible route that visits each city exactly once and returns to the starting city. x ij is used as the action variable, indicating whether the route progresses from city i to city j. The cost function to minimize in TSP is g(x) = n i=1 n j=1 d ij x ij , under the condition that all cities visited exactly once n i=1 x ij = 1 and n j=1 x ij = 1 for all i, j. Combinatorial problems are generally categorized as NP-hard due to their inherent computational complexity. For instance, a TSP with n cities presents (n -1)! possible routes, rendering the evaluation of all potential solutions impractical and exceedingly time-consuming as n increases.Prompting combinatorial problems in LLMs. To use LLM for solving CP tasks, we define f as the interface function of a generative LLM model, which accepts high-dimensional discrete input tokens and generates outputs within the same token space (f : W → W ). For each combinatorial problem task, the input Q to the LLM can be explicitly defined in a textual format. This description delineates the specific goal alongside a list of variables tailored to the task at hand. For instance, the objective of the Traveling Salesman Problem (TSP) can be textually articulated as "Find a route that minimizes the total travel distance, visits each city exactly once, and starts and ends in the same city." Subsequently, the variables, such as the distances between cities d ij , are provided in a format such as "The distance between city i and city j is [number]", laying out all necessary parameters for the model to process and generate solutions. The model will then process this structured input Q to produce the corresponding solution answer A, where both Q and A are within token space W ; formally, A = f (Q). Given the inherent complexity of combinatorial problems, direct zero-shot prompting f (Q) is insufficient. Consequently, we propose a self-guiding exploration algorithm that employs metaheuristic-like strategies to effectively solve CP tasks.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes]Justification: The code for the experiments, along with instructions, is provided in open access.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
method: 
 In this section, we introduce Self-Guiding Exploration (SGE) method and provide a detailed explanation of its algorithm designed to tackle combinatorial problems. The method (Fig 1 ), inspired by metaheuristic approaches, synthesizes multiple heuristic methods. It generates various thought trajectories, with each trajectory representing a specific heuristic approach. These trajectories are then integrated to form the final solution. To overcome the challenges of executing complex heuristics through LLMs in one step, our algorithm utilizes a decomposition strategy. This approach breaks down each trajectory into smaller, more manageable subtasks, enabling the solution to progress through sequential, simpler steps. This general-purpose algorithm is tailored to adapt to a wide range of combinatorial problems without the constraints of task-specific exemplars for few-shot solution generation. (5) Integration of all trajectories into a consolidated final solution A. Distinct from traditional exploration/decomposition techniques, SGE(Q) functions entirely autonomously, eliminating the reliance on task-specific queries or manually created thought exemplars. This independence makes it universally applicable to all CP tasks without necessitating modifications.Algorithm 1 Self-Guiding Exploration algorithm -SGE(•) Require: query Q, model f , meta-prompts Z, maximum recursion depth D 1: Q N = f (Q, Z explore ) ▷ Explore method trajectories 2: for iteration n ∈ 1, 2, . . . , N do 3: Q n K = f (Q, Q n , Z decomp ) ▷ Decompose trajectory subtasks 4: for iteration k ∈ 1, 2, . . . , K do 5: if f (Q n k , Z check ) then ▷ Check if subtask is simple 6: T n k = f (Q, T n k-1 , Q n k )▷ Execute subtask and get thought T n k = SGE(T n k-1 ||Q n k , f, Z) ▷ Recursive call of subtask 9:end if 10:Q n k f eedback = f (Q, Q n k , T n k , Z f eedback ) ▷ Get feedback query 11:Tn k = f (Q, T n k , Q n k f eedback ) ▷ Refine thought 12:end for 13: end for14: A = f (Q, T 1 K , ..., T N K , Z integrate ) ▷ Get answerThe proposed method's algorithm is segmented into five distinct phases, as outlined in Algorithm 1. These phases include exploring thought trajectories, decomposing each trajectory into subtasks, resolving each subtask to generate thoughts, obtaining feedback and refining the thoughts, and finally integrating all thoughts to formulate the answer. Each thought here represents one completed subtask.Exploration. During the exploration stage, the model tackles the overarching problem Q by engaging with exploration meta-prompt. This prompt Z explore is structured as: "List all possible methods to solve this problem. Return them separated by new lines." This prompt stimulates the model to enumerate potential methodologies pertinent to Q. The sequence is then divided into task-specific trajectories of queries Q n each incorporating a method to address Q:Q N = f (Q, Z explore ).Decomposition. Following exploration, each trajectory query Q n is processed through the model to break down the trajectory into actionable steps. The decomposition meta-prompt Z decomp is formulated as: "List all steps to use the method. Return them separated by new lines." This leads to the generation of subtask queries that operationalize the trajectory method:Q n K = f (Q, Q n , Z decomp ).Subtask resolution. Post-decomposition, the subtask queries Q n K are each split into K individual queries and processed by the model to generate thoughts. The model initially evaluates if the task is easily solvable using the meta-prompt Z check : "Is this problem easily solvable? Return yes or no":f (Q n k , Z check ).If the response is affirmative, the model executes the subtask query Q n k to generate a new thought:T n k = f (Q, T n k-1 , Q n k ). Otherwise, the model engages a recursive instance of the self-guiding exploration algorithm on Q n k instead of the main task Q to navigate and decompose the complex subtask, producing:T n k = f (Q, T n k , Q n k f eedback ).Feedback and refinement. In this stage, the model utilizes an additional meta-prompt Z f eedback -"Give feedback to the proposed solution" -to generate feedback queriesQ n k f eedback = f (Q, Q n k , T n k , Z f eedback ). This guides the model in refining the initial responses through reevaluation and enhancement of the thoughts:T n k = f (Q, T n k , Q n k f eedback ).Integration. Upon completion of all trajectories and their associated subtasks, the model employs a final meta-prompt Z integrate -"Integrate all previous findings and provide the final answer" -to amalgamate the last thoughts into a definitive solution answer:A = f (Q, T 1 K , ...T N K , Z integrate ).SGE draws inspiration from metaheuristic methods used to solve combinatorial problem tasks. Yet, due to its general-purpose nature and meta-prompts, it is also suitable for other tasks, beyond CPs. Essentially, it integrates elements of exploration-of-thought, decomposition, and refinement prompting strategies, but it does so without relying on task-specific prompts or solution exemplars.For additional information on these prompting strategies, see Section A.1 
experiments: 
 This section details the experimental setup and presents the results of our proposed method applied to combinatorial problem tasks, as well as its performance on other reasoning tasks commonly explored in LLM research. Baselines. We utilized four baseline prompting methods: Input-Output (IO) Direct Prompting, Chain-of-Thought Prompting, Self-Refine (Refine) Prompting, and Decomposition Prompting. The Input-Output (IO) approach involves a single prompt where the model is asked to provide a solution directly, without complex prompting. In this approach, we generate N sample candidates by repeatedly prompting the model with the same query Q, N times. The responses are then aggregated through majority voting to identify the most common solution among the N outputs. We employ the Self-Refine (Refine) method [19] , which includes a feedback-refinement procedure that aligns closely with phase four of SGE. Additionally, we use the zero-shot Chain-of-Thought method [13] , which is the basic technique among Exploration-of-Thought methods. Lastly, we implemented the Decomposition method as described in [49] . In our experiments, these baseline methods were tested across a range of five LLM models including GPT-4, GPT-3.5 by OpenAI, Gemini-1.5 by Google, and the Llama-2 series from Meta, which includes models with 70 billion and 7 billion parameters. We did not include prompting methods previously used in [16, 23, 41] , as their prompting strategies showed inferior results compared to the zero-shot Chain-of-Thought approach when tested with our data.Metrics. In our study, each method's performance is evaluated relative to IO (Input-Output) prompting. To quantify the improvement, we first measure the solution cost g io for each combinatorial problem task using IO prompting (e.g., for the TSP,g io = n i=1 n j=1 d ij x ij ).We then calculate the cost g method using alternative methods. The percentage improvement is computed as 100 × gio-g method gio. For problems of smaller sizes, we are able to obtain optimal solutions using the Google-OR-Tools solver through a brute force approach. In such instances, we measure the cost of the optimal solution g opt and determine the optimality gap as 100 × g method -gopt gopt .To evaluate the general performance of SGE on combinatorial problems, we conducted experiments comparing performance improvement to IO of SGE and CoT, Decomposition, and Refinement baselines using GPT-4 and Gemini-1.5 LLM models. Table 1 gives the results on six combinatorial problem tasks. The results analysis shows that the SGE method consistently outperforms CoT, Refine, and Decomposition methods across all tasks. Notably, the magnitude of improvement escalates with the increasing complexity of the problems, from polynomial to exponential. The margin with the second-best method, Decomposition, ranges from 7.53% for the Assignment Problem to 37.13% for the JSP. This trend suggests that the IO method may struggle with the computational demands of NP-hard problems, where more sophisticated strategies like SGE provide significant advantages. For a comprehensive view of all experimental results, see Section A.4.To qualitatively evaluate the performance of the Exploration, Decomposition, and Refinement phases of SGE method, we assessed the LLM outputs for each phase across five random instances of each combinatorial problem task. Figure 2 illustrates an example of how our method addresses the TSP, showcasing outputs during each of the three phases of SGE. In the Exploration phase, the first box of Figure 2 displays how LLM f generates a list of potential algorithms suitable for solving • Refinement Output:-Choose two edges -Remove these edges and reconnect the two paths that were created in such a way that the new connections do not cross over each other.-Check if the new tour has a shorter distance than the previous tour. If it does, keep the change. Otherwise, revert to the previous tour. -Repeat this process until no improvements can be made. the TSP, such as heuristic approaches like Nearest Neighbor, metaheuristic techniques like Ant Colony, and Mixed Integer Linear Programming (MILP) method. This phase adapts to different combinatorial problems by suggesting tailored algorithms, like the Hungarian algorithm for the Assignment problem, Greedy algorithms for the Knapsack problem, and Clustering methods for the Vehicle Routing Problem (VRP). Each list of algorithms forms the foundation for generating diverse candidate solutions tailored to each specific problem. The Decomposition phase, depicted in the second box of Figure 2 , breaks down each identified algorithm into specific subtasks. This example shows the decomposition of the Nearest Neighbor algorithm for the TSP, where the initial subtasks are simple enough for direct processing by model f . However, more complex tasks, such as loops, undergo further decomposition using SGE in a recursive manner, with computational or programming tasks being handled using Python within models like GPT-4 and Gemini-1.5 equipped with a Code Interpreter. Finally, the Refinement phase, illustrated in the third box of Figure 2 , focuses on enhancing the candidate solutions developed in the previous stage. This example pertains to refining a solution derived from the Nearest Neighbor algorithm for the TSP by implementing the 2-opt algorithm. Renowned for its effectiveness in TSP and VRP contexts, the 2-opt algorithm optimizes the initial solution to find locally optimal solutions within a specific neighborhood, thus improving the overall quality of the candidate solutions. This example shows that SGE method adapts its approach to suit different combinatorial problems, finding a special set of heuristics for each task.Effect of problem size on SGE performance. To evaluate the effect of problem size on SGE performance, we conducted experiments on all six tasks with input sizes of 5, 8, 12, 15, and 20 nodes using the GPT-4 model. Figure 3 gives the results of these experiments. The results analysis shows that generally, an increase in problem complexity, as determined by the size of the problem input, negatively influences performance improvement; larger problem sizes result in diminished performance improvement of the SGE method compared to IO. Specifically, tasks with 20 input nodes consistently exhibit lower performance improvements relative to the IO method than tasks with 5 input nodes. However, when comparing less disparate sizes, such as 8 and 12 nodes, the differential impact on performance is less pronounced and can occasionally be positive.Table 2 : Optimality gap of prompting methods using LLaMA-2-70B. The results are represented as performance percentage difference compared to optimal solutions (the smaller it is, the better). Gap between SGE performance and the global optimum. To evaluate the gap between SGE solutions and global optimum solutions, we conducted experiments on small problem sizes involving 5, 8, and 12 nodes, utilizing the brute force method via Google-OR-Tools to determine the global optimum. Figure 2 provides the results of these experiments in terms of the percentage gap between the performance of SGE and optimal solutions. The results analysis shows that generally, the SGE method exhibits a smaller optimality gap across all tasks when compared to baseline methods. This advantage is particularly pronounced for more complex problems such as Bin Packing, TSP, VRP, and JSP. For instance, SGE achieves a 12.16% smaller optimality gap on the Assignment task than the next best Decomposition method and a 34.85% smaller gap on the JSP.Effect of LLM selection on SGE performance. To evaluate the impact of model selection on SGE performance, we conducted experiments comparing different models, including GPT-4, Gemini-1.5, GPT-3.5, Llama-2-70b, and Llama-2-7b models. Figure 4 provides the results of these experiments.The results analysis shows that GPT-4 and Gemini-1.5 demonstrate significantly better performance compared to other models across all tasks. A notable feature of both models is the integration of a Code Interpreter (CI) tool, which appears crucial for combinatorial problem tasks as it enables the models to execute generated code and evaluate solution performance directly. In contrast, models lacking a CI tool, such as GPT-3.5, Llama-2-70b, and Llama-2-7b, exhibit poorer outcomes, with GPT-3.5 slightly outperforming the Llama models. The comparison between Llama models indicates that the size of the model with 70 billion versus 7 billion parameters does not significantly influence performance. This suggests that model size alone does not guarantee substantial performance improvements in combinatorial tasks.Trade-off between performance and cost in SGE. To evaluate the cost-effectiveness of different methods, we conducted experiments to compare the average performance improvement per method against the average number of LLM calls utilized to solve each combinatorial problem instance. Table 4 gives the results of these experiments, where the number of function calls in CoT and Refine methods was explicitly controlled to make them equal to SGE function calls. The results analysis shows that the SGE method achieves a 27.84% better performance compared to the Decomposition method but requires 87.89% more function calls. Thus, while SGE offers superior performance, it does so at a marginally higher operational cost. Therefore, the application of this method is particularly justified in scenarios where performance gains are prioritized over cost efficiency.To evaluate the versatility of SGE in handling different types of tasks, we conducted experiments across eight datasets commonly referenced in LLM research, categorized into three distinct task types: arithmetic, commonsense reasoning, and symbolic reasoning. Table 3 gives the results of these experiments, with each dataset comprising train and test splits where SGE and baseline methods were applied to the test splits. The results analysis shows that the SGE method demonstrates incremental but consistently superior performance across all task categories. Notably, the method shows particular strength in arithmetic tasks, where it achieves an average improvement of 4.83%, compared to 1.24% in commonsense reasoning tasks and 1.32% in symbolic reasoning tasks. This demonstrates the method's applicability and effectiveness across a diverse range of tasks, extending beyond combinatorial problems. 
conclusion: 
 This study has explored the application of Large Language Models to combinatorial problems, a category of tasks known for their NP-hardness. Our research introduced a 'Self-Guiding Exploration' prompting strategy that effectively utilizes the inherent strengths of LLMs. By generating multiple thought trajectories tailored to various CPs and autonomously decomposing them into manageable subtasks. Our findings confirm that SGE outperforms existing strategies, improving optimization performance by 27.84% and achieving a 2.46% higher accuracy in reasoning tasks. Notably, SGE shows a 34.85% smaller gap with the global optimum on complex tasks like the Job Sheduling Problem compared to baseline methods. These results underline the potential of advanced LLM strategies in complex problem-solving scenarios, suggesting that the right techniques can enhance the utility of LLMs in critical logistics and resource management applications.Despite the performance improvements demonstrated by the SGE, several limitations have emerged that merit attention. Firstly, SGE performance depends on the choice of language model. Secondly, the operational costs associated with SGE are notably higher; it requires 87.89% more function calls than the Decomposition method. These issues present clear avenues for future research. Enhancing SGE's computational efficiency while maintaining its high performance could broaden its applicability and make it a more practical choice for a wider range of problems.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: We have detailed the LLM models used, as well as the specific splits/details for reasoning and combinatorial problem tasks.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [No] Justification: Error bars are not provided. The mean values of LLM few-shot generations are reported, consistent with the standard practice in similar research.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: We believe the paper does not pose such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes]Justification: We have mentioned the companies that own the LLM models used in our experiments.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: A.1 Baseline prompting techniques Combinatorial problems are too complex for solving using direct approach. To solve in several shots, different methods can be used such as few-shot prompting, chain-of-thought, explorationof-thought, decomposition, and self-refine advanced prompting techniques. Traditional few-shot prompting involves teaching an LLM to derive an answer A to a query Q using a limited set of contextual examples D = {E 1 , ..., E |D| }, where A = f (Q, D). In the simplest few-shot setup, examples are formatted as E j = (Q j , A j ), where each Q j , A j are corresponding prompt and solution of example problem j. For Chain of Thought (CoT) prompting, the objective shifts to generating a sequence of intermediate reasoning steps, or "thoughts" T , and subsequently deriving the final answer from T . These in-context examples are structured as E j = (Q j , (T j,1 , . . . , T j,k ), A j ).Exploration-of-Thought techniques, such as those described in [37, 42] , focus on dividing the problem Q into K subproblems and auto-generating thoughtsT k through subproblem queries Q k with T k = f (Q k , T k-1 ).The ultimate answer is then computed as A = f (Q, T K ). In addition to that, in Tree-of-Thought (ToT) and Graph-of-Thought (GoT) prompting strategies, the problem is split into N thought trajectories T n k , using pre-determined subqueries Q n k , with the final answer determined byA = f (Q, T 1 K , ..., T N K ). These strategies necessitate manually identifying effective subqueries Q n k for each specific task (e.g., arithmetic, commonsense, symbolic). Decomposition prompting strategies, as referenced in [48, 12] get Q n k subqueries through in-context examples formatted similarly to CoT exemplars: E j = (Q j , Q j,1 , T j,1 ), ..., (Q j,kj , T j,kj ) A j . Another prompting method called self-refinement [19] uses feedback and refine procedures to generate feedback queries Q n k f eedback and subsequently refine thoughts T n k . In our research we combined these advanced techniques and updated them into new method called self-guiding exploration to enhance performance of LLMs for CPs.Combinatorial problems are decision problems where solver needs to assign binary decision variable x ∈ {0, 1} to minimize some cost function or maximize reward function given input C.Assignment problem. Despite not being classified as NP-hard and solvable in polynomial time using the Hungarian algorithm, the Assignment Problem remains a fundamental combinatorial challenge. This problem entails optimally assigning n tasks to n workers, aiming to minimize the total cost or maximize the total efficiency of the assignments. The input array C is represented as n × n cost matrix, where the element at the i th row and j th column represents the cost of assigning the j th task to the i th worker. The goal is essentially about finding a one-to-one matching between workers and tasks with the objective of minimizing the total cost, i.e.EQUATIONEQUATIONKnapsack problem. The knapsack problem is a classic combinatorial problem, focusing on resource allocation. It is a decision problem in which the goal is to pack items from a set of items with given weights w and values v into a container with a maximum capacity W . The input array C is represented as n × 2 matrix with volume and value information of every item i. The goal is to maximize total value of packed items without exceeding container capacity, i.e.EQUATIONEQUATIONBin packing problem. The bin packing problem is a combinatorial problem that involves efficiently packing n objects of different sizes w into a finite number of k bin containers of fixed capacity W in a way that minimizes the number of bins used. The input array C is represented as n × 1 vector with size information of every item i,EQUATIONEQUATIONTravelling salesman problem. In the travelling salesman problem, given a list of n cities and the distances d between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city. The input array C is represented as n × n cost matrix, where the element at the i th row and j th column represents the cost d ij of travelling between these two cities,EQUATIONs.t.EQUATIONVehicle routing problem. The vehicle routing problem generalizes the TSP by incorporating multiple vehicles into the route planning. The VRP seeks to determine the optimal set of routes for a fleet of K vehicles with maximum capacity P to deliver goods to n customers, typically from a central depot, with the objective of minimizing the total travel cost. In addition to TSP, the input C also includes the demand of each customer, i.e.EQUATIONs.t.EQUATIONIn cases when the capacity P is less than the customer's demand, the vehicle will go between the depot and the customer until the demand is satisfied.Job scheduling problem. The job scheduling problem focuses on scheduling n jobs on m machines, where each job i consists of a sequence of m operations that need to be processed in a specified order. Each operation requires a specific machine for a certain period of time, and each machine can handle only one operation at a time. The input array C is represented as n × m × 2 cost matrix, which stores machine id and completion time for every operation j of every job i. The primary objective is to minimize the makespan, which is the total time required to complete all jobs, effectively reducing the time from the start of the first operation to the completion of the last operation across all jobs.Challenges in solving combinatorial problems. The difficulty of the combinatorial problems like TSP, VRP, JSP, and Knapsack problem stems from several intrinsic and mathematical characteristics common among them. These problems are typically classified as NP-hard, which fundamentally contributes to their computational complexity. As the number of elements (cities, jobs, items, etc.) increases, the number of possible combinations or permutations explodes exponentially. For instance, the TSP with n cities has (n -1)! possible routes to evaluate. This exponential growth means that the time required to examine all possible solutions becomes impractically long even for relatively small n. In addition to that combinatorial problems involve decisions that are interdependent, where the choice for one element affects the options and costs for others. For example, in the JSP, the order in which jobs are processed on one machine can affect the scheduling for other machines. Applicability of SGE to combinatorial problems. For combinatorial problems, obtaining exact solutions is generally computationally prohibitive. Consequently, approximation algorithms and heuristic methods are frequently employed to tackle these challenges. Typically, these problems are broken down into more manageable subproblems. Initial solutions are then generated using heuristic functions, which are subsequently refined through additional heuristic techniques to enhance solution quality. The SGE approach is particularly well-suited for combinatorial problems as it embodies this multi-stage process: it systematically decomposes the problem, explores potential solving methods, and iteratively refines the solutions.To further strengthen our results and provide a comprehensive comparison of our method with well-established solvers and heuristics, we conducted additional experiments on larger instances of combinatorial problems. Specifically, we included experiments with Job Shop Scheduling Problems (Table 5 ) and Vehicle Routing Problems (Table 6 ), comparing our approach against well-known solvers and heuristics. The goal was to evaluate the scalability of our method and assess its performance relative to commonly used combinatorial optimization methods.Recognizing the need for understanding computational overhead, we have also provided an analysis of the computational cost involved in running our algorithm (Table 7 ). We have introduced a new baseline using large language models (LLMs) for heuristic generation, which is included in Table 8 . We used the general version of EoH [17] (originally used for the Bin Packing problem). Specifically, in our case, for the Job Shop Scheduling task, EoH generated heuristics that scored the job nodes, and the algorithm then selected the job with the highest score as the next one in the schedule. However, we found that for more complex tasks than Bin Packing (e.g., TSP), EoH is better employed with Guided Local Search, where simple heuristics like swapping are used for local optimization, and EoH identifies a heuristic that can disturb the local optimum to explore a better region of the solution space. We believe that EoH built in this way, developing specific heuristic programs for each problem instance, would likely perform similarly to Google OR-Tools and achieve better performance. This approach effectively works as a metaheuristic enhancer, providing state-of-the-art results as seen in [17] . There is a depot with coordinates (50, 50) and one vehicle with a maximum capacity of 50. The goal is to find the route that has the minimum total length and go through all the customers, starting and ending at the depot. The initial distances from the depot to each customer are as follows:- Improve the solution given feedback.• Refinement Output:we'll apply a 2-opt optimization to the route. This will involve swapping segments of the route to find a shorter path. Given the route '1 -> 2 -> 3 -> 4', we'll try different swaps and see if we can reduce the total distance further. -Let's simulate the 2-opt optimization on this route.-After applying the 2-opt optimization technique, the final optimized route has been adjusted to: Customer 1 -> Customer 3 -> Customer 2 -> Customer 4, then returning to the depot. This rearrangement was made to minimize the total distance traveled.• Prompt: [Task Description]. [All candidate solutions]. Integrate all previous findings and provide the final answer. Return the answer only as a Python list of elements.• Refinement Output: [1, 3, 2, 4] NeurIPS Paper Checklist38th Conference on Neural Information Processing Systems (NeurIPS 2024).https://github.com/Zangir/LLM-for-CP 


Decision: The paper proposes an LLM prompting algorithm for solving combinatorial optimization problems (COP). Some reviewers had concerns about the importance of the problem. However, studying this subclass of reasoning problems turns out to be interesting. Among the weakness, the reviewers pointed out the lack of comparison with COP tools and not reporting inference time. The rebuttal answered these points, offering comparison with the direct approach of just asking the solution (dubbed IO in the paper). The consensus is that the problem and the algorithm are interesting. I agree with the consensus.

Reviews: review: paper_summary: paper_summary: This paper discusses "Self-Guiding Exploration" (SGE), a new prompting strategy designed to enhance the problem-solving capabilities of Large Language Models (LLMs) in addressing Combinatorial Problems (CPs). The authors demonstrate that SGE leverages the autonomy of LLMs to generate and refine solution paths, significantly improving the models' efficiency in dealing with NP-hard problems prevalent in logistics and resource management. SGE operates by generating multiple thought trajectories for each CP task, breaking these into manageable subtasks, and refining the outputs to optimize results. The proposed strategy surpasses existing methods, enhancing CP optimization performance by 27.84% and achieving a 2.46% higher accuracy in various reasoning tasks compared to the best existing results. This research marks a pioneering effort in applying LLMs comprehensively to a range of complex CPs and establishes new benchmarks in both performance and versatility.
strength_weakness: strength_weakness: 1. Performance improvements are reported primarily in LLMs. The paper should address how the strategy scales with compact models, which are more accessible for practical applications and deployment.
2. The paper could strengthen its argument by providing a broader comparative analysis with other state-of-the-art methods, especially those using different AI approaches to solve combinatorial problems (such as approximation algorithms or heuristics). This would help validate the superiority of SGE across a wider range.
3. The paper occasionally glosses over deep technical details and assumptions within the SGE framework. More detailed explanations of the underlying mechanisms, particularly how the subtasks are autonomously generated and refined, would enhance the paper's transparency and reproducibility.
4. The computational cost of running multiple explorations and refinements on LLMs is not addressed. A detailed cost-benefit analysis would be pertinent, especially for potential adopters who are weighing the economic and environmental implications of such advanced AI techniques.
questions: questions: 1. Can the authors elaborate on how the Self-Guiding Exploration strategy scales with varying sizes of LLMs and combinatorial problems? Specifically, how does SGE perform under constraints of lower computational resources or with compact models?
2. How robust is the SGE strategy when applied to combinatorial problems outside the tested domains, such as logistics and scheduling? Are there specific types of CPs where SGE might not perform as well?
3. While the focus has been on NP-hard problems, has there been any exploration of the applicability of SGE to problems that do not fall into this category? What modifications, if any, would be necessary to adapt SGE to such contexts?
4. Could the authors compare SGE with other AI methods (such as approximation algorithms or heuristics) currently considered state-of-the-art in solving similar combinatorial problems?
limitations: limitations: 1. The strategy's effectiveness relies heavily on large language models' capacities and specific configurations. This dependency could limit the applicability in environments where such models are not feasible due to resource constraints or accessibility issues.
2. The paper primarily presents results for specific problem sizes. It would be beneficial to include an analysis of how well the SGE strategy generalizes across a broader range of problem sizes, particularly large state spaces common in real-world applications.
3. While the paper provides quantitative improvements, the experimental setup could be expanded to include more diverse datasets and problem scenarios to validate the SGE method's robustness and consistency.
4. A significant limitation is the lack of a detailed analysis of the computational, environmental, and operational costs of implementing SGE. 
5. The paper does not discuss how the SGE strategy adapts to evolving data or dynamic environments, which is critical for applications in rapidly changing fields such as logistics and real-time scheduling.
paper_summary: paper_summary: The paper proposes an LLM-based solution for solving standard combinatorial search problems such as TSP and VRP. The proposed solution, called SGE, uses LLMs to (1) propose alternative approaches to solve the problem at hand, (2) decompose a chosen solution approach into subtasks, (3) identify if a given subtask is easy or hard, (4) if it’s easy, just do it, else (5) recursively call SGE to solve the given subtask. Finally, SGE also uses an LLM to integrate the results returned by the above queries. 
Experimental results compared to other LLM-based approaches show huge gains for SGE.
strength_weakness: strength_weakness: 1.	It is not very clear to me why would one want to use an LLM to solve combinatorial problems. 
2.	It seems that SGE is similar to prior work noted by the reviewers for solving these problems via intelligent prompting. The main difference I could see is the part where it checks if a task is easy or not and calls recursively afterwards, and the integration of all the results together.

The authors provide reasonable responses to both concerns.
questions: questions: 1.	Did you consider comparing SGE with a fast suboptimal algorithm for solving the evaluated CPs, e.g., LNS?
2.	Why is the Integrate step done by the LLMs and not directly by parsing and analyzing the answer so far?
limitations: limitations: Not releavnt.
paper_summary: paper_summary: This paper introduces a self-guiding exploration (SGE) framework that integrates exploration-of-thought, decomposition, and refinement prompting strategies to tackle NP-hard combinatorial optimization problems (COPs). The experiments, conducted on various COPs and several reasoning tasks, demonstrate improved performance compared to existing prompt strategies.

*Based on my expertise, I will evaluate this paper from the perspective of combinatorial optimization.*
strength_weakness: strength_weakness: * Figure 2 is lacking in detail. A comprehensive example, including detailed prompts and outputs, should be provided. 
* It appears that the decomposition process cannot be parallelized across subtasks due to the dependence on preceding $T_{k-1}^n$.
* Limited review of related work:
  * LLMs/FMs in CP: Many recent studies are missing. Please see [5] for a comprehensive review.
  * Learning-based methods in CP: Numerous NCO studies, especially those published in the last three years, are missing as well, please see [6].
* My main concern about this paper is the weak experiments, which significantly weaken the contribution of this paper.
  * This paper only considers 5-30 nodes, which is **too small** for the NCO community. I would suggest generating code, like [2-4], in the decomposition or subtask resolution stages if the performance on large-scale instances is inferior.
  * The optimality gap (w.r.t. the traditional solver, e.g., LKH3, OR-Tools) and inference time should be reported.
  * Missing baselines, such as [1-4]. Only several prompt strategies are chosen as baselines.

```tex
[1] Large Language Models as Evolutionary Optimizers
[2] Mathematical discoveries from program search with large language models
[3] Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model
[4] Large Language Models as Hyper-Heuristics for Combinatorial Optimization
[5] https://github.com/ai4co/awesome-fm4co
[6] https://github.com/Thinklab-SJTU/awesome-ml4co
```
questions: questions: N/A
limitations: limitations: Yes, the authors discuss the limitations, such as more function calls, and the sensitivity to the used LLMs.

Comments: title: Thanks! many aspects have been clarified
One limitation response that did not fit into the rebuttal
comment: Thank you very much for your feedback. We appreciate your review that have helped us enhance our work.
I am pretty satisfied with the authors' responses. 
The comparisons to suboptimal solvers is especially exciting to me, and I think it must be in the paper.
Thank you for your valuable feedback. We greatly appreciate your support and are pleased that our revisions have addressed your concerns.
Thanks for your response, which addresses my concerns. I decided to raise my score.
Thank you for your question. We used general version of EoH (that was used for Bin Packing problem). Specifically, in our case, for the Job Shop Scheduling task, EoH generated heuristics that scored the job nodes, and the algorithm then selected the job with the highest score as the next one in the schedule. However, we found out, for more complex tasks than Bin Packing (e.g. TSP), EoH is better employed with the Guided Local Search, where simple heuristics like swapping are used for local optimization, and EoH identifies a heuristic that can disturb the local optimum to explore a better region of the solution space. We believe that EoH that is built this way and is developing specific heuristic programs for each problem instance would likely perform similarly to Google OR-Tools and achieve better performance. This way it works more like a metaheuristic enhancer and will give SOTA results like in [4]. Thank you again for your question, we will add this duscussion to our paper as well.
Thanks for your responses. It is surprising that SGE can outperform EOH (Table 4), which is the current SOTA based on code generation. Could the author elaborate on why this might be the case?
Thank you once again for your valuable feedback.
Thank you for your response and additional experiments. All my concerns are addressed and I have updated my score.
__Comment:__ The paper should address how the strategy scales with compact models.

__Response:__ Thank you for highlighting this important consideration. Regarding this comment, we already evaluated the scalability of our strategy with more compact models in our paper. Specifically, we included experiments with the LLaMA models, as detailed in Figure 4 (paper).

To clarify your comment further, we presented results for both the LLaMA-2-70B model, which requires around 140 GB of VRAM, and the LLaMA-2-7B model, which operates on just 14 GB of VRAM. Additionally, the LLaMA-2-7B model, when quantized, achieves a 4x reduction in VRAM requirements, allowing it to run on a single NVIDIA RTX GPU. This demonstrates the model's suitability for both the research community and practical deployments.

We hope this answers your concern regarding the scalability of our strategy with compact models. However, if you are referring to even smaller models, as mentioned in the paper and noted in the limitations section, SGE heavily depends on the underlying LLM, and smaller models like 1B do not exhibit strong performance. Once again, we appreciate your attention to this aspect of our work.