Self-Guiding Exploration for Combinatorial Problems

Comment: Figure 2 is lacking in detail. A comprehensive example, including detailed prompts and outputs, should be provided.

Response: Thank you for your feedback. Regarding this comment, we aimed to provide a comprehensive textual example, including prompts and model outputs, exactly in Figure 3. To clarify this concern, the first box of Figure 3 shows the text of the prompt that includes the TSP problem definition and the exact output from the Exploration stage of our method. The [Return Condition] represents the prompt text specific to the exploration stage, as discussed in Section 4.1 of the paper. These [Return Conditions] are general prompts that can be applied to various problems without modifications.

The third box again repeats the problem definition, this time joined with the candidate solution. If this figure remains unclear, we added a new figure with detailed examples of prompts and outputs solving a VRP instance, both in the paper and in the rebuttal PDF. We hope this explanation clarifies the intent behind Figure 3 and addresses your concerns.

Comment: It appears that the decomposition process cannot be parallelized across subtasks due to the dependence on preceding Tk−1n.

Response: Thank you for your observation. Regarding this comment, the decomposition process is inherently sequential by design. The tasks within a single decomposition are meant to be executed in sequence, not in parallel. For example, Task $T_{k-1}^n$ might involve computing the distance from the current node to all other nodes, followed by Task $T_{k}^n$, which chooses the closest node as the next node to go to.

These steps are dependent on each other and thus cannot be parallelized. However, processes from different decompositions can be parallelized. For instance, if one trajectory solves the VRP using the Ant Colony Optimization method and another uses the Nearest Neighbor approach, these processes are independent and can be executed in parallel.

Comment: Limited review of related work:

Response: Thank you for pointing this out. Regarding this comment, we initially did not include certain papers in our review because we believed they focused on different approaches, specifically tuning heuristics to specific instances of combinatorial problems. We now recognize the importance of including these related works to provide a more comprehensive literature review. We have extended our review to include these papers [1-6], acknowledging their relevance and contributions to the field. We hope this expanded literature review addresses your concern and provides a more complete context for our work. Thank you again.

Comment: 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.

Response: Thank you for your comment. We initially focused on small problem sizes due to lower computational costs and the ability to obtain optimal solutions. The models without code interpreter are indeed inferior on large scale, but GPT4 with code interpreter can still show good results. Based on your feedback, we have extended our experiments to include larger instances. To evaluate the performance of SGE against other state-of-the-art methods, we conducted experiments on larger problem sizes across various combinatorial problem domains. Table 1 (rebuttal) presents results on Job Shop Scheduling problems with 50 and 100 jobs, while Table 2 (rebuttal) shows experiments on the Vehicle Routing Problem with 100, 150, and 200 nodes. The results analysis shows that SGE performs better than LNS but falls short compared to LKH3 and Google OR-Tools, which are specifically tailored for combinatorial tasks. However, SGE remains applicable to a broader range of tasks (e.g. reasoning tasks). We believe that SGE's performance could improve further once libraries like LKH3 and Google OR-Tools are integrated into GPT-4's code interpreter, allowing our algorithm to leverage these tools within its solution trajectories.

Comment: The optimality gap (w.r.t. the traditional solver, e.g., LKH3, OR-Tools) and inference time should be reported.

Response: We appreciate your suggestion. In our original submission, we provided a comparison between SGE and Google OR-Tools, as shown in Table 2, focusing on small-size problems where globally optimal solutions could be achieved through exhaustive depth-first search. However, to further address your comment and enhance our analysis, we have conducted additional experiments, as mentioned earlier. The results from these larger-scale experiments (Tables 1 and 2), now included in our paper.

Comment: Missing baselines, such as [1-4]. Only several prompt strategies are chosen as baselines.

Response: Thank you for pointing this out. Regarding this comment, we acknowledge the importance of including relevant baselines. We assume that [2,3] may perform better than our approach on the Bin Packing problem, but according to [2], this is possible when a diverse list of programs (heuristics) is available as a database to avoid local minima. However, our goal was to develop an algorithm that does not rely on pre-existing examples of good solutions.

