Efficient Meta Neural Heuristic for Multi-Objective Combinatorial Optimization

Summary

This article presents an efficient neural heuristic method based on meta-learning, referred to as EMNH (Efficient Meta-learning Neural Heuristic), for solving Multi-Objective Combinatorial Optimization Problems (MOCOPs). The authors employ a shared multi-task model to expedite the meta-learning process and introduce a weight vector-based scaling symmetric sampling approach to stabilize this process. Furthermore, they propose a layered fine-tuning method to effectively address all sub-problems. Experimental results demonstrate that EMNH outperforms existing neural heuristic methods on three classical MOCOPs and can also compete with traditional heuristic methods.

Strengths

1. The article addresses the practical and challenging issue of MOCOPs, presenting a novel neural heuristic approach that combines ideas from meta-learning, multi-task learning, and layered fine-tuning. 2. The proposed method's advantages are theoretically analyzed, including accelerated and stabilized meta-learning processes, along with reduced fine-tuning steps. 3. The article conducts comprehensive experiments on three different types of MOCOPs, comparing against various benchmark methods. It showcases the proposed method's advantages in terms of solution quality, learning efficiency, and generalization ability.

Weaknesses

1. The article inadequately discusses the limitations and shortcomings of the proposed method, such as its applicability to more complex or higher-dimensional MOCOPs, sensitivity to weight vector selection, and risks of overfitting or underfitting. 2. The article lacks sufficient details to explain the model architecture, hyperparameter settings, experimental setup, etc. This might affect the replicability and credibility of the results.

Questions

1. Did the authors consider using other types of neural network structures or meta-learning algorithms to implement the proposed method? If so, how do they compare to POMO and Reptile? 2. Did the authors attempt to test the proposed method on other types or scales of MOCOPs? If yes, what were the results? If not, what were the reasons?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

1. The proposed method might require substantial training data and computational resources to achieve ideal results, potentially limiting its feasibility and scalability in practical applications. 2. The proposed method might struggle with MOCOPs featuring nonlinear or non-convex objective functions, dynamic or stochastic constraints, multi-modal or multi-peak distributions, and other complex features. 3. The proposed method might not guarantee the identification of true Pareto-optimal solution sets, only approximated solution sets, potentially affecting evaluators' judgments on solution quality and diversity.

Summary

The paper proposes efficient meta neural heuristic (EMNH) for solving multi-objective combinatorial optimization problems (MOCOP). The paper provides novel scaled sampling method for stability and a hierarchical fine-tune method for sub-task specific performance improvement over MDRL. The idea is sound and the experiments yield better performance than the state-of-the-art methods for MOCOP.

Strengths

The idea of using multi-task body with different heads in meta-learning is sound. The experiments are detailed and convincing.

Weaknesses

I’m not an expert in MOCOP problem, as far as I’m concerned, I detect no weakness of this paper.

Questions

1. According to Table 2, although the traditional heuristics may yield the best performance, it would take them much more time to solve the problem. Given the same amount of fine-tuning time, what is the performance of the proposed MOCOP method EMNH? (i.e. set K to a large number).

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The proposed EMNH provides no guarantee for the pareto front.

Summary

This work proposes EMNH, an efficient meta neural heuristic, for solving multi-objective combinatorial optimization problems. It builds a single meta model to tackle different trade-offs among multiple objectives during training, which can be efficiently fine-tuned into specialized submodels to solve different trade-offed subproblems. The main contributions are: 1) a multi-task meta model with parameter-shared body and task-related heads that can handle different trade-offs at the same time; 2) a scaled symmetric sampling method to stabilize the multi-objective training with imbalanced objectives; and 3) a hierarchical fine-tuning method to gradually fine-tune a set of submodel with much fewer steps. Experimental results show that the proposed EMHN method can outperform other neural combinatorial optimization methods on different combinatorial optimization problems such as MOTSP, MOCVRP, and MOKP.

Strengths

+ This paper is well-written and easy to follow. + Multi-objective combinatorial optimization is important for real-world applications. Neural heuristic is a promising approach to tackle this problem, but only a few methods have been proposed recently. This work is a timely contribution to a promising research direction. + The proposed method obtains promising performances on various multi-objective combinatorial optimization problems.

Weaknesses

