DRoC: Elevating Large Language Models for Complex Vehicle Routing via Decomposed Retrieval of Constraints
Authors: Xia Jiang
Yaoxin Wu
Chenhao Zhang
Yingqian Zhang
Venue: ICLR 2025 Poster (2025)
Keywords: vehicle routing problems; large language model; retrieval augmented generation
Primary area: optimization

Abstract: This paper proposes Decomposed Retrieval of Constraints (DRoC), a novel framework aimed at enhancing large language models (LLMs) in exploiting solvers to tackle vehicle routing problems (VRPs) with intricate constraints. While LLMs have shown promise in solving simple VRPs, their potential in addressing complex VRP variants is still suppressed, due to the limited embedded internal knowledge that is required to accurately reflect diverse VRP constraints. Our approach mitigates the issue by integrating external knowledge via a novel retrieval-augmented generation (RAG) approach. More specifically, the DRoC decomposes VRP constraints, externally retrieves information relevant to each constraint, and synergistically combines internal and external knowledge to benefit the program generation for solving VRPs. The DRoC also allows LLMs to dynamically select between RAG and self-debugging mechanisms, thereby optimizing program generation without the need for additional training. Experiments across 48 VRP variants exhibit the superiority of DRoC, with significant improvements in the accuracy rate and runtime error rate delivered by the generated programs. The DRoC framework has the potential to elevate LLM performance in complex optimization tasks, fostering the applicability of LLMs in industries such as transportation and logistics.

Published as a conference paper at ICLR 2025
DROC: ELEVATING LARGE LANGUAGE MODELS FOR COMPLEX VEHICLE ROUTING VIA DECOMPOSED RE- TRIEVAL OF CONSTRAINTS
Xia Jiang', Yaoxin Wu'; Chenhao Zhang", and Yinggian Zhang*
l Eindhoven University of Technology, The Netherlands Southeast University, China j.jiang1@tue.no @@tue.nl, y. wu22tuue.nl, zlangchentaasseefooomml..ccoo yqzhang@tue.r nl
ABSTRACT
This paper proposes Decomposed Retrieval of Constraints (DRoC), novel frame- work aimed at enhancing large language models (LLMs) in exploiting solvers tackle vehicle routing problems (VRPs) with intricate constraints. While LLMs have shown promise in solving simple VRPs, their potential in addressing complex VRP variants is still suppressed, due to the limited embedded internal knowledge that is required accurately reflect diverse VRP constraints. Our approach miti- gates the issue by integrating external knowledge via novel vetrieaal-augmente generation (RAG) approach. More specifically, the DRoC decomposes VRP con- straints, externally retrieves information relevant to each constraint, and synergisti- cally combines internal and external knowledge to benefit the program generation for solving VRPs. The DRoC also allows I.LSs to dynamically select between RAG and self-debugging mechanisms, thereby optimizing program generation with- out the need for additional training. Experiments across 48 VRP variants exhibit the superiority of DRoC, with significant improvements in the accuracy rate and runtime error rate delivered by the generated programs. The DRoC framework has the potential to elevate LLM performance in complex optimization tasks, fostering the applicability of L.MMs in industries such transportation and logisties.
INTRODUCTION
Vehicle Routing Problems (VRPs) are central computer science and combinatorial optimization, serving as a foundational benchmark for evaluating computational complexity and developing ap- proximation algorithms (Pillai & Singh 2023). Beyond their theoretical significance, VRPs also major focus in operations research (OR), where they model recision-making processes in various industrial domains. The NP-hard challenge of VRPs in practice escalates substantially with the complexity of composite constraints, reflecting the interplay between theoretical and practical aspects. Different solvers such as OR-tools and Gurobi are commonly used due to their accessibility and generic modeling capabilities. Despite easy applications in simple VRPs, for users who lack modelling and optimization skills, these solvers are hard to use for solving VRPs with composite constraints, since 1) there are few example codes/doccmenttation to explain the modeling of vari- ous constraints, and 2) developing programs for complex VRPs necessitates expert-level domain knowledge. Hence, it is challenging for non-experts to successfully apply the solvers to real-wor worl-world operations AkhmadiTeshnizz et al. 2024). Consequently, researchers have increasingly focused on automating problem- problem-solving procedures mitigate dependence domain and modelling expertise.
Large language models (LLMs) have demonstrated expert-level performance in several domains AAmeida et al.) (2024) and have recently been applied to optimization problems in OR (Xiao et al.) 2023: Zhang et | 2024a). Their advanced reasoning and generation capabilities offer the potential automate modeling lin and programming tasks. Despite the success in solving simple optimization problems, LLMs frequently face limitations when dealing with VRPs characterized by composite constraints (see Figure]] I which benchmarks GPT-3.5-turbo 48 VRPs used this paper). This
"Corresponding author

---

Published as a conference paper at ICLR 2025
challenge arises from LLMs' bounded internal knowledge since the Nomain--speciff corpus is insufficient during training processes. As result, LLMs exhibit deficiencies in generating programs for VRPs, and they lack capabilities of I) the accurate formulation of some specific constraints, and 2) the integration of heterogeneous constraints within a generated program. They pose significant obstacles to the widespread application of LLMSs in solving complex VRPs in real-world scenarios, particularly those distinguished by intricate constraints. For instance, state-of-ther based methods often f'ill to address complex problems due incorrect constraint modeling with coding errors (Ahmadi Seemadi'esshinn Teshnizi et al. 2024). Therefore, we aim for the integration of external knowledge into LLMs and target improving constraint modeling in program generation for VRPs.
(SOTA) LLM-
Inspired by Chain-of-Thought (CoT) (Wei et al. 2022) and Divide-and-Conquer (DaC) paradigms (Zhang et al., (0024b), which showcase that com- plex tasks can be solved by an LLM through a de- composed manner, we propose a systematic inte- gration external knowledge and decomposition techniques enhance LLMs in program generation for VRP solvers. Specifically, we introduce a novel retrieval-augmented generation (RAG) framework, termed Decomposed Retrieval of Constraint (DRoC), which enables LLMs more effectively address com- plex VRPs without additional training. The DRoC framework facilitates the incorporation of external knowledge retrieved from documentation and exam- ple codes. Notably, we perform constraint- based de- composition for the target VRP during the retrieval process, which further enhances the correctness and of generated programs. In addi- tion, our framework synergistically combines external and internal knowledge by empowering LLMs to dynamically select between RAG and self-debugging mechanisms, continuously optimizing the program generation process. We conducted experiments across a set of 48 assorted VRPs and further extend the method to other OR problems, demonstrating the efficacy of the DRoC framework.
Successfu Number variants
The number of sogitions contralins
12
20
Figure I: 48 VRP variants with different numbers of composite constraints. Performance declines with increased constraints.
The evaluation of gpt-3.5-turbo on
2
RELATED WORK
2.1 LLMS FOR VRPs
The advent of LLMs has facilitated advanced approaches to VRPs. LLMs can embed different problems by natural language and thereby enable multi-task model for tackling simple OR problems, including basic travelling salesman problem (TSP) and capacitated vehicle routing problem (CVRP) (Jiang al. 2024). The heuristics for addressing VRPs automatically searched through LLMs with the aid of evolutionary computation (EC) (Liu et al., 2024 Ye et al., 2024). However, these methods typically aim evolve pre-defined algorithm types such guided local search, necessitating much domain-speciff knowledge and prerequisites. Also, they often entail a substantial number of
LLM invocations for evolution, e.g., for creating and maintaining a population of algorithms.
Alternative research focuses on the modeling and programming of OR problems including VRPs based on the textual descriptions. These approaches aim to transform user queries into mathematical formulations and executable code recognizable to external solvers (Zhang et al. 2024a Tang et al. 2024). Further, the introduction of multi-agent frameworks enables the coordination among structured sequence of L.LM agents to perform tasks including formulation, programming, and evaluation for a target problem (Xiao et al., 2023 Ahmadi AhsadiTeshnizii et al.) 2024). Nonetheless, these methods predominantly rely the intrinsic knowledge embedded within LLMs, which limits their efficacy in addressing problems beyond the scope of their training data. This paper delves into directly generating programs for solving complex VRPs by integrating LLMs' internal knowledge and external references, without the process of mathematical model formulation.
NCO methods for VRPs. Beyond LLMs, quite few approaches automate end-to-end solutions for VRPs through deep (reinforcement) learning, collectively known as neural combinatorial optimization
(NCO) (Kool et al. 2019 Kim at. 2022 [uoo et.l. 2023 The predominant NCO methods typically
2

---

Published as a conference paper at ICLR 2025
employ Transformer-lit like neural architectures to process features (e.g., customer coordinates) in VRP instances by encoders and construct VRP solutions (i.e., tours) by the decoder. While these methods bypass the reliance manually designed heuristics to some extent, the heavy NCO models are often trained separately on individual and simple VRP variants (Hottung et al. 2021 Wu et al. 2021] Zhou et al. [2023a] Goh al., 2024) with massive time cost. Moreover, the simplified constraint-handling strategies hamper their applicability to complex VRPs with intricate real-world constraints.
2.2 RETRIEVAL-AUGGMENTE GENERATION
RAG approaches leverage the input sequence to retrieve relevant documents, which are subsequently utilized supplementary context while generating the target sequence. As potent mechanism to inject external knowledge into LLMs, the RAG is widely studied for language tasks, such as question answering (QA) (Lewis al. 2020; Jiang al.. 2023), dialog generation (Shen et al. 2023), and fact verification (Wang et al. (023). In addition. there are some efforts applying RAG in code generation, which generally retrieve information from different sources, such web content (Parvez et al. 2021]
fixed repository (Zhang et al. 2023), code documentation (Zhou et al. (2023)) or the combination of multiple resources (Su al. 2024). Interested readers can refer (Gao et al., 2023) for thorough and systematic review. VRP solvers usually have elaborate documentation and example codes contributed by the community, which can serve as external knowledge sources for RAG. However, retrieving irrelevant documents is probably unhelpful and even harmful to performance (Yoran et al., 2024). To address this, we decompose the retrieval for separate constraints and progressively refine the documents, which enhances the performance of RAG in generating more accurate programs.
3 PRELIMINARIES
3.1 VEIICLE ROUTING PROBLEMS
The objective of typical VRPs is to determine a set of vehicle routes with the least cost. The basic constraints are 1) each customer is visited exactly once by single vehicle, and 2) all vehicles depart from and return to one or more depots (Braekers et al. (2166). Suppose that there is one depot indexed by the commonly used objective for VRP with m vehicles and n customers formulated as
J= min ΣΣΣ REM IEN JEN
Cajatt
where M = (1...., m) and N = {0, 1, I....,,I n) represent the set of vehicles and the locations of depot and customers, respectively. Czj is the traversal cost between customer i and j. and æfy is the binary decision variable, indicating if vehicle k E M traverses from i to
A typical set of constraints for VRPs is formulated follows,
ΣΣ REM
2 =1
ViE N
(2)
JEN
Σ
J0j
Vk M
(3)
JEN
Σ N/O
=1 1
Vk E
(4)
IEN
Σ JEN
Σ
J WENNEEM
(5)
JEN
where Eq. (2) ensures each customer is visited exactly once by only vehicle; Eq. 3 and Eq. means vehicles depart from and return to the depot; Eq. (5) ensures the vehicle flow conservation. Besides the above basic constraints, different VRP variants characterized by various constraints that reflect practical restrictions for vehicle routing in real life.
In this paper, consider the following additional VRP constraints: 1) Vehicle capacity, limiting the maximum load a vehicle can carry; 2) Distance (or duration) limit, restricting the total distance or time vehicle can travel; 3) Time windows, requiring vehicles visit eustomers within specified
3

