Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization

We thank the reviewer for their time and constructive feedback. Our responses are below, with the revised paper attached as a PDF.

W1: Related works

We included the mentioned papers and other related works in the related work section (in red). Most RL-based approaches for multi-objective optimization rely on carefully selected convergence and fitness landscape features. In contrast, our approach uses a graph representation to learn advanced features during training, eliminating the need for feature design. While many methods focus on operator selection, they overlook configuring operator parameters. Unlike these approaches, often aimed at continuous optimization, we focus on multi-objective combinatorial optimization, where the discrete, high-dimensional, non-smooth solution spaces make generalizing parameter configurations across instances challenging.

W2: Graph information comparison

Chen et al. introduce NHDE, using graph attention to model relationships between the instance graph and the first Pareto front to guide methods like PMOCO. However, similar to decomposition-based methods, its applicability is limited by the specialized network structure for specific problems like TSP and CVRP with distance-based objectives. In contrast, our method is more versatile, solving different problem categories (routing and scheduling) with multiple objectives, including problems that are difficult to represent in a graph for decomposition or end-to-end approaches (e.g., DAFJS-STST).

Unlike NHDE, our graph representation captures the state of the evolutionary search. Rather than focusing on encoded solutions and solely the first Pareto front, we represent the entire objective space of all solutions in the population, mapping all fronts and normalizing them based on objective convergence. To demonstrate our method’s performance, we include NHDE-P (NHDE with PMOCO) in Appendix F. While inferior in size 100, GS-MODAC is superior for generalizing to different distributed instances in the other sizes.

W3: Unclear methodology

Nodes represent the objective values of solutions at a given iteration, mapped onto multiple objective planes and normalized based on objective convergence. The graph interconnects the points in the different Pareto fronts. As such, the final state represents a structured visualization of the final solution space and the convergence of the method. We have added this clarification to the caption of Figure 1 and extended our motivation in the introduction.

W4-1: Action space

To apply the method to different algorithms, only the output layer needs adjustment to match the number of parameters. Appendix B shows its application to MOPSO, which requires more parameters than NSGA-II. The results in Table 5 (Appendix C) demonstrate that GS-MODAC improves MOPSO's performance, highlighting its effectiveness across algorithms.

W4-2: Model generalization

The models can generalize to other configurations, and the method can train a well-performing policy when trained on all sizes. To show this, we used the 5j5m and 10j5m models for larger Tri-FJSP instances and trained GS-MODAC on all sizes. The results show that the 10j5m-trained model scales well to larger configurations, while the 5j5m model shows lower scalability. The model trained on all sizes performs well overall, achieving the best 5j5m results and second-best for 10j5m, performing comparably to the best baseline.

W5: In-depth analysis

The method is not provided with information about encoded solutions or the objective to be optimized, relying entirely on generalizing graph states to guide the underlying algorithm. To analyze this, we visualized the relationship between the states and actions in Appendix G using a model trained on objectives A/B to solve both objective configurations. While the graph patterns are visually similar, A/B converges faster toward balanced solutions, while C/D obtains solutions with more competing objectives, resulting in wider Pareto fronts. This leads to different actions: A/B is configured with high mutation and lower crossover rates, while C/D is configured with high crossover rates. The graph states can explain this: A/Bs solutions that are more similar in objective values seem to benefit from more local exploration, while C/D's competing objectives demand broader exploration. This indicates the method’s ability to adapt actions to the graph's features.

W6: Minors:

Thanks for these pointers, we have updated this accordingly.

Thanks for the responses. I keep my score due to four reasons:

a) the related work, although has been refined, still shows imcompleteness. Two recently proposed surveys [1][2] might help the authors to futher grasp up-to-date works.

b) the results in your response (W4-2), lack error bars. I can not tell the significance of the reulsts. Besides, the results for training GS-MODAC on 25j5m are missing. Further, if I understood it correctly, current results indicate that training on GS-MODAC on all sizes degrades the final performance? (e.g., 5.63 v.s. 5.70 on 10j5m, 2.09 v.s. 2.14 on 25j5m) I think this verifies the limited generalization of GS-MODAC.