I have the following concerns for the proposed method: **1. Runetime and Efficiency of Fine-tune** The runtime of the fine-tuning approach is not clearly discussed in the paper. In my understanding, for solving a new problem instance, the meta-learning based methods need to first fine-tune the meta model into different submodels, and then run each submodel to generate corresponding approximate solutions. In other words, the prediction is not zero-shot inference. However, in all experiments, the reported runtimes for MDRL and EMNH are similar to DRL-MOA and PMOCO which support zero-shot inference. Why the cost of fine-tuning is not included in the runtime? **2. Structure of Multi-Task Meta Model** The proposed multi-task meta model has a single model body that is shared by all tasks and specialized heads for different tasks. Recent work has also investigated fine-tuning a small part of the neural combinatorial optimization model to improve the performance of each instance for single-objective problems [1]. What is the advantage of the proposed model structure for multi-objective optimization? Is there any guideline for model design? [1] Efficient Active Search for Combinatorial Optimization Problems, ICLR 2022. **3. Solution Distribution** EMNH mainly uses the weighted-sum strategy to decompose a multi-objective optimization problem into multiple subproblems. According to PMOCO [1], different decomposition methods will lead to very different solution distributions on a given problem instance, especially those with more than two objectives. In addition, as reported in a current work [2], the decomposition-based PMOCO will generate redundant solutions for different preferences. Will EMNH also have these two issues? Can these issues be addressed by the scaled symmetric weight sampling method? [2] Pareto Set Learning for Neural Multi-Objective Combinatorial Optimization, ICLR 2022. [3] Graph Learning Assisted Multi-Objective Integer Programming, NeurIPS 2022. **4. Fine-Tuning PMOCO** As reported in this work, PMOCO usually has a promising zero-shot prediction performance, but it cannot be further improved with the fine-tuned approach. In my understanding, PMOCO is also a variant of the AM structure in POMO. According to recent works [1], only fine-tuning a small part of the model parameters in POMO can significantly improve the performance of single-objective optimization. It is interesting to know why fine-tuning does not work for PMOCO.

Questions

- Please address the concerns raised in Weaknesses.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The limitation of the proposed method has been discussed in the conclusion section.

Summary

The paper introduces a meta neural heuristic in which a meta model is first trained and then fine-tuned with a few steps to solve corresponding single-objective subproblems. For the training process, a partial architecture-shared multi-task model is leveraged to achieve parallel learning for the meta model, so as to speed up the training. Meanwhile, a scaled symmetric sampling method with respect to the weight vectors is designed to stabilize the training. For the fine-tuning process, an efficient hierarchical method is proposed to systematically tackle all the subproblems. The article contains a review of related works and preliminaries, then it presents the introduced methodology. This is followed by the description of experiments, their settings, results, and analysis. The experiments were carried out for the multi-objective traveling salesman problem, multi-objective capacitated vehicle routing problem, and multi-objective knapsack problem. They showed that the introduced method is able to outperform the state-of-the-art neural heuristics in terms of solution quality and learning efficiency and yield competitive solutions to the strong traditional heuristics while consuming a much shorter time. The main text is followed by supplementary materials.

Strengths

The introduced methodology is quite advanced and seems to be innovative and successful. I also like that it was tested on several problems from different domains and besides reporting efficiency and the quality of the found solutions, the required time is reported too. The paper is well written and it is good that it is followed by the supplementary materials. I like that there is a pseudocode in the supplementary materials and the authors declared that the codes for all the methods will be made available.

Weaknesses

The main weakness I found is that the code and the datasets used in experiments are not available, so it is difficult to verify and reproduce the results. However, the authors provided some pseudocode and declared that the code will be made publicly available. Besides, didn't find serious weaknesses of this paper, but it is possible that I didn't understand some parts.

Questions

I don't have any specific questions.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The main limitation, according to the authors, is that the method can not guarantee to obtain the exact Pareto front (similar to other neural heuristics). Also, the code and the datasets used in experiments are not available, so it is difficult to verify and reproduce the results. However, the authors provided some pseudocode and declared that the code will be made publicly available. I didn't find other limitations, but it is possible that I didn't understand some parts.

Summary

In order to achieve higher learning efficiency and better solution quality, this paper proposed an efficient meta neural heuristic (EMNH), in which a meta model is first trained and then fine-tuned with a few steps to solve corresponding single-objective subproblems. For the training process, an architecture-shared multi-task model is leveraged to achieve parallel learning for the meta model, so as to accelerate the training; meanwhile, a scaled symmetric sampling method with respect to the weight vectors is designed to stabilize the training. For the fine-tuning process, an efficient hierarchical method is proposed to systematically tackle all the subproblems. The general idea of this paper is clear and logical.

Strengths

1. The methodology part of the paper is clearly described and has a certain degree of logic.

Weaknesses

1. In the Methodology part, this paper proposed three methods for accelerate training, stabilize training and hierarchical Fine-tuning. However, in the Introduction part, the connection between motivation of this paper and the proposed stabilized training method should be clearer described. 2. In the Experimental Results part, ablation experiment should be added in order to verify the effect of the proposed method. To be more specific, as for the experiments towards learning efficiency, the comparison between original method and method without adding stabilized training part should be done.

Questions

1. In the Experimental Results part, the experiment results in tables should be further analyzed. 2. In the Training Efficiency part, more current comparison method should be added in order to support the experimental conclusion with more sufficient and comprehensive experimental results. 3. Are there any control parameters in the proposed method? how sensitive are them? 4. The picture in Figure 4 is too small for clearly understanding of readers. 5. The writing of the paper could be improved for better description and clarification.

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

1. The experimental problems of this method are limited to real-world problems, and further experimental verification should be carried out on synthetic problems.

Official Comment by Reviewer EY2k

The reviewer appreciates the authors' detailed response. After reading the rebuttal, I have decided to maintain the previous rating.

Thank you for the detailed response.

Thank you for your detailed response, and all my concerns have been properly addressed. I keep my positive score (6) and lean toward accepting this paper.