---

Published as a conference paper at ICLR 2025
time intervals; 4) Multiple depots, allowing vehicles to start and end routes at different depots; 5) Open route, where the start and end node of vehicles are not specified: 6) Prize collecting, optimizing routes by balancing the penalty of locations that are not visited; 7) Pickups and deliveries, managing paired pickup and drop-off demands within a route; 8) Service time, accounting for the time spent in serving customers each location; 9) Resource constraints, limiting the number of vehicles that can be loaded or unloaded at the depot simultancously, potentially causing delays in departure or return. VRP variants featured by combinations of the above constraints are elaborated in Appendix [
Typically, a VRP, including its objective and constraints, is expected to be formulated as a mathemati- cal program by a human expert. Once the problem is accurately modeled, existing solvers, such as Gurobi Gurobi 2024) and OR-Tools (Furnon & Perron 2024), can be called to solve the given VRP.
3.2 PROBLEM FORMULATION
We solve code generation (or code completion) problem, without the mathematical model formula- tion process as done in [Ramamonjison et al. [2022] Xiao et al.) [2023] A Teshnizi et al. (2024). In our approach, the input to an LLM consists of the name of VRP variant and the corresponding function signature, which specifies the function's 's name, its parameters, and parameter types. With each parameter in the function described by the doestring, the LLM is responsible for completing the "solve" function by invoking a designated solver. We illustrate an example of the function signature in Appendix B Compared to using textual descriptions of problems as input (Huang et al. 2024), our formulation offers better generalization for two reasons: 1) once function is successfully generated, it can be applied to all instances of that specific VRP variant, and 2) only describing basic docstrings reduces the volume of input an LLM and minimizes the inference effort required for prompting.
Formally, given an input q representing a VRP, an LLM P(y q) generates a program recognizable to solver, which can be applied solve the VRP We assume the availability of a collection of documents D, where each document corresponds to a part of documentation or example codes for the solver. During the RAG process, the generation is conditioned on a particular subset of documents D. S D. The marginalized generation probability over all D. S D is given by,
Ply q, D)
Σ Ply D.D, q) D.CD
(6)
As enumerating all possible subsets is computationally infeasible, we use retriever R to select the most probable subset of documents D. := arg maxd,ço (R q, D), and thereby enables the LLM to produce program based on the most likely relevant documents:
P(y D) = Ply D.) P(D. 9)
4 METHODOLOGY
Our approach aims to enable LLMs to invoke solvers more accurately for solving VRPs by decom- posing the problems and integrating external knowledge. Solving VRPs using LLMs is characterized by the following aspects: 1) Once the generated program successfully verified on a single instance, it can be applied to all problem instances of the same structure (e.g., the same types of constraints and input parameters). This allows for convenient self-debugging on a simple instance using the LLM and the code executor; 2) The structure of code for addressing different VRPs is mostly the same when calling the same solvers, and the primary variation lies in how constraints are programmed through the solver API functions. These characteristics of LLMs motivate us perform decomposed retrievals for specific constraints and enhance the quality of code generation. Therefore, we propose the DRoC framework that elegantly amalgamates the two aforementioned points. The framework is illustrated on the left subfigure of Figure 2 which is carried out in the following steps:
Direct code generation: An LLM as the first- first-time generator is prompted directly by the input q (i.e., a VRP) to generate a program y. without external information retrieval. Here the code generation purely depends on the internal knowledge of LLM, prompting it to solve the problem by its inherent programming capability.
Step 1:
Step 2: Code check: The program generated in Step is run by code executor, invoking solver to solve the VRP. The LLM will be provided with execution traceback the code contains errors, meaning an injection of external knowledge into the I.I.M
4

---

Published as a conference paper at ICLR 2025
Component with only internal knowleege
Mandatory puth
Optional path
Input
Component with external knowledgg
Documentation
routing solver
Large language model
VRP with C C. U Cy
calbackk...
posilly differest and end bostons veluole...
Step generation
decomposition
Solution function
if passed
Executor
codo check
Skep 2:
G retrieval
retrieval
Cz
retriesal
Cy
doteave callockiivee inde,
Example code
ToNiskefonn, inale))
not passed
external knowlodee
external knowlodge
external
setam Maseee reane" "foer nced to rodd)
nece iines lshodeio indes)
Router
Lnowledgee
mangge presasp wew.repoooitiatteeeaaaeaee
First stage filser
dusihssnd deaj (eeefl
Siep St soroinngg
IF melippp decuments temminitus
Execution Trucehack
Secoad stage filer
Debuggeer
Retriever
cuntext
bunlext
context
mokie sell spseen ixpertinane "agg. "Eoagg))
fomonoods
MedaleNellcaddieee No modals named umer commanstr
Step 4 (I) self debrag
(Il)
Generation
decomposed retrieval
Overall pipeline
Decomposed retrieval
External knowledge sources
Figure Overview of the proposed DRoC framework.
Step 3: Routing: According the execution traceback, an LLM as router determines the operation in Step 4, cither self-debugging (I) or RAG (II).
Step 4 (I): Self-debugging: An LLM as the self-debugger analyzes the execution traceback (and errors) and attempts to refine the code, which produces a new version of the program.
Step 4 (II): Decomposed retrieval: The retrieval is decomposed to refer LLM to external documentation or example codes for seeking relevant documents separate constraints of the target VRP, so as to enhance the accuracy code generation.
In the following subsections, we present the detailed process of the DRoC framework.
4.1 EXTERNAL KNOWLEDGE SOURCES
As VRP solvers generally have elaborate documentation and example codes contributed by the community, we incorporate them into our external knowledge sources for retrieval rather than relying solely on single-source data as is common in literature (Zhang et al. 2023 Zhou et al. 2023b). For example, Google's 's OR-Tools (Furnon & Perron 2024) provides a detailed tutorial for solving VRPs in its online documentation and has ample example codes in its open-source repository 2 The multi-source information can be more synergistic and actively utilized by the LLM during RAG.
In addition, we leverage feedback from the code executor (e.g., Python interpreter) to empower the LLM to precisely identify errors within the code. Unlike the retrieval of documents from other knowledge sources (e.g., documentation and example codes), which typically requires conducting a semantic similarity search in embedding space, obtaining execution feedback involves direct access to information generated by the interpreter (Su et al. 2024). such as error information and traceback.
Using OR-Tools as an example, the external knowledge is briefly shown on the right subfigure of Figure 2 We also investigate a dynamic knowledge source update via Bootstrap for potential performance improvement, which is discussed in Appendix (G] Note that external knowledge contains both relevant and irrelevant data, so it is critical to design an effective and precise retrieval mechanism.
4.2 DECOMPOSED RETRIEVAL
Despite the availability of documentation and example codes for solver, such as those for OR-tools, generating accurate programs for a VRP (with composite constraints) is still challenging, due to the difficulty in obtaining appropriate context to guide LLMs via RAG. On one hand, external
5

---