c) in W4-1, you claim that for new algorithm, only the final MLP requires to be changed. I agree with that, however, what shape of the MLP (number of layers, what kind of activation function) should be adopted when we adapt GS-MODAC to different algorithms with different complexities? Besides, although the network before the final MLP does not to be changed, it requires re-training, this is not efficient. If the authors claim universality of GS-MODAC across diverse algorithms, there are two key points should be integrated into current version (from my perspective): 1) making the MLP a fixed maximum output length, while interprete action for different algorithms. 2) training GS-MODAC on an associate distribution of algorithms and problem intances.

[1] https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4956956 [2] https://arxiv.org/pdf/2411.00625

Thank you for your response. Please find the revised paper attached as PDF.

Point A: Related work

Thank you for bringing these very recent works to our attention. We have carefully reviewed these papers and found valuable insights into challenges that require careful consideration and were addressed in our study. For instance, [1] discusses the difficulties of deep reinforcement learning (DRL) in managing high-dimensional state spaces and large-scale multitask learning problems. [2] highlights the limitations of many studies that overlook the parameter configurations of operators they learn to select, as well as the limitations in generalizability, where methods are often only trained and demonstrated on simple continuous optimization problems and standard benchmark functions. In our work, we focus on multi-objective combinatorial optimization. We build upon an N-dimensional graph as MDP, which avoids relying on high-dimensional state spaces while optimizing N objectives simultaneously. Additionally, we aim to learn how to control parameter configurations for solving combinatorial optimization. By configuring the state in the standardized graph-based representation, we can generalize trained models to different instance sizes, objectives, and complex problem variants. We have also shown the method's applicability in integrating it into different EC algorithms. We included the observed challenges in the related work section of our paper. We did not find any specific work in these two papers that is more relevant to our research than those we have already cited.

Point B: Significance

Please find the updated table below, including error bars, and the performance results of GS-MODAC trained on 25j5m and the overall-best baselines (SMAC3). With the results provided in the table above, we aimed to address your concerns regarding the scaling of the models trained on small problem instances (5j5m/10j5m, which are cheaper to train on) to solve large-sized instances.

From the table, we observe that the model trained on all instance sizes performs less effectively than models trained directly on the size of the tested instances. However, it consistently outperforms all other baselines specifically trained or tuned on the testing problem configuration in terms of mean and maximum hypervolume (except for the maximum hypervolume on 5j5m, where irace scores slightly better). This supports the conclusion that the trained models can generalize effectively to handle instance sizes not encountered during training.

Point C: Generalizability

It is important to clarify that our objective was not to create a universal model capable of managing multiple EC algorithms simultaneously. This is due to the significant differences in the search dynamics of various EC methods. For instance, Swarm Intelligence and Evolutionary Algorithms exhibit fundamentally different search behaviors, meaning that identical action selections can produce vastly different outcomes depending on whether they are applied with MOPSO or NSGA-II operators. To illustrate this, in response to point 1, we applied a trained model for MOPSO with a fixed output length to control NSGA-II in solving the CVRP. This resulted in a notable decrease in performance (see table below). In response to 2, we have trained GS-MODAC on both NSGAii and MOPSO simultaneously for different configurations of the CVRP problems. Also for this configuration, we observe a strong performance decline, although less severe than point 1.

We acknowledge the need to retrain GS-MODAC when adapting it to a new algorithm may seem inefficient. However, this approach prioritizes preserving performance while ensuring versatility. The trained model can adapt effectively to problems configured with varying objectives, instance sizes, or more complex problem variants, scenarios that are highly relevant in real-world applications.

Thank you to the reviewer for their thoughtful review and helpful suggestions. We have provided our responses to the comments below and attached the updated manuscript as a PDF.

W1: Choice for static problems

Although we acknowledge that stochastic problems are very interesting and relevant, addressing these scenarios using search-based methods typically requires extensive simulations to account for variability, vastly increasing the computational resources required for this study. By sticking to the selected problems in this work, we were able to highlight its effectiveness in dynamically configuring algorithms based on the stage of the search, and generalizing to different problem sizes (Table 2), more complex problem variants (Table 3), and different objective functions (Table 4).