To clarify further, we believe that using [3] (EoH) as a baseline is sufficient, as EoH is an improved version of [1,2]. We chose not to use [4] as a baseline, because it was published very recently, just before the NeurIPS deadline (although it's a good model). However, we have extended our paper to include the EoH baseline and have run its implementation on Job Shop Scheduling (JSP) problems. Table 4 (rebuttal) shows the results of SGE versus EoH. The analysis indicates that while the results are close, SGE achieved slightly better performance. We hope this additional comparison addresses your concern.

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.

Comment: It is not very clear to me why would one want to use an LLM to solve combinatorial problems.

Response: Thank you for your comment. The use of large language models to solve combinatorial problems offers an advantage by choosing a specific set of heuristics/metaheuristics tailored to concrete situations. Essentially, LLMs can function as highly flexible metaheuristics that possess knowledge of various heuristics and metaheuristics. As LLMs continue to advance, we expect that their ability to produce effective solutions in this domain wil improve.

Comment: 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.

Response: Thank you for your comment. Regarding this observation, we acknowledge that different papers have explored various high-level prompting strategies. In our paper, we combined three of these approaches into a unified framework. However, to clarify your comment further, our method differs from prior work in that it is fully self-guiding. Unlike previous methods that rely on in-context learning with specific examples or prompts tailored to each problem, our approach does not require such modifications from problem to problem. (Please refer to the differences in the answer $A$ equations in Section 4.1 and A.1 (our approach does not require exemplars $E$)).

The primary aim was to evaluate whether this self-guiding strategy could effectively improve performance on complex tasks while also maintaining strong results in reasoning tasks. We hope this addresses your concern and provides a clearer understanding of our approach.

Comment: Did you consider comparing SGE with a fast suboptimal algorithm for solving the evaluated CPs, e.g., LNS?

Response: Thank you for your question. Regarding this, we did consider comparing SGE with fast suboptimal algorithms, such as Large Neighborhood Search. To address this, we added two experiments to evaluate the performance of SGE against other well performing methods on larger problem sizes than considered in the paper. Table 1 (rebuttal) presents results on Job Shop Scheduling problems with 50 and 100 jobs, while Table 2 (rebuttal) shows experiments on the Vehicle Routing Problem with 100, 150, and 200 nodes. The results analysis shows that SGE performs better than LNS but falls short compared to LKH3 and Google OR-Tools, which are specifically tailored for combinatorial tasks. However, SGE remains applicable to a broader range of tasks (e.g. reasoning tasks). We believe that SGE's performance could improve further once libraries like LKH3 and Google OR-Tools are integrated into GPT-4's code interpreter, allowing our algorithm to leverage these tools within its solution trajectories.

Comment: Why is the Integrate step done by the LLMs and not directly by parsing and analyzing the answer so far?

Response: Thank you for your question. Regarding this comment, the Integrate step is handled by the LLMs because the task involves more than simply choosing one of the solution trajectories. Instead, the LLM may combine elements from different solution trajectories to potentially create a more optimized overall solution. By allowing the model to perform this integration, it can either select the best individual solution or combine parts from multiple solutions to enhance performance. We hope this explanation clarifies the rationale behind our approach.

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.

Comment: The computational cost of running multiple explorations and refinements on LLMs is not addressed.

Response: Thank you for bringing this important aspect to our attention. Regarding this comment, we have added a new analysis to address the computational cost of running multiple explorations and refinements on large language models.

To evaluate the cost-effectiveness of our approach, we conducted experiments on the Vehicle Routing Problem using the GPT-4 model. Table 3 (rebuttal) presents the average computational cost associated with these experiments. However, while the costs are substantial for large models like GPT-4, using open-source models such as LLaMA can significantly reduce expenses, particularly when running on personal hardware.

We have incorporated this new analysis into the main paper to strengthen the discussion on the economic implications of our approach. We hope this addresses your concern.

Comment: Can the authors elaborate on how the Self-Guiding Exploration strategy scales with varying sizes of LLMs and combinatorial problems?

Response: Thank you for your question. Regarding this comment, we acknowledge the importance of understanding how the SGE strategy scales with varying sizes of LLMs and different combinatorial problems.

To clarify, the performance of SGE does improve with larger models; however, the scale of improvement is not linear. For instance, while the LLAMA-7B model exhibits lower performance compared to the LLAMA-70B model, the difference in performance is not proportional to the difference in model size. This suggests that while larger models offer better results, smaller models like LLAMA-7B still perform reasonably well, though not as effectively.

We did not include results from smaller LLMs in our paper because open-source models smaller than LLAMA-7B generally perform worse. However, we believe that fine-tuning these smaller models using supervised learning with examples of methods to solve combinatorial problem tasks could potentially enhance their performance.

Regarding larger models, as presented in Tables 1 and 2 (rebuttal), the results show that SGE performs comparably to other solvers even with larger problem sizes.

Comment: Are there specific types of CPs where SGE might not perform as well?

Response: Thank you for this thoughtful question. Regarding this comment, we acknowledge the importance of understanding the robustness of the SGE strategy across different combinatorial problem domains.

In our current study, SGE has shown performance improvements in the tested domains (Table 1, paper), including Vehicle Routing and Job Shop Scheduling problems. However, we recognize that real-world applications often involve more complex scenarios, such as stochastic or dynamic versions of these problems.

While testing SGE on stochastic and dynamic combinatorial problems is indeed a valuable direction for future research, it is a distinct area within combinatorial optimization and is beyond the scope of our current work. We plan to explore this in subsequent studies.

Comment: What modifications, if any, would be necessary to adapt SGE to such contexts?

Response: Thank you for your question. Regarding this comment, our primary goal in designing the SGE method was to develop a general approach that could be applied across a broad range of problem types, such as both combinatorial and reasoning tasks.

To validate the robustness of our model, we extended our experiments to include reasoning tasks that are well-established benchmarks in the LLM research community. The results of these tests are presented in Table 3 of the paper.

To achieve this, we have employed the same algorithm without modifications across these contexts. This design choice was intended to ensure that SGE remains versatile and effective across various problem domains.

We acknowledge that specific modifications to SGE could potentially improve its performance for certain types of problems that do not fall into the NP-hard category. However, our main objective was to create an algorithm that balances generality with strong performance across a wide spectrum of problems, and we believe the current implementation of SGE achieves this balance.

Comment: Could the authors compare SGE with other AI methods?

Response: Thank you for your insightful comment. Regarding this comment, we already provided a comparison between SGE and Google OR-Tools in our original submission, as shown in Table 2. In these experiments, we focused on small-size problems where globally optimal solutions could be found using a full search via Google OR-Tools, employing depth-first search to exhaustively explore all possible solutions.

However, to further clarify your comment and expand the breadth of our analysis, we have conducted additional experiments and included new comparative results. To evaluate the performance of SGE against other state-of-the-art methods, we conducted experiments on larger problem sizes against various combinatorial solvers. Table 1 (rebuttal) presents results on Job Shop Scheduling problems with 50 and 100 jobs, while Table 2 (rebuttal) shows experiments on the Vehicle Routing Problem with 100, 150, and 200 nodes. The results analysis shows that SGE performs better than LNS but falls short compared to LKH3 and Google OR-Tools, which are specifically tailored for combinatorial tasks. However, SGE remains applicable to a broader range of tasks (e.g. reasoning tasks). We believe that SGE's performance could improve further once libraries like LKH3 and Google OR-Tools are integrated into GPT-4's code interpreter, allowing our algorithm to leverage these tools within its solution trajectories.

We have incorporated these new tables into the main paper to provide a more comprehensive analysis. We hope this addresses your concern.

Thank you once again for your valuable feedback.