Published as a conference paper at ICLR 2025
knowledge sources typically contain exemplar problems with simple constraint structures and may not directly provide documents relevant to the target VRP. On the other hand, the retrieval process may overlook critical constraints if the problem is not properly decomposed. For example, using keywords like "open capacitated vehicle routing problem" often results in retrieving documents related to CVRP, neglecting the key constraint of the open route. This underscores the need for more nuanced approach to ensure that all relevant constraints are consistently considered. To overcome the issue, we propose to progressively cope with the constraint in decomposed manner. We break down the retrieval into three sub-processes, including problem decomposition, single-come cenge-consttri resolution, and context merging. Specifically, we first decompose a target VRP into individual constraints and then resolve these constraints by retrieving from external knowledge sources. Finally, the retrieved documents are merged to form the context for the LLMs, which are used to guide the code generation.
Problem decomposition. To formulate queries for retrieval and handle constraints separately, we decompose the target VRP based on its constraints. In addition to the general constraints formulated by Eq. 2
( 5). the VRP variants have their own specific constraints, e.g., the additional constraints described in Section 3.1 Since these constraints are known (Elshaer & Awad 2020), LLMs have basic understanding of their meaning. Therefore, we employ decomposer (i.e., an LLM) to split the constraints of the target VRP into individual items, with each represented by a keyword of the corresponding constraint. As shown the middle subfigure of Figure 2 C₁, C2, ... Cio keywords of individual constraints. A VRP with w additional constraints produces w keywords.
congla-costtraitt resolution. The limited internal knowledge of LLMs hinders their ability to accurately generate codes for specific constraints. We enhance them by retrieving relevant external knowledge (i.e., documentaaioon/exampll codes). We employ OpenAl's embedding model transform external knowledge into embeddings for dense retrieval. The retriever uses the input "Python code of i E {I...., w) as query Q, to conduct a semantic similarity search among all the embedded documents. With the embedding En of each document d E 'D and the embedding Eq. of the i-th query text, we use squared Euclidean distance to measure the similarity between Q; and each document d:
E
DQs
= Σ (E)
E/²
(8)
j=1
where E' denotes the dimension of the embedding space. The top-k nearest documents are selected by the retriever as the candidates for the corresponding constraint.
Given that external knowledge may contain irrelevant information, we implement a two-stage filter to refine the candidate documents for each constraint. The first stage involves invoking an LLM (i.e., first-stage filter) to assess the relevance between the documents and the constraint C.. By doing so, the LLM is tasked with explicitly articulating the rationale behind the identified documents relevant, which refer to pertinent documents as supporting evidence. The output is structured into three fields: relevant, code snippet, and summary, with an example in Appendix A.2 The second stage is activated multiple documents remain after the initial filtering. An LLM (i.c., second-stage filter) is instructed to aggregate the documents and their corresponding summaries, ultimately selecting the most relevant one D, for C, through comparative analysis fulfilled by the LLM itself.
Context merging. After obtaining all the single-constree for each constraint, we simply concatenate them as the merged generation context, which is defined by D. (D....., } The context as part of the input to the LLM is used to generate new programs.
contexts, i.e., the most relevant document
4.3 IMPLEMENTATION DETAILS
Given the pipeline of DRoC illustrated in Figure 2 we allow the LLM to generate code up iterations, meaning the process will terminate even if a successful program, which outputs feasible solutions to the given VRP, is not obtained after attempts. Specifically, if the first-time generator fails to produce an appropriate program using only its internal knowledge, router (i.e., an LLM) is invoked to dynamically choose between two strategies for utilizing external knowledge: self- debugging decomposed retrieval. We employ two distinct prompt templates to guide the LLM's role in leveraging the retrieved external knowledge: the surieval-augmenter generator and the retrieval-ane retrieval-uugmented debugger. More precisely, the retrieval- augmented generator is triggered only once, in order to generate a completely new program based on the retrieved context, while the retrieval-augmented debugger is invoked for the remaining I 2 iterations progressively refine

---