W2: Size of Shops and CVRP problems

We focused on smaller problem instances to assess the effectiveness of GS-MODAC. These instances enabled controlled experiments, demonstrating the method's applicability across diverse problem domains, sizes, and objectives. Scaling up to larger problem instances would significantly increase computation time, making search-based methods a less optimal solution.

Q1: Selection of benchmarking methods

In this work, we focus on the dynamic configuration of algorithms. As such, we have compared with traditional methods for algorithm configuration (vanilla (NSGAii), Bayesian optimization (SMAC3), and search (iRace), and with state of the art dynamic algorithm configuration method (MADAC).

We appreciate the reviewer's effort and insightful feedback. Here are our detailed responses. We provide a revised version of our work in the attached PDF file.

W1: lack in-depth analysis

Aim As described in our abstract, this work develops a DRL-based method for dynamic algorithm configuration (DAC) in multi-objective combinatorial optimization (MOCO). Unline static algorithm configurations, which assume fixed optimal parameters, DAC adapts during optimization. Despite its effectiveness, its research on MOCO remains underexplored. This work innovatively applies DRL with graph neural networks to automatically learn DAC for MOCO.

Challenges Applying DRL to learn DAC for MOCO poses significant challenges. Configurations at each step must be guided by states and rewards that capture effects across multiple objectives. Existing RL-based DAC approaches have limitations: they often rely on manually selected convergence and landscape features, which are tedious and suboptimal. Moreover, they primarily focus on operator selection while neglecting the operator's parameters, and are limited to simple continuous optimization problems, overlooking the greater complexity of MOCO's discrete and combinatorial solution spaces. We discussed this in lines 51-65.

Solutions We propose a graph-based representation framework that eliminates manual feature design to address these challenges. Inspired by metrics like elite solutions, solution spacing, gaps, and hypervolume, our method dynamically learns advanced features to capture the state across objective planes. With normalization in graph representation and reward functions, our approach achieves superior performance in configuring MOCO algorithms, generalizing effectively across problem sizes (Table 2), complex variants (Table 3), and objectives (Table 4). We discussed this in lines 60-65

W2: Embedding information in a GNN

Unlike the reviewer suggested, we do not retrain our graph structure during each iteration. Our approach focuses on graph classification and uses GCNs in an inductive manner. Specifically, we separate the train and test data, training the GCN only on graphs from the algorithm’s search state for training instances. Empirically, we have shown that our inductive approach enables the GCN to achieve strong generalization performance, as demonstrated by our results (Tables 2, 3 & 4). Intuitively, the GCN learns effective graph embeddings from the (normalized) structure of Pareto solutions that differentiate states in the algorithm process. Our results show that the proposed method is computationally efficient (as detailed in responses to W3 and W4 below), and delivers promising outcomes in the targeted optimization tasks. We conducted an ablation study to evaluate the choice of GCN (Table 8), which consistently delivered the best overall performance with comparable runtime, confirming its effectiveness for our framework.

W3: Computational costs of updating DRL parameters

Unlike the reviewer mentioned, our approach does not require updating the DRL parameters at each iteration. After training, the inference of the DRL policy only requires the state configuration at each step and the computation of the policy network to generate new parameter configurations for the optimization algorithm. Compared to the static-configured algorithm, the added computational costs of GS-MODAC are negligible, especially for larger problem instances where the additional computation of GS-MODAC is more slight than the runtime of the optimization algorithm itself. Further details on the computational costs of our approach and its components can be found in our responses to W4.

W4: Computational Complexity

We profiled GS-MODAC to assess its computational complexity, focusing on graph state configuration and policy network inference. Results show the actor's inference time is 0.13 seconds, and state extraction takes 0.2 seconds, together accounting for 2.0% of the total time for the smallest problem instances. For larger problems, this proportion decreases significantly as solution evaluations dominate computation. Despite a slight overhead, its substantial performance gains justify GS-MODAC’s minimal additional cost.

W5&6: Role of GCN and Resolutions

Figure 1 has been updated with detailed computations within the agent, and the resolutions of all figures have been improved.

W7: Analysis of limitations

A limitation of our approach is the lack of usage of a specialized RL algorithm for contextual MDPs. While our ablation study showed the advantage of GCN, it can be further advanced to enhance the learning of Pareto front representations. We have updated our conclusion section with this analysis.

After reading other reviews and the rebuttal, I hold my score due to following reasons:

1. Please provide an in-depth analysis of your method, your responses are not convincing. For example, you should provide a theoretical analysis to demonstrate the effectiveness of your method.
2. Exploring the reasons behind the success of these techniques and providing intuitive explanations would contribute to the overall scientific contribution of the work.
3. Why not provide computational complexity before rebuttal?
4. The format of references violates the code of ICLR.
5. Please provide more peer competitors to enhance the generalizability of your method.
6. You should provide the training costs, and memory costs. DRL is very slow compared to other superior methods.

Thank you for these insightfull points. Here are our detailed responses. We provide a revised version of our work in the attached PDF file.

Q1: In-depth analysis

Theoretical analysis for methods that use neural networks (NNs) to learn heuristics (DRL policies) is very rare in existing literature. This is because NNs learn complex patterns that are difficult to explain or model mathematically. The adaptive nature of NNs makes it hard, often impossible, to provide a detailed theoretical justification for their performance.

Intuitively, our method works well because the DRL policy learns to leverage the graph-based representation to capture the current search state of the iterate process, sample actions to interact with it, and achieve better convergences of the different objectives. The reward scheme is designed to encourage Pareto optimal solutions in a problem-agnostic way, with increasing rewards as the search converges toward an ideal point. By incorporating normalization in both the graph representation and the reward function, we ensure the method generalizes well and performs efficiently across various scenarios. For more in-depth insights, we refer to our response to Q2, where we offer a further intuitive explanation of the method’s effectiveness, supported by additional analysis in Appendix G.

Q2: Intuitive explanations behind the success of GS-MODAC

The success of our method can be attributed to its ability to adapt actions based on the underlying graph states, even without direct knowledge of the encoded solutions, instance information, or the objective to be optimized. To illustrate this, we visualized the relationship between states and actions in Appendix G, using a model trained on objectives A/B to solve both A/B and C/D objectives configurations. The figure shows that while the graph patterns for A/B and C/D are visually similar, their convergence behaviors differ. A/B converges more quickly toward balanced solutions, while C/D tends to produce solutions with more competing objectives, resulting in wider Pareto fronts. These differences lead to varying action strategies: for A/B are high mutation and low crossover rates selected, while for C/D it selects higher crossover rates.

The different graph states offer an intuitive explanation for this. The A/B solutions encoded in the graph, which are more similar in objective values, benefit from more local exploration. In contrast, C/D's solutions, which involve competing objectives, require a broader exploration of the solution space. This ability of the method to adjust actions based on the graph's features demonstrates its flexibility and adaptability, contributing significantly to the overall success of the approach.

Q3: Reporting on computational complexity

Computational complexity is often not included in the literature for neural network-based methods like ours, as the emphasis generally tends to be on empirical performance rather than computational complexity. In our case, we chose not to report inference times initially because the algorithm adds only a negligible computational overhead: 2% for the smallest FJSP configuration and dropping to only 0.001% for the largest configuration, as the evaluation of the underlying solutions dominates the runtime. Following the reviewer's suggestion, we have included our computational complexity analysis in Appendix I.

Q4: References format

Thanks for this observation, we have updated the violating reference where we used parenthesis using \citet{} to meet the ICLR template requirements.

Q5: Peer competitors comparison

We have integrated our framework with a Swarm Intelligence-based algorithm, MOPSO, with implementation details provided in Appendix B. The results presented in Table 5 (Appendix C) show that GS-MODAC enhances MOPSO's performance, demonstrating its effectiveness across different algorithms.

Q6: Training and memory costs

Details about the training are provided in Section 4, under Baselines and Training. The training was conducted on an Intel(R) Xeon(R) CPU E5-1650 v4 processor with 16 GB of RAM, using five parallel environments. While DRL requires a longer training period than the tuning times of the baselines, the trained network can be directly utilized during testing without needing additional training or fine-tuning of the policy during inference. This makes it highly efficient in terms of testing and deployment.

We appreciate the insightful feedback. Below are our detailed responses, and the revised paper is attached.

W1: Graph representation benefits

We used a graph representation to avoid the cumbersome and suboptimal process of manual state space design. We have added additional explanations of its benefits in the introduction and provided more details about its construction in the caption of Figure 1 (marked in red).

W2: DRL agent interaction

Following the reviewer's suggestion, we have extended subsection 3.2 to briefly reflect on how the agent interacts with the MDP.

W3: Components justification:

Pooling aggregates the node embeddings into a fixed-size graph representation, summarizing the population’s solutions to predict algorithm parameters. To investigate the mean pooling choice, we tested max, sum, and attention pooling methods on Tri-FJSP-10j5m and found them generally inferior to the mean pooling used in our work:

The feature vector, indicating the remaining search budget, is provided to the agent after the pooling layer. Its impact is shown in Table 7, which also highlights the benefit of multiple GCN layers. Table 8 compares GCN's contribution to other popular GNNs. In an additional experiment, we tested the HV rewarding component with an Inverted Generational Distance (IGD) metric. Results in Appendix E demonstrate GS-MODAC's effectiveness for IGD.

W4-1: Results observation:

We are indeed referring to the comparison algorithms. Although GS-MODAC, trained on Bi-CVRP-100, performs slightly worse than MADAC (trained on Bi-CVRP-500) in mean HV, it outperforms MADAC in max HV. We’ve updated our statement (in red in Section RQ2) to clarify that the generalized models, despite training on different problem sizes, perform similarly to MADAC while surpassing the other baselines.

W4-2: Results observation:

The reviewer’s observation is correct. We have revised the statement in RQ2 to emphasize that models trained on diverse instance sizes can learn a robust, well-performing policy. We ran additional experiments and added performance results for a model trained on all Bi-CVRP sizes to Table 2. Additionally, we provide below new results for a model trained on all Tri-FJSP sizes, outperforming the model trained on the smallest instances for 5j5m, and the best non-learning baseline (irace) on the larger instances.

W5: Additional Baselines

We added new baseline results in Table 3 (in red), including GS-MODAC trained on the complex variants. GS-MODAC trained on the complex variant demonstrates superior performance (except for mean HV in the Penta-problems). The results also show that the method generalizes well to more challenging variants. Notably, GS-MODAC trained on 10j5m outperforms all other baselines tuned for the DAFJS and YFJS problems.

W6: Problem size CVRP

We conducted the experiment using the PMOCO setup, including their tuned models, configurations, data generation, and problem sizes (20, 50, and 100). Following another reviewer's suggestion, we did additional experiments and updated Appendix F with results for NHDE-P (Chen et al., 2024). NHDE-P outperforms PMOCO in generalizability but underperforms on the smallest instance size and smaller different distributed instances.

W7: MADAC inclusion

Thanks for the suggestion; we’ve added MADAC to the ablation study in Table 7.

W8: Naming consistency:

We updated the names to use only the 'Bi-CVRP-100' notation.

Q1: High budget run

Our reward function requires only an approximation of the ideal point during training. Lower budgets can still provide a good estimate, and even with an underestimated ideal point, the function remains effective, rewarding convergence beyond 100%. The table below shows that NSGA-II with a doubled budget does not outperform GS-MODAC.

Q2: SMAC3 comparison

We selected NSGAii as the baseline for its foundational configuration. However, since SMAC3 performs better for this problem, we conducted further experiments and included it in Figure 2. The figure shows GS-MODAC outperforming both baselines.

Q3: HV performance metric

We conducted the experiment using the PMOCO setup, including their tuned models, configurations, data generation, and problem sizes (20, 50, and 100).

Thank you for your valuable feedback, which has helped improve our work. Below are our detailed responses to the follow-up questions, and a revised version is included in the attached PDF.

Q1: Agent mechanism

After receiving the state input, the DRL agent processes the graph-based state using two GCN layers. These layers extract node embeddings, capturing both local and global structural information within the graph. A global mean pooling operation then aggregates these node embeddings into a single graph-level embedding, creating a compact summary of the graph's structure. This graph embedding is concatenated with a feature vector containing search budget information and is then passed through a linear layer to predict the mean values of the action distributions. We have described this working in lines 272-284, and the advantages of the agent configurations are demonstrated through the ablation study in Appendix E.

Graphs offer a powerful means of representing structured and informative embeddings, with the flexibility to scale to different sizes. Graph Neural Networks (GNNs), such as GCNs, have been widely applied across diverse graph-related tasks due to their ability to effectively model graph structures and extract meaningful representations [1]. In our case, we leverage GNNs to extract the graph state, enabling the DRL agent to make more informed and effective decisions based on the state of the iterative search. We modified section 3 to provide readers with essential background knowledge on GNNs and outline their benefits for our graph-based learning. Additionally, following the suggestion, we have incorporated additional background knowledge of DRL in related work in ‘algorithm configuration’.

[1] https://www.sciencedirect.com/science/article/pii/S2666651021000012

Q2: Additional Baselines

We have included the additional baselines in Table 4. We observe here that the observation still holds; the trained models can be transferred to other configurations of the problem, finding solutions of similar or better quality than the configured baselines, with a similar performance gap as observed for two objective problem variants displayed in Table 1.

Q3: Name consistency

Thanks for this observation, we updated the names to use only the 'SMAC3' notation.

Q4: Comparison on FJSP

In the context of multi-objective optimization, we are unaware of any end-to-end learning approaches specifically designed for multi-objective FJSP. We compared our method against end-to-end approaches such as PMOCO and NHDE-P, which are designed specifically for multi-objective routing problems. Although our method did not outperform PMOCO and NHDE-P on all instances, we want to point out that POMCO and NHDE-P can only be used to solve specific routing problems, as they rely on specialized network architectures tailored for Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP). In contrast, our method effectively guides multi-objective evolutionary algorithms, enabling them to address diverse problems across different domains and with varying objectives. This versatility allows our approach to be seamlessly applied to two distinct problem types (scheduling and routing), a capability that has yet to be demonstrated by other Pareto front approximation/end-to-end solution methods.