Published as a conference paper at ICLR 2025
Table 1: Performance of different methods with gpt-3.5-turbo and gpt-4o. The reported values are averaged over the results of 48 VRP variants.
Method (gpt-3.5-turbo)
AR f
RER
Method (gpt-4o)
AR f
RER
Standard Prompting
14.58%
66.67%
Standard Prompting
20.83%
58.33%
CoT
8.33%
79.17%
CoT
22.92%
50.00%
РHP
12.50%
79.17%
РHP
22.92%
54.17%
Self-debug
14.58%
66.67%
Self-debug
31.25%
37.50%
Vanilla RAG
10.42%
60.42%
Vanilla RAG
37.50%
31.25%
Self-RAG
16.67%
56.25%
Self-RAG
33.33%
39.58%
DRoC (Ours)
20.83% %
47.92%
DRoC (Ours)
45.83%
20.83%
the previously generated code by incorporating insights from external documents. In addition to the RAG processes, the self-debugging operation also be introduced if the LLM thinks the error be fixed by itself. This dynamic routing process ensures a more flexible and adaptive framework, improving the likelihood of generating accurate solutions for complex problems.
The prompts for all components in our framework are provided in Appendix A. including the first-time generator, router, self-debugger, decomposer, filters, retrieval -aggeeted generator, and retrieval-augmennt debugger. These prompts detail the instructions given to the LLM in the pipeline.
5 EXPERIMENTS
To verify the effectiveness of DRoC, we conduct extensive experiments. We evaluate the DRoC and other baselines 48 VRPs variants by combining different constraints. These VRP variants and the corresponding dataset are elaborated in Appendix B In principle, the DRoC framework can work with any LLMs or optimization solvers. In our experiments, we mainly use ChatGPT (gpt-4o-2024-08 400-4-00---0-006 and ept-3.5-turbo-011 -0155 as the chosen LLM and OR-tools as the optimization solver. In addition, we provide experimental studies on other proprietary and open-source LLMs (i.e., claude3.5 and Ilama3. I), and another widely used solver (i.e., Gurobi), to show the generalizability. set the number of retrieved documents k and the number attempts = 4. The same values for l and I are used across all baselines to ensure fair comparison. The best result among independent runs is reported for all the methods. We use the following two performance metrics:
Accuracy Rate (AR): This metric defined as AR = V, x 100%, where V the total V.
number of generated programs for different VRP variants, and V. represents the number of successful programs that result in the optimal solution for given VRP variant.
Runtime Error Rate (RER): This metric defined as RER V, 100%. where V. V.
indicates the number of program that encounter runtime errors, representing the proportion of generated programs experiencing execution errors stemming from internal logical errors because of incorrect calls of solver APIs or syntax errors.
5.1 BASELINES
We benchmark DRoC against baselines in the main results: Standard Prompting, Chain-of-Thouug (Wei et al. 2022), Progressive-Hint Prompting (PHP) (Zheng et al., (023). Self-debug (Chen et al.) 2024). Vanilla RAG (VRAG), and Self-RAG (Asai al. 2022). In addition, compare DRoC with two recent works, Evolution of Heuristics (EoH) (Liu et al. (024) and Reflective Evolution (ReEvo)
evolutionary computation. We name them LLM+EC methods. More details of the baselines are elaborated in Appendix C Our code and
Ye et al., 2024), which LLMs to improve heuristics
data are publicly available at /https:: // thub. Com/Summer 42857/DRoC
5.2 OVERALL PERFORMANCE
Table
Table/[ppret presents the performance of the proposed DRoC and baselines in terms of AR and RER. The results show that although applying a more powerful LLM (i.e., gpt-4o) does improve the performance of all tested methods, all 6 baselines were able to produce successful programs only for less than 40%
7

---

Published as a conference paper at ICLR 2025
Stardard
Sta idard Prompting
70-
60
58,38 33
Burtina Ent Ratel
50
47.52
27.08
40
20.50
20.83
30
27.08
12.50
10-
024-3.5.uubb
G3K-0
diuded.5 sonter lama5.1-706
gps-3.5-uubo
9pK-4o
(a)
Figure 3: Performance of DRoC and Standard Prompting with different LLMs: (a) AR metric (b) RER metric. The DRoC applicable to varied LLMs, showing clear performance enhancements.
of tested VRP variants. This demonstrates the difficulty in solving complex NP-hard problems for SOTA LLMs. We observe that the methods that either rely solely on the internal knowledge LLMs (i.e., Standard Prompting, CoT,, and PHP) or only combine execution feedback (i.e., Self-debug) do not result in good performance. Meanwhile, the performance boost from VRAG and Self-RAG is minimal, and VRAG can actually lead to performance degradation (for gpt-3.5-turbo) suggesting that inappropriate or ineffective retrieval methods fail to provide significant assistance solving VRPs.
In comparison, the proposed approach achieves the best results in both generating correct programs and reducing runtime errors. Compared to the standard prompting approach, DRoC successfully solves 25% more VRP variants by gpt-4o. Moreover, produces more generation of error-free programs. For solutions that do not have rumning errors but are not optimal, they may miss some of the constraints, and human coder illustrative results of the generated solutions are provided in Appendix DJ where we present visual plots of the solutions for various VRP instances. Additionally, correct API-calling code generated before and after applying our method. DRoC also demonstrates applicability other OR problems, such as the assignment and facility location problems, which we discuss in detail in Appendix E This highlights the need for more refined retrieval techniques and integration strategies, as DRoC, for tackling complex moblem-solving scenarios.
further improve them without building from scratch. More
also compare the incorrect and
Meanwhile, we report the running time of the generated programs in Appendix F and find that DRoC does not lead any significant increase in running time of the problem-sol process.
5.3 EVALUATION WITH DIFFERENT LLMS
To demonstrate that the DRoC is general tool for enhancing VRP-solving capabilities with LLMs, we also evaluate its performance with the other two LLMs: Blaude-3.55 3.55-sonnet-22222 connet-2024102 1022 and Ilama3. 1- 70b. The results presented in Figure 3 We observe that even advanced LLMs, such gpt-4o and 3.5dl-3,--sonett, still struggle to correctly solve VRPs. However, the proposed DRoC consistently improves the performance of various LLMs, indicating that DRoC can function generic tool to enhance the VRP-solving abilities of LLMs in spite of their different architectures.
5.4 EVALUATION WITH GUROBI SOLVER
We show DRoC can embed different optimization solvers such as the popular Gurobi solver. Different from OR-tools, which solves VRPs by simply calling the APIs, the use of Gurobi for solving particular VRP variant requires us to first build the corresponding Mixed-Integer Programming (MIP) model, making it a more difficult task. In the experiments, we use the programs of 10 VRP variants, which only contain 0 or additional constraint, as the external knowledge source, and allow the DRoC retrieve from these simple VRP solutions. We evaluate the performance advanced LLMs, i.e., gpt-4o and claude-3.5 remains effective when working with the Gurobi solver. While only VRPs with single constraint as external knowledge, the LLMs can accurately solve more VRP variants with more than constraint, indicating that complex tasks can be fulfilled by our decomposition- based method.
The results (see Table 2 show that DRoC
8

---

Published as a conference paper at ICLR 2025
Table 2: The performance evaluated Gurobi solver with and without DRoC.
LLM
AR
RER
gpt-4o (Standard Prompting)
2.08%
45.83%
Mlaude3.55-oome (Standard Prompting)
12.50%
52.08%
gpt-4o (DRoC)
31.25% %
25.00%
claude-3.5-sonnc (DRoC)
31.25%
37.50%
5.3 ABLATION STUDY
Table 3: The results of ablation studies.
OR-tool
Gurobi
Method
AR 1
RER
AR 7
RER +
DRoC (Full)
45.83% %
20.83%
31.25% %
25.00 %
w/o filter
37.50%
31.25%
27.08%
27.08%
w/o DR
35.42%
29.17%
27.08%
29.17%
w/o router
43.75%
29.17%
29.17%
31.25%
We conduct ablation studies for both OR-tools and Gurobi for a more comprehensive comparison. The studies are based gpt-4o, which has showcased good performance under different settings.
Ablation study on two-stage filter. We first evaluate the necessity of the filter process, which refines the retrieved documents and reduces extraneous information. As shown in Table 3 we observe slight drop in model performance when potentially irrelevant documents are not filtered out. This outcome is similar to the poorer performance observed with VRAG shown in Table T suggesting that the relevance of the context provided during generation significantly impacts the results. The filter ensures that pertinent information is used, which is crucial for optimizing VRP-solving effectiveness.
Ablation study on decomposed retrieval (DR). In order to evaluate the necessity of DR, we replace by direct retrieval of documents, which takes "Python code of [the name of the VRP)" as the query, aiming at retrieving code that mostly close to the target VRP variant. This replacement is applied whenever the retriever is called, and the final context obtained by randomly choosing from top-k retrieved documents. Similarly, there is also performance drop for both OR-tools and Gurobi, suggesting that LLM can learn to solve complex VRPs from single-constraint resolutions in the DR.
Ablation study on router. We replace the router with random routing strategy. which randomly routes the workflow the self-debugger or retrieval retrieval-augmentte augmented debugger. There also slight drop in performance without the proposed router, indicating that the selection between execution-baal and documentation-basse external knowledge important.
5.6 COMPARISON WITH LLM+EC METHODS
LLMs can be used to evolve heuristics for solving VRPs, as shown in the literature. We conducted ex- periments to find out how such an approach performs in comparison to our approach which based on VRP solvers. We take the Prize Collecting Travel- ling Salesman Problem (PCTSP) as demonstration problem, which ChatGPT cannot originally solve due to the incorrect calls of solver API (see Ap- pendix D). to conduct comparison study between SOTA LLM+EC methods and the proposed DRoC.
EoH
Token usage of DRoC DRoc
Objective value
25
20
We utilize EoH and ReEvo to evolve the ant colony al- gorithm, as detailed Ye et al., 2024), and compare the results of these evolutionary approaches. Specif- ically, we record both the best objective values and the number of tokens consumed by the L.LM for EoH
200000 Accumulated number of tokens
Figure 4: Comparison between LLM+EC
methods (EoH and ReEvo) and DRoC.

---

Published as a conference paper at ICLR 2025
and ReEvo during iteration- based evolution. As shown in Figure compared to DRoC, the LLM+EC methods require a substantial number of tokens (e.g., over IM) to evolve towards a solution which significantly increases computational costs and potential carbon emissions. Notably, the best heuris- ties for EoH and ReEvo achieve objective values of 6,436 and 6.984, respectively, while DRoC with OR-tools yield superior result of 6.352. The findings suggest that DRoC framework is more efficient and competitive than EC methods, providing greater enhancement of the LLM.
5.7 SENSITIVITY ANALYSIS
50-
50-
46-
46-
Pannino Srr Ross D6
Accuaag Rata (50
46-
40-
55
Buntira
15
15
36
36-
0.5
1.0
(a)
(b)
(c)
Figure 5: The results for sensitivity analysis on (a) /; (b) k; (c) temperature.
We study how three key parameters influence the performance of DRoC: the maximum number of generation J, the number of retrieved documents k, and the temperature of the LLM. The analysis is also based on gpt-4o, and the results are shown in Figure 5
Sensitivity analysis on I. The performance of DRoC generally improves with the increase of I, but the improvement turns marginal from to Therefore we set across all our main experiments.
Sensitivity analysis on k. The value of & has less influence than 7. The performance is slightly improved when varying from I to 3, mainly because more comprehensive contents are retrieved with a larger k. After that, the performance tends to be stable because the generation context is relatively unchanged since redundant documents are filtered out by the two-stage filter process.
Sensitivity analysis on temperature. The performance of DRoC remains relatively stable across different temperature parameters. This indicates that the combination of iterative refinement and tar- geted document selection helps maintain consistent results, regardless of variations in the randomness of generation influenced by the temperature configuration.
5.8 BOOTSTRAP-BASED OPTIMIZATION
As the LLMs can solve more problems utilizing external knowledge, they can also take the correct generation as part of the external knowledge, making it possible to improve the performance through Bootstrap. We also analyze the impact of such Bootstrap mechanism and find that the integration of LLM generations and original external knowledge (publicly accessible documentation and codes) can also boost the accuracy to some extent. The details and result are elaborated in Appendix G and we find that more than 50% VRP variants can be resolved after introducing the Bootstrap mechanism.
6 CONCLUSIONS
In this paper, we propose DRoC, an effective framework designed for solving VRPs with complex constraints, utilizing LLMSs and optimization solvers. By integrating external knowledge through -ugmenttd generation and decomposing constraints for more accurate retrieval, the DRoC significantly improves LLM performance across a wide range VRP variants. For instance, improves the accuracy rate of gpt-4o from 20.83% to 45.83%. In the future, we plan to expand our focus to integrate the DRoC with solver selection and metaheuristic generation processes, enhancing the versatility and reliability in addressing more diverse optimization tasks. We will also introduce more external knowledge sources for better RAG performance and integrate modeling function into framework, further boosting its effectiveness.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Ali AhmadiTeeshizzi Wenzhi Gao, and Madeleine Udell. OptiMUS: Scalable optimization modeling with (MI)PP solvers and large language models. In Forty-first International Conference on Machine Learning, 2024.
Guilherme F.C.F. Almeida, José Luiz Nunes, Neele Engelmann, Alex Wiegmann, and Marcelo de Araújo. Exploring the psychology of Iims' moral and legal reasoning. Artificial Intelligence, 333:104145, 2024.
Akari Asai, Zeqiu Wu, Yizhong Wang, Avirup Sil, and Hannaneh Hajishirzi. Self-RAG: Learning to retrieve, generate, and critique through self-reftection. In The Twelfth International Conference on Learning Representations, 2024.
Kris Brackers, Katrien Ramaekers, and Inneke Van Nieuwenhuyse. The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 99:300-313, 2016.
Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. Teaching large language models to self-debug. The Twelfth International Conference on Learning Representations, 2024.
Raafat Elshaer and Hadeer Awad. A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants. Computers & Industrial Engineering, 140: 106242, 2020.
Vincent Furnon and Laurent Perron. Or-tools routing library, 2024.
Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yi Dai, Jiawei Sun, and Haofen Wang. -etreetelaugmmente generation for large language models: A survey. arXiv preprint arXiv:2312 10997, 2023.
Yong Liang Goh, Zhiguang Cao, Yining Ma, Yanfei Dong, Mohammed Haroon Dupty, and Wee Sun Lee. Hierarchical neural constructive solver for real-world tsp scenarios. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 884-895, 2024.
Gurobi. Gurobi Optimizer Reference Manual, 2024.
André Hottung, Bhanu Bhandari, and Kevin Tiemey. Learning latent search space for routing problems using variational autoencoders. In International Conference on Learning Representations, 2021.
Zhehui Huang, Guangyao Shi, and Gaurav S. Sukhatme. Can large language models solve robot routing? arXiv preprint 4rXiv:2403.10795, 2024.
Xia Jiang, Yaoxin Wu, Yuan Wang. and Yingqian Zhang. Unco: Towards unifying neural combinato- rial optimization through large language model. arXiv preprint arXiv:2408.122 12214, 2024.
Zhengbao Jiang, Frank Xu, Luyu Gao, Zhiqing Sun, Qian Liu, Jane Dwivedi-YY Yu, Yiming Yang, Jamie Callan, and Graham Neubig. Active retrieval augmented generation. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 7969-7992, December 2023.
Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-neo: Leveraging symmetricity for neural combinatorial optimization. In S. Koyejo. S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances Neural Information Processing Systems, volume 35, pp. 1936-1949 2022.
Wouter Kool, Herke van Hoof, and Max Welling, Attention, learn to solve routing problems! In International Conference Learning Representations, 2019,
Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler. Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. -euteeeal-uugmenteed generation for knowledge inteedege-netniveeeeeeee nlp tasks. In Advances Neural Information Processing Systems, volume 33, pp. 9459-94744 2020.
11

---

Published as a conference paper at ICLR 2025
Fei Liu, Tong Xialiang, Mingxuan Yuan, Xi Lin, Fu Luo, Zhenkun Wang, Zhichao Lu, and Qingfu Zhang. Evolution of heuristics: Towards efficient automatic algorithm design using large language model. In Forty-first International Conference on Machine Learning. 2024.
Fu Luo, Xi Lin, Fei Liu. Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. In Advances in Neural Information Processing Systems, volume 36, pp. 8864, 2023.
Md Rizwan Parvez, Wasi Ahmad, Saikat Chakraborty, Baishakhi Ray, and Kai- Chang. Retrieval augmented code generation and summarization. In Findings of the Association for Computational Linguistics: EMNLP 2021, pp. 2719 2734, November 2021.
Aditya Pillai and Mohit Singh. Linear programming based reductions for multiple visit tsp and vehicle routing problems. arXiv preprint arXiv:2308. 11742, 2023.
Rindra Ramamonjison, Haley Li, Timothy Yu, Shiqi He, Vishnu Rengan, Amin Banitalebi- -cchkidrd- Zirui Zhou, and Yong Zhang. Augmenting operations research with auto-formulation of optimiza- tion models from problem descriptions. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing:
Industry Track, pp. 29-62, December 2022.
Weizhou Shen, Yingqi Gao, Canbin Huang, Fanqi Wan, Xiaojun Quan, and Wei Bi. Retrieval- generation alignment for end-to-end task task-oriented dialogue system. Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 8261-8275, December 2023.
Hongjin Su, Shuyang Jiang, Yuhang Lai, Haoyuan Wu, Boao Shi, Che Liu, Qian Liu, and Tao Yu. Arks: Active retrieval in knowledge soup for code generation. arXiv preprint 240iv:2402..23111 2024.
Zhengyang Tang, Chenyu Huang, Xin Zheng, Shixi Hu, Zizhuo Wang, Dongdong Ge, and Benyou Wang. Orlm: Training large language models for optimization modeling, arXiv preprint arXiv:2405. 17743, 2024.
Zhiruo Wang, Jun Araki, Zhengbao Jiang, Md Rizwan Parvez, and Graham Neubig. Learning to filter context for
generation. arXiv preprint arXiv:2311.0833 2023.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed Chi, Quoc V Le, and Denny Zhou. thain-off-thougle prompting elicits reasoning in large language models. In Advances in Neural Information Processing Systems, volume 35, pp. 24824-24837, 2022.
Yaoxin WU, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuristics for solving routing problems. IEEE transactions on neural networks and learning systems, 33(9): 5057-5069, 2021.
Ziyang Xiao, Dongxiang Zhang, Yangjun Wu, Lilin Xu, Yuan Jessica Wang, Xiongwei Han, Xiaojin Fu, Tao Zhong, Jia Zeng, Mingli Song, et al. Chain-of-experts: When ilms meet complex operations research problems. In The Twelfih International Conference on Learning Representations, 2023.
Haoran Ye, Jiarui Wang, Zhiguang Cao, Federico Berto, Chuanbo Hua, Hacyeon Kim, Jinkyoo Park, and Guojie Song. Large language models as hyper-heuristics for combinatorial optimization. In Advances in Neural Information Processing Systems, 2024.
Ori Yoran, Tomer Wolfson, Ori Ram, and Jonathan Berant. Making retrieval-augmente language models robust to irrelevant context. In The Twelfth International Conference on Learning Repre- sentations, 2024.
Fengji Zhang, Bei Chen, Yue Zhang, Jacky Keung, Jin Liu, Daoguang Zan, Yi Mao, Jian- Gunn-Gaan Lou, and Weizhu Chen. RepoCoder: Repository- -leel code completion through iterative retrieval and generation. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 2471-2488 December 2023.
12

---

Published as a conference paper at ICLR 2025
Jihai Zhang, Wei Wang, Siyan Guo, Li Wang, Fangquan Lin, Cheng Yang, and Wotao Yin. Solv- ing general natural- languagg-dessciiiion optimization problems with large language models. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Compu- tational Linguisticss, pp. 483-490, June 2024a.
Yizhou Zhang, Lun Du, Defu Cao, Qiang Fu, and Yan Liu. An examination on the effectiveness of -ouccuu prompting in large language models. arXiv preprint arXIv:2402.05359, 2024b.
Chuanyang Zheng. Zhengying Liu, Enze Xie, Zhenguo Li, and Yu Li, Progressive-hie prompting improves reasoning in large language models, 2023.
Jianan Zhou, Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Towards omni-generalizable neural methods for vehicle routing problems. In Proceedings of the 40th International Conference Machine Learning, volume 202, pp. 42769 47779947779,,. 23 Jul 2023a.
Shuyan Zhou, Uri Alon, Frank Xu, Zhengbao Jiang, and Graham Neubig. Docprompting: Gen- crating code by retrieving the docs. In The Eleventh International Conference on Learning Representations, 2023b.
13

---

Published as a conference paper at ICLR 2025
A PROMPT AND OUTPUT TEMPLATES
A.1 PROMPTS
Table 4: The prompts skeleton for each DRoC component
Component
Prompt Skeleton
First-time gen-
You are an expert in Python programming for operations research. You are very good calling solver in Python and solving problems.
erator
Respond with the syntactically correct code for solving problem using solver.
Make sure you follow these rules:
1. Read the template. First understand the meaning of the parameters in 'solve' function, and then complete the code inside the function.
2. Ensure all parameters in the template are used in the function.
3. Do not give additional examples or define main function for testing.
4. Return the objective value of the problem by the 'solve' function.
5. Ensure any code you provide can be executed with all required imports and variables defined. Template:
Structure your answer with description of the code solution, and then list the imports, and finally list the functioning code block.
Router
Your task is to determine how to refine the incorrect Python code, which is produced by another programmer.
Here is the code: <prep_codee code>
The code is about solving problem based solver, and there is the error information while running the code:
Error message: <message>
There are several tools that can be called, which can be one of the following: (1) Larrraaaaaammeee__deee _aggaanntedddeubuliinnu Retrieve code examples from repos- itory, and then refine the current program drawing upon the retrieved codes. Prioritize it when the error is caused by incorrect use of solver API. (2) self debug[input]: Call a pretrained LLM like yourself. Prioritize it when you are confident in fixing the error yourself, e.g., when the error of the code is caused by syntax error or wrong import. Return "1" if you think you should use tool (1), otherwise return "2". Do not return other things.
Self-debugger
You are an expert in Python programming for operations research by calling solver. Now your responsibility is to debug the code snippet with errors.
The code snippet with bug is as <prep_ code>. Here is the eтror message of the code: <message>. You can first reason about the error, and finally refine the code and return the whole fixed function. Ensure any code you provide can be executed with all required imports and variables defined. Remember, the final solution should be returned by the 'solve' function. Do not use other name for the function and do not give example usage of the function. Structure the refined solution by firstly giving the reason of the error and the strategy for fixing it. Then list the imports. Finally list the functioning code block and solve the problem with 'solve' function.
Decomposer
You will extract the keywords of a vehicle routing problem (VRP) for me. give you the name of a VRP and you produce the keywords according its constraints. Structure your answer with list of keywords inside "<> and use commas to separate different keywords. Do not return other things.
For example, the output of "Capacitated Vehicle Routing Problem with Time Windows and Multiple Depots (CVRPTWMD)" should <Capacitated, Time Windows, Multiple Depots>, and the output of "Prize Collecting Travelling Salesman Problem (PCTSP)" should be <Prize Collecting?.
14

---

Published as a conference paper at ICLR 2025
First-stage fil-
You are an expert in Python programming and solver for vehicle routing prob- lem.
ter
will give you a retrieved documents potentially related to keyword, and you will firstly assess if the document includes Python code program keyword. If so, you should explain how the code addresses the constraint of keyword. Here is the retrieved document: {context]
If the document contains Python code related to keyword, grade it as relevant, After that, extract the code snippet in the document related to keyword. Finally, produce an explanation on how to program the constraint of keyword, and your goal is to make other programmers know how to do that. Structure your answer with the binary score 'yes' or "no' to indicate whether the document relevant, and then list the related code snippet, and finally give the summary. the document is not related, just return 'no' for the binary score, and nothing for the code snippet and the summary.
Second-stage filter
You are an expert in Python programming and solver for vehicle routing problem (VRP).
I will give you several retrieved documents (codes) and their explanations potentially related to keyword, and you should assess which context is the most relevant one and with minimal redundant information.
Here are the documents, which are separated by" [contexts]
Return the index of the most relevant document and do not return anything else. For example, if you think the second document is the most relevant one, just return 2. Please strictly return integer index following the above instruction. You are an expert in Python programming for operations research and combi- natorial optimization. You are good at calling <solver> in Python and solving problems.
Retrieval- augmented generator
Respond with the syntactically correct code for solving problem using solver. Make sure you follow these rules: 1. Read the template. First understand the meaning of the parameters in 'solve' function, and then complete the code inside the function.
2. The context provides example codes of addressing each constraint of (prob- lem) by (solver). Learn to model each constraint and solve the problem accordingly.
3. Do not give additional examples or define main function for testing. 4. Return the objective value of the problem by the 'solve' function. 5. Ensure any code you provide can be executed with all required imports and variables defined. Template: }
Context: [context)
Structure your answer with a description of the code solution, and then list the imports, and finally list the functioning code block.
Retrieval- augmented dubugger
You are responsible for refining the code with errors, which tries to solve problem by calling solver in Python.
The code snippet with the bug is as <prep_code>. Here is the error message of the code: <message>.
Make sure you follow these rules: 1. You can first reason about the error, and then refine the code and return the whole fixed function.
2. The context provides examples of solving problems with different constraints, referring to the relevant parts and modifying the code accordingly: <context>.
3. Do not give additional examples or define the main function for testing.
4. Return the objective value of the problem by the 'solve' function.
5. Ensure any code you provide can be executed with all required imports and variables defined.
Structure your answer with description of the code solution, then list the imports, and finally list the functioning code block.
15

---

Published as a conference paper at ICLR 2025
A.2 OUTPUT EXAMPLE OF THE FILTER
relevance="yes"
snide_="ipet="" Add Capacity constraint\n
def mamand_callbacke (ffrm_index)::::
# Convert from routing variable Index to demands NodeIndex \n from_node = manager. IndeeToood (from_index) \n return demandssfrron_nodee]vk.
Register the demand callback with the routing model
demand_callback_index routing Reiisteruuarrrrrrstttcaaaaaa demand_callback)11
routing
demand_callback_indee
0, # null capacity slack\n
vehiccl__caaciities,
vehicle maximum capacities True, start 'Capacity")",
cumul to zero
summary="To program the Capacitated constraint in the Capacitated Vehicle Routing Problem with Distance Limit (CVRPL) using OR-tools in Python, you need to define demand callback function that maps the routing variable Index demands NodeIndex. This function is registered as a unary transit callback with the routing model. Then, the capacity constraint is added using the www.mmmmooooitteeiclll......
method, specifying the demand callback index, null capacity slack, vehicle maximum capacities, start cumul zero, and the dimension name 'Capacity'. This ensures that the vehicle capacities are respected during the routing optimization process."
Figure 6: The example of the output of the first-stage filter.
B VRP VARIANTS
def solve Solleetime_matteee matrix: list, time_winde windwwinsw:: list, demands: list, vehicle capaciieep: list, num_vehicles: int, starts: list, ends: list):
Args:
time_matrix: contains the integer travel times between locations time_windows the list of tuples for time windows of the customers
demands: the list of integer customer demands vehicle_capacities: the capacity of each vehicle jum_vehicles, the number starts: the index of the starting depots for vehicles ends: the index of the ending depots for vehicles
the vehicle
Returns:
obj: a number representing the objective value of the solution
obj = -1
return obj
Figure 7: Function template of CVRPTWMD.
As mentioned in Section 3.1 there are several common additional constraints for the VRP, and we create VRP variants by combining different constraints, for which is shown in Table Due to the high complexity of VRPs, designing numerous large instances with feasible solutions challenging. Therefore, we use carefully crafted, simple instance for each VRP variant, developed by human experts. This approach ensures the feasibility of each instance and provides the dataset for evaluating the performance of various baselines alongside our proposed method, DRoC. The ground truth for the optimal solutions of the instances is primarily obtained using Hybrid Genetic Search (HGS) (Wouda
16

---

Published as a conference paper at ICLR 2025
et al. 2024), which is widely recognized as method for calculating approximate optimal solutions for VRPs. For VRP variants with constraints of "Pickup and Delivery" or "Resource Constraints, we utilize OR-Tools with search time limit of 100 seconds to determine their ground truth, the used HGS solver does not support these specific constraints. To make the instances more informative, we randomly use distance matrix time matrix represent the graph of the VRP. Therefore, impose distance limits on those with distance matrix and duration limit on those with time matrix. Accordingly, create 48 unique VRP variants, each paired with specific instances, forming benchmark dataset for evaluation. A program is deemed correct when its generated solve function yields the same value as the optimal solution. Additionally, such correct programs can generalize to any VRP instance sharing the same constraint structure, regardless of input parameters (e.g.. customer coordinates).
Different from previous studies (Zhang et al., 2024 Huang et al. 2024), which try to solve OR problems with natural language description, we just take the name of the problem and the function signature as input. We take the function signature of the CVRPTWMD as example, which is
shown in Figure 7
In this case, the LLM needs to try to understand the meaning of each parameter and generate programs accordingly. Once a program for a VRP variant is produced successfully, it can be used in all instances of the same VRP. Compared to natural language-base based description, which specifies the data of the problem, this method is more generalizable.
C BASELINES
In this section, we elaborate on the implementations of the baselines involved in the experiments:
Standard Prompting: it refers to using the prompt skeleton the first-time generator in Section A. The generator is called up to I times independently without the injection of any external knowledge.
Chain-of-Thoughe similar to the CoT baseline in (Xiao et al., 2023), we add the sentence "Let's think step by step" in the standard prompting to guide the model's 's thought process, aiming using the internal knowledge of the LLMs for reasoning as much as possible.
Progressive-Hit Prompting: similar the PHP baseline in (Xiao al. 2023). we produce an initial program and then use previous generations as hints to progressively guide the LLM toward the correct solutions. It fulfilled by verifying if the current response the same as the previous one.
Self-debug: it is based on the method proposed by Chen et al. (2024), using the error information and corresponding traceback produced by the executor to teach the L.M conduct debug without any human feedback on the code correctness. Specifically, it follows the prompt of the self-debugger in Section A.I The number of generations is also up
The VRAG approach retrieves relevant context before each round of program genera- tion. In the first iteration, the query set as "Python code of the name of the VRP." " For subsequent iterations, the query consists of the generated code from the previous iteration to retrieve the most relevant documents. During program generation, the top-k retrieved documents are included as part of the input to guide the model in generating more accurate solution.
Vanilla RAG:
Self-RAG: Originally proposed by Asai et al. (004)), we adapt Self-RAG to the VRP tasks. Similar to VRAG, a retriever is used to obtain relevant documents, followed by relevance grader to assess whether each retrieved document pertinent to the target VRP. We implement this process using the first-stage filtering mechanism from our DRoC framework. The remaining relevant documents are then used in parallel to generate solutions. Each generated program executed until one can run successfully. Additionally, the code generated in previous iterations is used as query for further retrieval, continuing until the maximum number of generations 1 is reached.
EoH: EoH evolves the codes of heuristics by diverse prompt strategies. We basically follow the configuration in the original paper (Liu et al. (024). We use 30 populations at the initial stage and 10 populations for each iteration. We allow for most 300 times of evaluations the PCTSP instances.
ReEvo: ReEvo uses the reflection mechanism to progressively evolve the heuristics. We follow the default settings in Ye al. (2024) with also up 300 evaluations on the instances.
17

---

Published as a conference paper at ICLR 2025
Table 5: The studied 48 VRP variants with nine additional constraints.
Vehicle
Distance
Time
Multiple Depots
Open Route
Prize
Pickup and Delivery
Service Time
Resouree Constraint
Capacity
Limit
Window
Collecting
TSP
TSPTW
TSPTWS
VRP
VRPL
VRPMD
VRPS
VRPSL
VRPTW
VRPTWL
VRPTWMD
VRPTWS
VRPTWMDL
VRPTWSL
VRPTWMRC
VRPTWMRCI.
CVRP
CVRPL
CVRPTW
CVRPMD
CVRPTWL
CVRPMDLL
CVRPTWMD
CVRPTWMDL
CVRPTWRC
CVRPTWRCL
PCTSP
PCTSPTW
PCVRP
PCVRPTW
PCVRPMD
PCVRPTWMD
OVRP
OVRPL
OVRPTW
OCVRP
OCVRPL
OCVRPTW
PDP
PDPL
PDPTW
PDPMD
PDPTWL
PDPTWMD
PDPSL.
PDPTWS
PDPTWSL
PDPTWMDL
For the comparison study of EoH and ReEvo, The evolution is conducted on PCTSP instances with 50 nodes, which are randomly sampled from a unit square. Let the distance between node and the depot be d, and dmmax (d)) the prize of node is set to prize, mmxx. where di The penalty values for unvisited nodes are set the same the prizes.
1+ [99-r]
Tmuxx
D GENERATED SOLUTIONS
We present several examples of solutions that DRoC method can achieve, which the standard approach fails to generate, as illustrated in Figure These VRPs often involve multiple constraints that pose significant challenges for LLMs to address effectively.
We use gpt-4o to invoke OR-tools for solving VRPs with the Prize Collecting constraint. The primary distinction between the Standard Prompting and DRoC methods lies in how they handle the constraint, with the former failing to produce a correct solution, while the latter succeeds. As shown in Figure 9 the programming approaches for the Prize Collecting constraint differ significantly. DRoC enables
18

---

Published as a conference paper at ICLR 2025
Disst
Custorer
Ieficke
Vilidee Dopot Castome
Vehide
VCoertrain
Depet
VCoertpan
Tonntran
D.ortinute
Coorsirate
(a)
(b)
(c)
(d)
Figure 8: Example solutions generated by DRoC. (a) CVRPTWRC solved by OR-tools; (b) PCVRP solved by OR-tools; (c) CVRPMD solved by Gurobi; (4) VRPTWL solved by Gurobi.
vehicles to drop nodes, effectively accommodating the constraint. In contrast, the standard method produces meaningless content, leading to hallucinations during the generation.
Define the prize collection callback
def prize_cal www.calllacckkkccc (artecccalaaccffoo_iiiiiii (frorfffooooeeee
from_node manager Index (from_index) return prizes[from_nodd pr zee_callback_index routing. ott.rrdeeeetttoooonogggeeeeereee ttt.sgisseeeuuurrrtrtatttaallll
prize_callback)
routing AdbDinensssooittiiiiiceeeecpppp
prize_ caazze_allback_ideex,
e, no slack
[sum(prizes) num_vehicle, vehicle maximum prize capacity True, start cumul to zero 'Prize')
Setting objective to maximize the prize collection priieeddienssieee = routing.GetDiment GetDimensionOrDie PPizze') for vehicle_id in range (wwm_ vehicle): routing SetFixed SefFixedCotoovehicle. ( (-seeessssuspmm sumppizes), vehicle_id)
Generated code snippet by Standard Prompting, (Incorrect)
Allow to drop nodes. for node in range len [diistance_matrix. routing, jjunct ([ ([manager.. NodeToInder ndex (node)], pri zrs [node]]
Generated code snippet by DRoC. (Correct)
Figure Comparison of code snippets for Prize Collecting constraint.
E APPLICATION TO OTHER OR PROBLEM
Many real-world OR problems possess composite constraints, and thus these in which our methods can be applied. In order to show the applicability of the proposed DRoC to other OR problems, we take the assignment problem and facility location problems as the examples, which are both fundamental combinatorial optimization problems.
E ASSIGNMENT PROBLEM
We focus on the scenario of worker assignment problem: Given assignment costs for each worker-tast pair, need allocate workers to distinct tasks that each worker is assigned to and at most one task and the total cost is minimized. The following additional constraints are considered: I) Teams of Workers: the workers divided into several teams, and each team perform most
19

---

Published as a conference paper at ICLR 2025
tasks, where is parameter; 2) Task sizes: Each task is assigned size indicating the necessary time or effort, and the total size tasks allocated to each worker is restricted by a fixed limit.
Define constraints for in range (num_ solver. Anwverr.ddd(eee Adu (x[i, j] for range (num_workers)) task_sizes[j])
for i in (nuneennu_wwrkee
solver, Add (x[i, i] for j in range Lenummtassss <= team _ax)
solver, Add sum (x[i, j] task_sizes [j] for j range (num_ tasks)) <= size_max)
(a) Generated code snippet by Standard Prompting. (Incorrect)
Each worker is assigned to at most one task. for worker range mnum_wrrkers)
model. Add
sum Saaassssizeestaaa * x[worker, task] for task in range num_tasks)) <= size_mar max
Each task is assigned to exactly one worker. for task in range mrum_tasks): A AddExactlyoe (x[worker, task] for worker in range (num (um_workers))
Each team takes at most team_max tasks.
for team in worker_teams:
team_tasks []
for worker team:
for task in range (num_tasks)
team_ append (x[worker, task])
model Add (sum (team_tasks) <= team_max)
(b) Generated code snippet by DRoC. (Correet)
Figure 10: Comparison of code snippets for the worker assignment problem.
We consider the worker assignment problem with both constraints of Teams of Workers and Task sizes. We also use the OR-Tools to solve it. The way that gpt-3.5-turbo handles the constraints is shown as Figure 10 (a), while the code snippet of DRoC is shown in Figure (b). We find that the LLM without DRoC neither groups workers effectively nor assigns the correct number of worker for the tasks. In comparison, method generates the program by modeling the constraints correctly.
E.2 FACILITY LOCATION PROBLEM
The Facility Location Problem (FLP) encompasses optimization tasks aimed at selecting optimal sites for facilities minimize the conveying cost from facilities eustomers. FLPs may include constraints such as facility capacity. Various real-world scenarios present different optimization objectives for FLPs, leading distinct problem variants, such as: p-median: minimizing the total distance from each customer to their nearest facility; 2) p-center: minimizing the maximum cost any customer must spend reach the nearest facility: 3) p-maxian: maximizing the total weighted travel cost incurred by all customers; 4) p-dispersion: maximizing the smallest distance between any pair of facilities. These objectives necessitate additional constraints during the modeling. Hence, we explore the integration of capacity constraints with these objectives and assess the performance of DRoC on these FLP variants. We take part the codes implemented by (Gaboardi (2015) as the external knowledge and use Gurobi to model and solve the FLP variants.
Table 6 illustrates that DRoC facilitates the resolution of more FLP variants, including some not encompassed by external knowledge. In partieular, DRoC augmentation empowers 3pt-3.5-turbo to successfully tackle five additional problem variants, while the standard g.t-3.5-tume exhibits very limited proficiency in solving FL.Ps.
20

---

Published as a conference paper at ICLR 2025
Table 6: The evaluation results on the FLPs.
Solved by gpt-3.5-turbo (DRoC)
Contained in the external knowledge
Solved gpt-3.5-turbo
Solved by gpt-4o
Solved by gpt-4o (DRoC)
p-median FLP
p-center FLP p-maxian FLP p-dispersion FLP
<
Capacitated FLP
Capacitated p-median FL.P
X
Capacitated p-center
Capacituted p-maxian FLP
X
Capacitated p-dispersion FLP
X
F RUNNING TIME OF THE GENERATED CODE
Table 7: Comparison of running time
Method
Mean Time (s)
Std Time (s)
Mean Log Ratio
Std Log Ratio
HGS
1.005
0.003
DRoC (HGS)
0.329
0.713
-3.257
0.317
OR-Tools
12,503
32.379
DRoC (ools) 1.411
4.059
-1.145
0,882
We also explore the rumning time of the generated programs and check if the LLM produce code with extended compuation time duration. In our implementations, we used the HGS solver for obtaining optimal solutions and OR-Tools in our RAG framework, respectively. Specifically, the running time for the HGS solver is supposed to be configured, which serves as the stopping condition for the search process. We set maximum run time of second for HGS, as we found it is sufficient to obtain optimal solutions for the simple instances used in our evaluation. For the OR- Tools solver, we set the search time limit 100s, it has early stop mechanism once there is solution improvement. The statistics for running time are shown Table 7 Note that we calculate the running time of DRoC for instances solvable by HGS [denoted DRoC (RGC(H and those solvable by OR-Tools [denoted as DRoC (OR-Tools)], respectively.
The results empirically show that the mean and standard deviation of the running time for DRoC (OR-Tools) are smaller than those of directly calling OR-Tools. This is mainly because the search limit parameter
configured for most of the instances in the programs generated by DRoC, while we predetermine the search limit for OR- OR-Tools when calculating the approximated optimal solutions. When we set the same time limit for both OR-Tools and DRoC (OR-Tools), the time metrics can be nearly identical (with a mean log ratio of 0.004). This is intuitive, the generated code produced by DRoC maintains similar structure to manually written code for solving specific VRPs. Thus, DRoC does not introduce any significant increase in running time, while it provides automatic and user-friendly approach to solve the problems.
G ROOTSTRAP-BASER OPTIMIZATION
We have introduced DRoC using static external knowledge sources. However, as LLMs, powered by DRoC, begin generating more accurate solutions, we can dynamically update the external knowledge by incorporating these generated solutions. Specifically, we first solve all solvable VRP variants using the statie DRoC approach, and subsequently embed all the generated programs, which have been executed successfully. to the knowledge base. We create a new retriever for these LLM L.MM-genertee solutions and ensemble it with the retriever other knowledge. Following this, we initiate new round of generation aimed at solving the previously unsolved problems. By leveraging the solutions generated by the LLMs, we enhance the model's performance a Bootstrap based manner, process term DRoC with Bootstrap- based optimization (ORoC-BBO), This iterative approach allows the LLM to improve progressively by utilizing its own outputs as external knowledge, thereby improving its problem-solving capabilities successive iterations.
21

---

Published as a conference paper at ICLR 2025
52
Accuracy Rate (%)
51
20.5
50
Runtiime Enrr Rote
20.0
metric
49
RER metric
19.5
19.0
Round of Generation
Figure 11: Performance of the DRoC-BBO.
Experimentally, the DRoC-BBO can slightly improve the performance with more rounds of generation with updated knowledge sources, which is shown in Figure [1] This indicates that the LLMs can also be enhanced through Bootstrap for solving optimization problems like VRP.
REFERENCES
Akari Asai, Zeqiu Wu, Yizhong Wang, Avirup Sil, and Hannaneh Hajishirzi. Self-RAG: Learning to retrieve, generate, and critique through self-reflection. The Twelfth International Conference on Learning Representations, 2024.
Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. Teaching large language models to self-debug. The Twelfth International Conference on Learning Representations, 2024.
James
Gaboardi.
Facility location
location
allocation.
https://gituub.com/fffaa hotph//hchoommabbbbrraaaiitttttt Loctrrdtiiiiiittyyooooooooooooo
Location, 2015.
Zhehui Huang,
Guangyao Shi, and Gaurav Sukhatme. From words to routes: Applying large language models to vehicle routing, arXiv preprint arXiv:2403. 2024.
Fei Liu, Tong Xialiang, Mingxuan Yuan, Xi Lin, Fu Luo. Zhenkun Wang. Zhichao Lu, and Qingfu Zhang. Evolution of heuristics: Towards efficient automatic algorithm design using large language model. In Forty-first first International Conference Machine Learning. 2024.
Niels A. Wouda, Leon Lan, and Wouter Kool. Pyvrp: A high-performance vrp solver package. INFORMS Journal on Computing, 36(4):943-955, 2024.
Ziyang Xiao, Dongxiang Zhang, Yangjun Wu, Lilin Xu, Yuan Jessica Wang, Xiongwei Han, Xiaojin Fu, Tao Zhong, Jia Zeng, Mingli Song, et al. Chain-of-experts When lims meet complex operations research problems. In The Twelfth International Conference on Learning Representations, 2023.
Haoran Ye, Jiarui Wang, Zhiguang Cao, Federico Berto, Chuanbo Hua, Haeyeon Kim, Jinkyoo Park, and Guojie Song. Large language models as hyper-heuristics for combinatorial optimization. In Advances in Neural Information Processing Systems, 2024.
Jihai Zhang, Wei Wang. Siyan Guo, Li Wang, Fangquan Lin, Cheng Yang, and Wotao Yin. Solv- ing general natural-language- language-descrrption optimization problems with large language models. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Compu- tational Linguisticss, pp. 483 383-490, June 2024.
22


Reviews:
[{"review_id": "ZEBgTP5uhw", "reviewer": "Reviewer_i3uy", "summary": "This work is along the popular direction of using LLM to automatically generate modeling code and then call solvers in the backend to solve the problem. Specifically, it proposes a novel framework that enhances LLMs in code generation to solve complex vehicle routing problems (VRPs) with intricate constraints. Traditional LLMs perform well on simpler VRPs but struggle with complex versions due to a lack of embedded domain-specific knowledge. The proposed DRoC framework addresses this by using a retrieval-augmented generation (RAG) approach to incorporate external knowledge for constraint modeling.", "questions": "1. What happens if the given VRP variant cannot be solved by the solver?\n2. In the experiment, the authors use \"optimality gap\" as a criterion. Is the feasibility verified first? Otherwise we would have objective value that is not feasible, or even lower than the optimal value of that problem.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem is well motivated. It is important to be solve different variants of VRP problems. From the numerical results, it appears that with the proposed approach, the accuracy of modeling is improved substantially.", "weaknesses": "1. The RAG technique is common for code generation. What is the challenge of applying RAG in solving VRP? The novelty of this paper is limited.\n2. In practice, there are also other variants of VRP which cannot be solved immediately by the solvers. The paper does not address the case where the problem at hand cannot be solved by the VRP solver.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "B2di7dQdAp", "reviewer": "Reviewer_45kN", "summary": "The work proposes a framework for solving complex vehicle routing problems using LLMs. The framework's novelty is decomposed retrieval of constraints, where the VRP's constraints are decomposed into individual constraints, and then relevant conditioning documents are retrieved, and code generation is conditioned on those documents.", "questions": "What is the set of VRP problems the evaluation was performed on? Is this set publicly available?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The  work combines an algorithmic solution with queries to LLM to solve challenging problems of operation research. The algorithms are described in detail, and accompanied by extensive empirical evaluation and ablation study.", "weaknesses": "Update: authors' clarifications and answers are quite convincing. Updating my evaluation accordingly.\n\nIntroduction: vehicle routing problems in computer science are not formulated or solved to route vehicle, contrary to what the introduction says. Many VRPs are hard problems to which other problems can be reduced to show hardness and devise approximations. \n\nMethodology: including a code base on VRPs into the set of the documents for retrieval introduces data leakage and effectively replaces code generation with search for appropriate code. Integration with Gurobi, where only single constraint solutions are provided, does not convince otherwise because Gurobi is a specific solver where constraints are inherently and trivially composable.  \n\nEmpirical evaluation: there are two important missing baselines without which the evaluation does not make much sense.\n1. Any VRP problem can be solved optimally by enumeration. Judging by the figures, problem instances are small, so enumeration should be feasible if slow. What is the ratio of running times  by DRoC and by enumeration? On both successful and unsuccessful instances, mean and standard deviation of the log ratio of running times.\n\n2.There are non-LLM based (including the code base used for conditioning) algorithm implementation for VRP problems used for evaluation (here is how the optimal solution metrics are obtained). Similarly, what is the ratio of running times (mean/standard deviation of log ratio)?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "I7v4NPnwpy", "reviewer": "Reviewer_x6QC", "summary": "The paper presents DRoC, an approach for LLM-based generation of VRP optimization models via decomposed retrieval of constraints. Specifically, DRoC iteratively improves solutions by using both self-debugging and specialized RAG that integrates external knowledge per constraint based on decomposition of the VRP constraints. Experiments on 48 VRP variants and two solvers (OR-Tools, Gurobi) show the proposed approach significantly outperforms the baselines.\n\n\n----\nBased on the authors' response and improvements to the paper, I have increased my evaluation.", "questions": "I would appreciate if the authors could comment on the points mentioned above, in particular with respect to the experimental evaluation.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Strengths:\n- LLMs for operations research modelling is an important topic with significant recent interest.\n- Experiments over 48 VRP variants show significant gains for the proposed approach\n- Paper is mostly clear and written well.", "weaknesses": "Weaknesses:\n- I have major concerns regarding the experimental evaluation:\n\t- Evaluation based on success rate can be misleading: the generated code could run successfully and lead to a feasible solution but not the correct one for the requirement. For example, it can ignore (relax) some of the constraints, thus keep the problem feasible.\n\t- Evaluation based on optimality gap is also unclear to me in this setting. Comparing optimality gaps makes sense when we compare the efficiency of solving or modelling techniques (assuming both candidates are solving the same problem). Here we are comparing the accuracy of the formulation. If you are not solving the same problem (e.g., because generation dropped a constraint or added a constraint while maintaining feasibility) it is not clear how this helps. \n\t- It is also not clear how the optimal solution (used in the OG computation) is obtained. Is it based on a ground-truth formulation, or on solving the generated instance for longer? While the appendix indicates a time limit of 100s to determine optimal solution, it is not clear what was the time limit for the solving of the generated instances.\n\t- Overall it seems like none of the evaluation actually talks about the correctness of the generated model.\n\n- A more restricted setting (user provides both the name of the VRP variant and the signature of the function with clear documentation) compared to various previous work that supported natural language. This is a more restricted setting that requires more expertise from the user (both coding and familiarity with the literature). For example, if the user knows the problem they are solving is called \"Capacitated Vehicle Routing Problem with Time Windows and Multiple Depots\", they can probably decompose it themselves to the aspects of \"capacitated\" \"time windows\" and \"multiple depots\" (or that we could hard code those for each of the 48 problems, there are not that many) eliminating the need for a decomposer. This is not a flaw but it does restrict the potential impact of the approach.\n\n- From a technical perspective there is limited innovation and it is more of a new LLM-based workflow. It is not entirely clear to me that these ideas will generalize well outside of VRP (even in the world of operations research), for example, the decomposer seems to rely heavily on the very useful naming of VRP problems that clearly define its constraints.\n\n- Minor: \n\t* OG is presented as a fraction but presented in percentage.\n\t* According to OG formula it is not clear that OG is bounded at 1 (the difference can be larger than the optimal value), and therefore it is not clear why 1 is used for unsuccessful programs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "stH32UPV3V", "reviewer": "Reviewer_sHTV", "summary": "This work mainly established a novel RAG-LLM framework called DRoC which can resolve various complex VRPs with composite constraints. DRoC incorporates internal LLM knowledge and external information by decomposing the retrieval of constraints, deeply stimulating the intrinsic ability of LLM in intergrating different sources, and generating the problem-solving code without any training process. This approach can either flexibly apply vairous expert documentations or rigorously self-debug as circumstances may require, while iteratively optimizing the solution multiple times. The experimental results indicate that DRoC achieves SOTA preference in each metric compared with other homogeneous methods.", "questions": "- It seems this is a code generation problem specifically. Is it more proper to add the keyword \"code generation\" to this paper?\n- In figure 1, why are the numbers of different additional constraints not the same? A uniform standard is better needed, especially for the intro figure.\n- At the end of section 4.2 \"Single-constraint resolution\", does \"selecting the most relevant document\" mean that currently DRoC retrieves information from only one document for each additional constraint? Is there any opportunity for LLMs to retrieve and digest information from multiple documents and make a composite utilizaiton of them?\n- What are the standard prompts in section 5.1?\n- What's the support for the statement at the end of section 5.4 \"the LLMs can solve the 48 VRP variants with more composite constraints, indicating that complex tasks can be fulfilled by our decomposition-based method\" ?\n- I do not understand the motivations behind section 5.6 and 5.8, which seem not to be tightly related to the main topic of DRoC.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- This paper clearly states its research motivation and emphasizes why it is important to establish a novel LLM framework for solving complex VRPs.\n- The methodology is rigorous and mature, paying attention to many practical details. This can be reflected in the mechanisms of the router, the debugger and the retriever with a refined structure.\n- The experimental results in section 5 show a promising enhancement when compared to the listed former approaches. Ablations studies also support the structure design of DRoC.\n- DRoC proposed a flexible problem-solving LLM-based framework without any training requirement. This framework could be referenced in other LLM scenarios with fast external information access.", "weaknesses": "- In my prospective, this is a pure prompt-based framework that may lack novelty and seem trivial. It would more significant if DRoC could shows more strong points other than SOTA preference, such as the generalization ability in analogous problems, remarkable inference efficiency, or convincing justification of framework structures, etc.\n- The figure 2 can be more precise in order to guide the reader to better understand the framework structure. (1) The workflow of this flowchart is currently incomplete. For example, the \"if not passed\" desicion node needs \"yes/no\" paths to direct different outcomes. (2) The specific positions of each LLM module mentioned in appendix A should be indicated in this chart. For example, when does DRoC apply the first/second-stage filters?\n- There is no specific dataset description in section 5. Appendix B provides an overall illustration of the considered VRP variants. However, the source of 48 problems remains unclear. This may affect the reproducibility of DRoC's experimental results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)