Q5: HV performance metric

We formulated the results of this experiment using the PMOCO setup, including their objective, tuned models, configurations, data generation, and problem sizes (20, 50, and 100). Following another reviewer's suggestion, we did additional experiments and updated Appendix F with results for NHDE-P (Chen et al., 2024), which was also performed according to this setup.

Q6: Statistical tests

We have performed statistical tests using the Wilcoxon rank-sum test ($p < 0.05$), as explained in Section 4 in “testing” and we demonstrate significance in the main results table (Table 1). Here, we underlined significantly better solution values. In the additional tables, we included alternative baselines for GS-MODAC, such as models trained on different problem sizes or variants. In these tables, we observed for various configurations that proposed GS-MODAC models performed significantly better than other baseline methods. However, as there is no significant difference among the GS-MODAC variants themselves, we could not identify a GS-MODAC configuration that significantly outperformed all the included solution results. Therefore, no underlining is performed for these scenarios.

Thank you for this response. Below, we answer your questions:

[Statistical tests] We conducted statistical tests for the results presented in the remaining tables. However, many of these experiments included alternative GS-MODAC-based baselines, which were trained on different problem sizes or variants. Since the performance of various GS-MODAC-based models was similar, there were no significant differences among these variants. As a result, no single GS-MODAC configuration consistently outperformed all other solutions. We have identified testing scenarios where all trained models significantly outperformed the included baselines (e.g., in the Tri- and Panta DAFJS and YFJS problem variants).

[MADAC baselines] As stated in lines 57-60, we argue that MADAC, being designed for continuous optimization, may not work well on large-size, complex COPs with many objectives, due to less smooth solution spaces and a wide range of objective values of COPs. This limitation was evident in its substantial performance shortcomings across various scheduling problem variants in Table 1. Consequently, we excluded MADAC from the additional scheduling experiments presented in Tables 3 and 4. Notably, the other baseline methods that were included in these tables consistently match or surpass MADAC's performance on the scheduling problems presented in Table 1 (apart from max HV for Penta-FJSP-25j5m).