Neural Multi-Objective Combinatorial Optimization via Graph-Image Multimodal Fusion
Authors: Jinbiao Chen
Jiahai Wang
Zhiguang Cao
Yaoxin Wu
Venue: ICLR 2025 Poster (2025)
Keywords: Neural Multi-Objective Combinatorial Optimization
Multimodal Fusion
Deep Reinforcement Learning
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: This paper proposes a graph-image multimodal fusion framework for neural multi-objective combinatorial optimization.

Abstract: Existing neural multi-objective combinatorial optimization (MOCO) methods still exhibit an optimality gap since they fail to fully exploit the intrinsic features of problem instances. A significant factor contributing to this shortfall is their reliance solely on graph-modal information. To overcome this, we propose a novel graph-image multimodal fusion (GIMF) framework that enhances neural MOCO methods by integrating graph and image information of the problem instances. Our GIMF framework comprises three key components: (1) a constructed coordinate image to better represent the spatial structure of the problem instance, (2) a problem-size adaptive resolution strategy during the image construction process to improve the cross-size generalization of the model, and (3) a multimodal fusion mechanism with modality-specific bottlenecks to efficiently couple graph and image information. We demonstrate the versatility of our GIMF by implementing it with two state-of-the-art neural MOCO backbones. Experimental results on classic MOCO problems show that our GIMF significantly outperforms state-of-the-art neural MOCO methods and exhibits superior generalization capability.

Published as a conference paper at ICLR 2025
NEURAL MULTI-OBIECTIVE COMBINATORIAL OPTI- MIZATION VIA GRAPH-IMAGE MULTIMODAL FUSION
Jinbiao Chen', Jiahai Wang Zhiguang Cao Yaoxin Wu?,
School of Computer Science and Engineering, Sun Yat-sen University, P.R. China 2 Key Laboratory of Machine Intelligence and Advanced Computing. Ministry of Education,
Sun Yat-sen University, P.R. China
3 "Gunngdong Key Laboratory of Big Data Analysis and Processing, Guangzhou, P.R. China
"School of Computing and Information Systems, Singapore Management University, Singapore
$ DDepartment of Industrial Engincering & Innovation Sciences, Eindhoven University of Technology chen jubnnbb6 6 (9mmmil22 sysu. edu. en, wangjiahhmmill sysu. edu.cn zgcao smu. edu. sg, y. ywu22tue.nnl
ABSTRACT
Existing neural multi-objective combinatorial optimization (MOCO) methods still exhibit an optimality gap since they fail to fully exploit the intrinsic features problem instances. A significant factor contributing to this shortfall is their re- liance solely on graph-modal information. To overcome this, we propose a novel graph-image multimodal fusion (GIMF) framework that enhances neural MOCO methods by integrating graph and image information of the problem instances. Our GIMF framework comprises three key components: (1) a constructed in- stance image to better represent the spatial structure of the problem instance, (2) a problem-size adaptive resolution strategy during the image construction process to improve the cross-size generalization of the model, and (3) multimodal fusion mechanism with modality-specific bottlenecks to efficiently couple graph and im- age information. We demonstrate the versatility of our GIMF by implementing it with two state-of-the-ar neural MOCO backbones. Experimental results on classic MOCO problems show that GIMF significantly outperforms state-of- the-art neural MOCO methods and exhibits superior generalization capability.
INTRODUCTION
Multi-objective combinatorial optimization (MOCO) involves optimizing multiple conflicting ob- jectives within a discrete solution space, resulting in trade-off's between different criteria for infor- mative decision making. It holds significant importance due to its wide range of real-world applica- tions in logistics, scheduling, resource allocation and so on (Ehrgott & Gandibleux, 2000; Liu et al., 2020: Türkyılmaz et al., 2020). MOCO aims to identify Pareto-optimal set of solutions, where any improvement in one objective necessitates a compromise in another. Since an MOCO problem more complex than its single-objective counterpart, exact methods generally impractical for MOCO, due to the NP-hard complexity of typical CO problems. As an alternative, heuristic methods have been developed to efficiently search for approximate Pareto-optimal solutions. Nevertheless, the conventional heuristics heavily hinge on problem-specine expertise and instance-specific tuning work for achieving desirable performance, posing challenges in automatic algorithm development.
With the rapid progress of neural CO methods for single-objective CO problems (Kool et al., 2019; Kwon al., 2020; Bi al., 2022; Chen al., 2022: Zhang al., 2022: Grinsztajn et al., 2023; Chalumeau et al., 2023; Drakulic et al., 2023; Son et al., 2023; Fang et al., 2024; Xiao et al., 2024a;bxe; Goh et al., 2024; Liu et al., 2024; Zhou et al., 2024; Wang et al., 2024; Kong et al., 2024), recent years have witnessed surge in the development of neural MOCO methods. Differing from conventional heuristics, the neural MOCO employs deep neural models to autonomously learn constructive policies from problem instances in data-driven manner. It allows for the automatic search of promising end-to-end solutions, bypassing the labor- inbeeninte algorithm development in
"Corresponding Author.

---

Published as a conference paper at ICLR 2025
Instance graph
Instance graph
Instance
image
Graph Transfomer
Multimodal Transfomer
Charnel
Solution
Solution
Channel
(a)
(b)
Figure 1: Typical neural MOCO methods (a) vs. the proposed GIMF framework (b). An example of instance image (c) for an M-objective 5-node traveling salesman problem is illustrated, with blank and black pixels filled with 1 and 0, respectively.
conventional heuristics. However, current neural MOCO methods still exhibit an optimality gap, as they fail to fully exploit intrinsic features of problem instances. They commonly represent a prob- lem instance a graph that lacks the informed representations inherent in other modalities such as images, thus hindering neural models from achieving comprehensive encoding.
In this work, construct images of MOCO problems with the aim offer the complementary instance information from different modalities, i.e., graphs and images. To advance neural models, develop graph-image multimodal fusion (GIMF) framework synergize the multimodal rep- resentation learning for enhancing the MOCO performance. The difference between our framework and current neural MOCO methods, and the images used in this paper are illustrated in Figure
Our contributions are summarized as follows. (I) We propose a transformation from an MOCO instance to construct an instance image, which with the graph representation, provides complemen- tary multimodal information to facilitate comprehensive representation learning in neural models. (2) During the image construction, we present problem-sizz adaptive resolution (PSAR) strat- egy that effectively enhances the model's generalization capacity for out-of-distribution problem sizes. (3) We design a multimodal fusion mechanism with modality-xpccifie bottlenecks (MSB) to favorably synergize the multimodal information from the graph and image. (4) We demonstrate the versatility of our GIMF framework by deploying it with two state-of-the-ar neural MOCO methods. Experimental results classic MOCO problems show the significant superiority of our GIMF, The advantageous effects of the multimodal fusion and generalizability are corroborated as well.
RELATED WORKS
Conventional MOCO methods. Conventional MOCO methods are categorized into exact and heuristic approaches. Exact methods exhaustively identify Pareto-optimal solutions, resulting in pro- hibitive exponential computational complexity (Ehrgott et al., 2016; Figueira et al., 2017). con- trast, heuristic methods, particularly multi-objective evolutionary algorithms (MOEAs) (Deb et al., 2002: Zhang & Li, 2007; Deb Jain, 2013; Deng et al., 2022; Qi et al., 2014; Yuan et al., 2016), are competent to efficiently search for near-optimal solutions. Furthermore, the problem-specific local search algorithms can be integrated into general MOEAs (Jaszkiewicz, 2002; Shi et al., 2020; 2024) enhance the performance. Despite considerable domain knowledge invested in algorithm design, these conventional heuristics still require intensive intrinsic searches from scratch when solving each instance, underscoring a significant limitation in their effectiveness. For more detailed survey on heuristics for MOCO, please refer to Verma et al. (2021); I); Liu et al. (2020).
Neural MOCO methods. Most neural MOCO methods decompose the MOCO problem into a se- ries of scalarized subproblems, addressing each through a single-objective neural CO method, such as the notable policy optimization with multiple optima (POMO) (Kwon et al., 2020). Based on the number of trained models, neural MOCO methods can be grouped into three categories: multi- model, single-model, and unified-mood model methods. Multi-model methods train a set of neural models via transfer learning (Li et al., 2021; Zhang et al., 2021) meta-learning (Zhang et al., 2023; Chen et al., 2023a), with each model specialized for each specific subproblem. contrast, single-model methods (Ye et al., 2022; Wang et al., 2024) employ single model for all subproblems, typically multi-objective combinatorial optimization (PMOCO) (Lin
represented by preference-conditionn al., 2022), but they still require substantial efforts in the separate training for different problem
2

---

Published as a conference paper at ICLR 2025
sizes. The most recent unified-modd method, the conditional neural heuristic (CNH) (Fan al., 2024), trains only a generic model that can generalize across various sizes, achieving the state-of- the-art performance in neural MOCO. Distinct from the mainstream decomposition- based neural methods, some orthogonal research attempts to enhance diversity (Chen et al., 2023b) or develop learning-based iterative methods (Wu al., 2022; Su et al., 2024; Ye et al., 2025), which signifi- cantly increase computational overhead for limited improvements. This paper focuses on improving the optimality of subproblems in decomposition based neural methods by employing the graph- image multimodal fusion.
3 PRELIMINARY
An MOCO problem can be defined minwen objective vector with M objective functions, π is the decision variable, and Ω is a discrete feasible solution space. The Pareto properties of solutions for an MOCO problem provided below.
where f is the
Definition 1 (Pareto dominance). A solution πe' dominates another x² (denoted as π < n²) f( f((")), Vi E (1,... M) and fT(' < (, Ej E M.)....M.
Definition (Pareto optimality). A solution π is Pareto optimal if it is not dominated by any other solution æ. The Pureto sel refers all Pareto optimal solutions, i.e., P { Ω 7lr' E ft: a xt }. Its image in the objective space is known as the Pareto front, i.e., F = {f(x) E R. T EPP.
3.1 DRCOMPOSITION-BANT BASED NEURAL MOCO
The decomposition is widely used technique for MOCO problems. An MOCO problem can be de- composed into N subproblems, each of which is scalarized CO problem associated with weight vector E RM satisfying X; 2 0, Vi {1...., .) and ΣM A; 1. The scalarized objective g(T[A) for a subproblem can be derived by different scalarization functions, e.g., the most straight- forward weighted sum (WS) represents the objective minmen gws(TT|) = Σ> fffi(T). After decomposition with N weight vectors, the N derived subproblems are solved by neural CO methods.
Neural CO methods for subproblems. Treating the solution π sequence π { ..... ,T) of length T. the solution construction process for a scalarized subproblem is Markov decision process, with following definitions: (1) The state step E (I....TT) consists of the weight vector A, the current partial solution 11:-1 and the instance G. (2) The action is selecting node n, to add to T- (3) The state transition is represented as ा:. = [ 11 m (4) The reward defined as the negative of the scalarized objective, i.e., R = g( 9 A). (5) The stochastic policy is parameterized by a neural model and used to sequentially construct the solution, with the process denoted by P(T|A,9) 9) = IIL Pa Ti 9) The policy network is typically trained by the REINFORCE algorithm (Williams, 1992), with the gradient VL(0)
B (o (A)
b) Ve log P(T,, |A, G.)], where B is the batch size, and is a baseline that is often derived from the average of multiple optima as done in POMO (Kwon et al., 2020), for reducing the variance.
Graph Transformer. An MOCO instance can be defined over a graph g = (V, where V = (U1,-..,%%, ) denotes the node set and & = (e(v, mty) [e; Uy V, + j) denotes the edge set. Given an instance graph with nodes featured by z-dimensional vectors Ui..... Un E R (see Appendix A), the majority of existing neural MOCO methods all adopt vanilla graph Transformer (Kool et al., 2019) (details in Appendix B) to handle the graph input. Generally, L self-attention layers in encoder evolve node embeddings to (-) (- E Rd (d 128). Then, the decoder uses the attention to autoregressively infer the probability of node selection with I' steps.
4 METHODOLOGY
Our graph-image multimodal fusion (GIMF) framework integrates complementary information from both graph and image modalities. The two key challenges are the construction of informative images from MOCO instances and the effective fusion of graph and image data. Correspondingly, propose an image construction approach with problem-size adaptive resolution (PSAR) strategy, and design multimodal fusion mechanism with modality-specifie bottlenecks (MSB).
3

---

Published as a conference paper at ICLR 2025
4.1
IMAGE CONSTRUCTION
Before stepping into the image construction approach, we first introduce the definition of the image.
Definition 3 (Image). An image is defined discrete function I D - C.K, where D ((r,y)a, E 2, S x S W, S I H} represents the set of pixels, with (x,y) denoting a pixel, W denoting the image width, and H. denoting the image height. The parameter K refers to the number of channels, and C is the set of possible pixel values for each channel. The image size (a..a.,, resolution) is defined as W H1. The most ubiquitous example the 3-channel RGB image, where C3 = 255 represents the intensities in the red, green, and blue channels.
Instance image for MOCO. Given an MOCO instance, we construct its image by specifying node features as pixels and pixel values separately. referred to as the instance image. Our image construc- tion generally applicable to different MOCO problems. In this paper, we consider classic MOCO problems that are extensively studied in the neural MOCO literature (Lin et al., 2022; Chen et al., 2023a;b; Fan et al., 2024), including the bi/tri-objective traveling salesman problem (Bi/Tri-TSP) (Lust & Teghem, 2010), bi-objective capacitated vehicle routing problem (Bi-CVRP) (Zajac & Hu- ber, 2021), and bi-objective knapsack problem (Bi-KP) (Ishibuchi et al., 2015) (Please see Appendix A for detailed problem statements). Their instance images are described below.
For the Mobjecttive TSP, each node i, Vi E {l..... n]. is featured by u, E R2M representing M groups of coordinates. Each pair (Va2y-1, Ui,2)), vjj {I..... MM, corresponds to the j-th group of coordinates. An M-channel instance image TMPT of the M M-objective TSP, can be constructed by treating each coordinate as a pixel, and defined as follows,
I M-PP (x, y) = -{ 1, otherwise
{
0, if (x, = (12)-11-(22))
(1)
where (1/22)- ((y)) E [1 x [1, H] is a coordinate derived by normalizing the original U1,2; E [0, 1J3, that is, (1/2))-11 ple of M-TT for a 5-node M-oojective TSP instance is illustrated in Figure 1(c). For Bi-CVRP, each node feature u E R² represents a coordinate (U1,02) E [0, 1]2 and a demand v3 E [0, 1). The single-channel instance image BBi-CVRP can be constructed by taking the normalized co- ordinate as a pixel and the demand as the pixel value. Formally, the image can be defined by ZBi-CVRP (Ix 3) 03. if (z. y) = (v/, v2)). For Bi-KP, the node feature u, E R3 represents two [0, 1) and weight v3 E (0, 1) of an item. Similarly, the single-channel instance image -BP-KP is constructed by taking two normalized values as pixel and the weight as the pixel
(LWox22-11 + 1, [[ + 1). An exam-
values (V),
value, resulting in Bii-KP KP (z, y) Uz if (z. v) (t1, v2))
4.2 PROBLEM-SIZE ADAPTIVE RESOLUTION
The constructed images are processed by a vision Transformer (Dosovitskiy et al., 2021), which is a mainstream neural model to handle image data. Concretely, a K-channel image with the resolution W x H is divided into non-overlapping patches with a uniform size w x h. Each patch is flattened into vector and linearly projected sinusoidal encoding) are added to the patch embeddings, enabling the model to be aware of the spatial relations between patches. Then, a standard Transformer encoder with L self-attention layers evolves the embeddings to capture global features and contextual relationships within the image.
d-dimensional embedding. Positional encodings (e.g., the
When our instance image adheres to the fixed resolution, common setting in ordinary image-related tasks, it could pose challenges in the generalization across problem sizes. Specifically, we define the node density p as the ratio of the non-one pixels in our instance image (Note: A low node density means that the number of non-one pixels approximately equals to the problem size n). Intuitively, the node density increases as the problem size n grows with fixed resolution, since more pixels occupied by non-one values. The density at the patch level varies proportionally due to the fixed patch size. Consequently, the neural model is subject to the -fft-ii-iitiittionn generalization issue when the patch-level density significantly differs from those of the training data.
Problem-size adaptive resolution (PSAR). To address the above generalization issue, we propose a PSAR strategy maintain relatively stable density for both the image and patches. Generally, can adaptively adjust the resolution by setting an approximately linear relationship between W x H and when constructing our instance image, so that the density is roughly uniform with varied
4

---

Published as a conference paper at ICLR 2025
Image bottleneck
Graph bottleneck
steeps
Patch embedding
Node embedding
Patch emboddings Node embeddings
Softmax
Vision layor
Graph layer
(LL-))
Query
Key
Value
Valuo
Key
Query
Compatibility
Image guided
Graph-guided cross- atss-attention
Multimodal fusion with MSB
Cross-attention
cross-attention
Encoder
Decoder
Figure 2: Our multimodal neural model based on an encoder-decoder (middle-right) architecture. The multimodal fusion layer with modality-specifff bottlenecks (MSB) (left) leverages modality- specific bottlenecks to efficiently couple the graph and image information. The dashed line pointing from the selected node πe the context embedding h. indicates that h, is determined by zy.
problem sizes. In this paper, we set w h and W H - density p of approximately 0.01. By doing so, the number of patches (i..,, the length of the patch sequence) varies with the changing problem size. However, the vision Transformer benefits from the stable density among patches, and hence gain better generalization performance.
x w to maintain the node
Scalable positional encoding. With the fixed patch size, the PSAR results varied lengths of propose learn scalable positional
the patch sequence. To indicate the positions of patches, encodings. We utilize a multi-layer perceptron (MLP) with a d-dimennsional hidden layer and ReLU activation map the patch coordinates (s* .y²) [0, 1J into position embeddings, which are then added to the patch embeddings. The MI.P is applicable to varied problem sizes due to the fixed size of input (i.e., patches).
4.3 MULTIMODAL FUSION
The simple graph structures (e.g., fully-connected graphs for TSP, CVRP, and KP) may obscure spatial relationships among nodes. Our instance image offers more informative view of the spatial structure, which maps more explicit node distribution to image. Mcanwhile, the graph remains essential for fine-grained node-level encoding and decoding. To effectively integrate these two com- plementary modalities, develop multimodal fusion model with modality-speciff bottlenecks.
Our multimodal fusion model, built in an encoder-decodee structure, illustrated in Figure 2. Given the graph and instance image of instance, the L-layer encoder processes them to generate high- dimensional node and patch embeddings. After that, the decoder computes the probabilities for node selection, which are used to sample nodes for constructing the solution.
Single-modal layer. the encoder, the node and patch embeddings are first passed through L L' single-modal graph and vision layers, respectively. Specifically, the initial node embed- dings h (0) E Rd are obtained via linear projection with a trainable matrix W and bias 6" which is formulated by h
(0) " + b" Vi E {1...., n). The initial patch embeddings h (0) (())) E Rd are derived from the flattened patch vectors u', u', E Ruh via linear projection and position encoding, which is formulated by h, Wn ut bb' +MLP(x, v/"), Vi [I. {I....,n'), n'}, where n' is the number of patches. Then, each single-modal graph and vision layer consists of a multi-head self-attention (MHSA) block with 8 heads and feed-forward (FF) block. Each block is followed by the residual connection (He et al., 2016) and instance normalization (IN) (Ulyanov al., 2016). The embeddings are updated each layer 1, VI E [ L-L),, as follows,
A = (1-H) + MHSA (( (-")), H' = -IN(H + MHSA H H'
H (0) IN + FF
O = IN + FF(H)))
where H and H' denote the concatenation of the node embeddings (h)..... h } and the patch embeddings (hi ), respectively, which iteratively evolved by single-modal layers.
5

---

Published as a conference paper at ICLR 2025
Multimodal layer. After L - L' single-modal layers. L' multimodal fusion layers used to ef- ficiently synergize the graph and image information. We introduce a small set of bottleneck tokens to manage cross-modal interaction for condensing essential information and alleviating the compu- tational burden of full attention calculations. Unlike the vanilla bottleneck approach (Nagrani et al., 2021), which uses shared bottlenecks across modalities, propose modality-specifft bottlenecks (MSB) to more precisely concentrate the information within each modality.
Specifically, we introduce nh, (nt n) graph bottlenecks B = {bi,.... b and ni, (n/ n') image bottlenecks B' = {bi..... by into the graph and vision layers. respectively. The initial
graph and image bottlenecks B(L-L'+1), B((L-L'11) E Rd are random learnable parameters and updated through T,' multimodal fusion layers. Using the bottlenecks, the efficient fusion is achieved by two types of multi-head cross-attention (MHCA) with heads. As depicted in Figure 2, the graph-guided and image-guided cross-attentions symmetrically fuse information between the two modalities. The multimodal cross-attentions at layer 1 E (L- L' 1,...,
......,,,, L), are given below,
L MHCA((E)())) B(I (H-1), ( ,B(-1), B)) "TT"","00) = MHCA((H (("-(-)),B"")))) (H B "(0-"),(-"1)) B(I-")),
(3)
where MHCA(X, Y) denotes the multi-head cross-attention with X representing the queries and Y representing the keys and values. The modal-specific bottlenecks improve performance of multi- modal fusion, while avoiding the computational burden by self-attention between all embeddings in modalities. We use the FF block, residual connection and IN similarly as in the single-modal layer.
Probability for node selection. In the decoder, we apply the node and patch embeddings processed by multimodal layers to autoregressively compute the probability for node selection. At each decod- ing step & {L..., T"). a context embedding h. which depends on T (see Appendix C), used to compute a glimpse qe via an MHCA block with 8 attention heads. This glimpse is then used to calculate the compatibility score a, as follows,
q. MHCAAhe, (H H H)),
if node i is masked
04 a
C. tanh( of (W
otherwise
vd
where the result is clipped with C 10 (Kool et al., 2019). Finally, the probabilities for selecting eligible nodes are normalized using softmax.
Deployment onto neural MOCO methods. Our GIMF is generic framework that can be in- tegrated with existing neural MOCO methods. We implement it with the state-of-the-art CNH to further enhance the performance in solving MOCO problems. Additionally, we implement GIMF with the well-known PMOCO, a type of method different from CNH, to demonstrate its flexibility. The resulting methods are referred to as GIMF-C and GIMF-P, respectively. GIMF-C employs dual-attention model to associate the instance with the weight vector of the scalarized subproblem, while GIMF-P utilizes hypernetwork to tackle the weight vector of the scalarized subproblem. The detailed architectures of GIMF-C and GIMF-P are given in Appendix D.
5 EXPERIMENTS
5.1
EXPERIMENTAL SETTINGS
Problems. We assess our GIMF framework on four well-established MOCO problems commonly examined in neural MOCO research, including Bi-TSP, Bi-CVRP, Bi-KP, and Tri-TSP. Detailed de- scriptions are provided Appendix A. For the experiments, we use three standard instance sizes:
20/ 20/50/100 for Bi-TSP, Bi-CVRP, and Tri-TSP, and 50/ 1000 /00 for Bi-KP. While CNH and GIMF-C are trained across problem sizes n E {20, 21, ... 100} (except n E {50, ... 2003 for Bi-KP), other neural methods trained separately for each problem size. Moreover, uate the model's 's out-of- oi--iitrinttion generalization capability on larger instances of 500250000/200 and three widely used TSPLIB (Reinelt, 1991) benchmark instances, i.e., KroABB00//5000 0001500/000
eval-
Hyperparameters. Most hyperparameters for GIMF-P and GIMF-C are configured in line with the original PMOCO and CNH, respectively. For model, T. 6, L' 3, and n. ng 10. The

---

Published as a conference paper at ICLR 2025
patch dimensions are fixed at = h 16. The model undergoes training for 200 epochs, with each epoch processing 100,000 randomly selected instances and a batch size of B = 64. The Adam optimizer (Kingma& & Ba, 2015) is used with learning rate of 10-4 (except 10-5 for Bi-KP) and weight decay of 10-6. The N weight vectors for the decomposition are generated according to Das & Dennis (1998), with N 101 for M 2 and N 105 for M = 3.
Baselines. We compare our method against state-of- offte- thrt neural MOCO methods, the widely used outlined below. (1) Neural MOCO methods: This includes the state-of-the-ar CNH (Fan et al., 2024) and PMOCO (Lin et al., 2022). Addition- ally, we include multi-model methods such as DRL-MOA (Li et al., 2021), MDRL (Zhang et al., 2023), and EMNH (Chen et al., 2023a). In particular, DRL-MOA trains N POMO models for the N subproblems, starting with 200 epochs for the first model and using 5-epoch parameter transfer for each subsequent model. Both MDRL. and EMNH fine-tune the N POMO models from shared pretrained meta-model with the same structure, following the training and fine-tuning configura- tions as described in Chen et al. (2023a). (2) Widely used MOEAs: Specifically, MOEA/D (Zhang & Li, 2007) and NSGA-II (Deb et al., 2002) are implemented with 4,000 iterations, representing decomposition- bbaed and dominance-base also with 4,000 iterations and 100 local search steps per iteration, and PPLS/D-C (Shi et al., 2024), which runs for 200 iterations, are both tailored for MOCO with a 2-opt heuristic for TSP and CVRP and a greedy transformation heuristic (Ishibuchi et al., 2015) for KP. (3) Strong problem-specine heuristics: For the multi-objective TSP and KP, WS-LKH and WS-DP combine the weighted sum (WS) scalarization with the strong LKH (Tinós et al., 2018) and dynamic programming (DP) solvers to handle scalarized subproblems. All methods adopt WS scalarization for fair comparisons, and are executed on machine equipped with an RTX 3090 GPU and an Intel Xeon 4216 CPU. Our code is publicly available'.
MOEAS, and strong problem-specifee heuristics,
MOEAs, respectively. MOGLS (Jaszkiewicz, 2002),
Metries. To assess the performance of the MOCO methods, we use the widely recognized hyper- volume (HV) indicator (Audet et al., 2021), where a higher HV value indicates a superior solution set (see Appendix E for more details). We report the average HV, the gaps relative to GIMF-C-Aug, and the total computation time for 200 instances. Methods with "-Aug" incorporate instance aug- mentation (Lin et al., 2022) (dctails in Appendix F) to enhance performance. A Wilcoxon rank-sum test at 1 % significance level is conducted to assess statistical differences. The best result and those not significantly different from it are highlighted in bold, while the second-best result and those not significantly different from it are underlined. The names of our methods are also presented in bold.
5.2 EXPERIMENTAL RESULTS
Comparison analysis. The comparison results are presented in Tables and 2. GIMF-C con- sistently outperforms CNH across all scenarios, establishing itself as the new ofate-of-the-art neural MOCO method. Similarly, GIMF-P shows significant improvement over PMOCO in every case, and it even surpasses PMOCO-Aug, which employs instance augmentation. on Bi-CVRP100, achieving a gap of 0.69% vs 2.70%. These results confirm the effectiveness of GIMF in synergizing the com- plementary strengths of graph and image information. Moreover, when enhanced with instance aug- mentation, GIMF's performance improves further. Compared with the cumbersome multi-model methods that require training fine-tuning numerous models, GIMF-C maintains superiority in most cases, with only slight underperformance relative to EMNH on Bi-CVRP and Bi-KP. Notably, GIMF-C still manifests significant superiority over EMNH on Bi-TSP and Tri-TSP, such as a gap of 1. 1.00% vs 3.09% on Tr-OTSP000. Additionally, GIMF significantly reduces computational time compared with conventional methods, as demonstrated by GIMF-C-Aug, which requires just 21 minutes vs 6.0 hours for WS-LKH on Bi-TSPI00, while delivering competitive results.
dittt--dit size generalization analysis. We evaluate the model's generalization ca- pability on the out-of-distribution larger-size Bi-TSP150/200 instances and benchmark instances KroAB100/155 50/200. The results of the neural methods are obtained based on models trained on Bi- TSPI00, except CNH and GIMF-C trained across sizes {20, 21, 100). shown in Table 3 and Figure 3. Compared with all neural baselines and well-known MOEAs, GIMF-C achieves the best generalization performance across all citto--distribution cases. Similarly, GIMF-P consistently outperforms PMOCO in all scenarios. The visualized Pareto fronts of TroAB100/110022 in Figure
'https://git thub. com /bi 11 11-oj//G/nn
7

---

Published as a conference paper at ICLR 2025
Table I: Comparison results on Bi-TSP and Bi-CVRP both with 200 random instances.
Bi-TSP20
Bi-TSP50
Bi- Bi-TSPI00
Method
HVT
Gapl
Time
HVT
Gapl
Time!
HVT
Gapl
Time
WS-LKH
0.6270
0.00%
10m
0.6415
-0.06%
1.8h
0.7090
-0.35%
6.0h
MOEA/D
0.6241
0.46%
1.7h
0.6316
1.48%
1.8h
0.6899
2.35%
2.2h
NSGA-II
0.6258
0.19%
6.0h
0.6120
4.54%
6.1h
0.6692
5.28%
6.9h
MOGLS
0,6279
-0.14%
1.6h
0.6330
1.26%
3.7h
0.6854
2.99%
11h
PPLS/D-C
0.6256
0.22%
26m
0.6282
2.01%
2.8h
0.6844
3.13%
11h
DRL-MOA
0.6257
0.21%
6s
0.6360
0.80%
9s
0.6970
1.34%
21s
MDRL
0.6271
-0.02%
5s
0.6364
0.73%
0.6969
1.36%
17s.
EMNH
0.6271
-0.02%
5s
0.6364
0.73%
9s
0.6969
1.36%
16s
PMOCO
0.6259
0.18%
6s
0.6351
0.94%
10s
0.6957
1.53%
19s
GIME-P
0.6266
0.06%
7s
0.6374
0.58%
12s
0.7006
0.84%
24s
CNH
0.6270
0.00%
14s
0.6387
0.37%
17s
0.7019
0.65%
29s
GIMF-C
0.6270
0.00%
15s
0.6397
0.22%
19s
0.7040
0.35%
33s
MDRL-Aug
0.6271
-.02%
33s
0,6408
0.05%
1.7m
0.7022
0.61%
14m
EMNH-Aug
0.6271
-0.05%
338
0.6408
0.05%
1.7m
0.7023
0.59%
14m
PMOCO-Aug
0.6270
0.00%
1.1m
0.6395
0.25%
3.2m
0.7016
0.69%
15m
GIMF-P-Aug
0.6271
-002%%
1.5m
0.6403
0.12%
4.7m
0.7043
0.31%
20m
CNH-Aug
0.6271
-0.02%
1.5m
0.6410
0.02%
4.1m
0.7054
0.16%
16m
GIMF-C-Aug
0.6270
0.00%
2.0m
0.6411
0.00%
5.5m
0.7065
0.00%
21m
Bi-CVRP20
Bi-CVRP50
Bi-CVRP100
Method
HV1
Gap.
Time!
HVT
Gap.l.
Time.]
HV1
Gap
Time.
MOEA/D
0.4255
1.05%
2.3h
0.4000
2.49%
2.9h
0.3953
3.09%
5.0h
NSGA-II
0.4275
0.58%
6.4h
0,3896
5.02%
8.8h
0.3620
11.25%
9.4h
MOGLS
0.4278
0.51%
9.0h
0.3984
2.88%
20h
0.3875
5.00%
72h
PPLS/D-C
0.4287
0.30%
1.6h
0.4007
2.32%
9.7h
0.3946
3.26%
38h
DRL-MOA
0,4287
0.30%
10s
0.4076
0.63%
12s
0,4055
0.59%
33s
MDRL
0.4291
0.21%
8s
0,4082
0.49%
13s
0.4056
0.56%
32s
EMNH
0.4299
0.02%
7s
0.4098
0.10%
13s
0.4072
0.17%
318
PMOCO
0,4267
0.77%
7s
0,4036
1.61%
12s
0.3913
4.07%
27s
GIME-P
0,4287
0.30%
7s
0.4076
0.63%
12s
0.4051
0.69%
29s
CNH
0.4287
0.30%
15s
0.4087
0.37%
17s
0.4065
0.34%
31s
GIME-C
0.4289
0.26%
15s
0.4089
0.32%
18s
0.4066
0.32%
36s
MDRL-Aug
0.4294
0.14%
11s
0.4092
0.24%
36s
0.4072
0.17%
2.8m
EMNH-Aug
0.4302
-0.05 %
0.4106
-0.10%
35s
0.4079
0.00%
2.8m
PMOCO-Aug
0.4294
0.14%
14s
0.4080
0.54%
36s
0.3969
2.70%
2.7m
GIMF-P-Aug
0.4298
0.05%
17s
0.4098
0.10%
48s
0.4075
0.10%
3.0m
CNH-Aug
0.4299
0.02%
22s
0.4101
0.02%
45s
0..4077
0.05%
2.5m
GIMF-C-Aug
0.4300
0.00%
25s
0.4102
0.00%
54s
0.4079
0.00%
3.1m
3 clearly show that the solutions identified by GIMF-C (or GIMF-P) are superior to those found by CNH (or PMOCO). Detailed results on these benchmark instances are provided in Appendix G.
Effectiveness of the multimodal fusion mechanism with MSB. To verify the effectiveness of our MSB, we compare GIMF with models utilizing other multimodal fusion mechanisms. The base- lines include the vanilla self self-attention (VSA) using a unified Transformer stream, the vanilla cross- attention (VCA) with two dedicated Transformer streams, a variant of MSB using fully learnable bottlenecks (FLB) in each layer, and the vanilla shared bottlenecks (SB) (Nagrani et al., 2021) with the same total number of bottlenecks as MSB. As shown in Figure 4, the results on in-distribution Bi- TSPI00 demonstrate that all multimodal methods outperform CNH, although the differences among these methods are not significant. However, the results differ on the out-of-distribution Bi-TSP200, where GIMF performs the best, while VCA, the performmn model, even falls short of CNH. In conclusion, while incorporating image information improves in-distribution performance, our multimodal fusion mechanism with MSB is critical for superior out-of distributtt performance.
Effectiveness of the PSAR strategy. To assess the effectiveness of the PSAR strategy, we remove it from both GIMF and VSA, resulting in the variants GIMF w/o PSAR and VSA w/o PSAR. For
8

---

Published as a conference paper at ICLR 2025
Table 2: Comparison results Bi-KP and Tri-TSP both with 200 random instances.
Bi-KP50
Bi Bi-KPIO0
Bi-KP200
Method
HVT
Gapl
Time
HVT
Gapl
Time!
HVT
Gapl
Time
WS-DP
0.3561
-0.03%
22m
0.4532
0.00%
2.0h
0.3601
0.03%
5.8h
MOEA/D
0.3540
0.56%
1.6h
0.4508
0.53%
1.7h
0.3581
0.58%
1.8h
NSGA-II
0.3547
0.37%
7.8h
0.4520
0.26%
8.0h
0.3590
0.33%
8.4h
MOGLS
0.3540
0.56%
5.8h
0.4510
0,49%
10h
0.3582
0.56%
18h
PPLS/D-C
0.3528
0.90%
18m
0.4480
1.15%
47m
0.3541
1.69%
1.5h
DRL-MOA
0.3559
0.03%
9s
0.4531
0.02%
18s
0.3601
0.03%
1.0m
MDRL
0,3530
0.84%
6s
0.4532
0.00%
21s
0.3601
0.03%
1.2m
EMNH
0.3561
-0.03%
6s
0.4535
-0.07% %
21s
0.3603
-0.03%
1.2m
PMOCO
0.3552
0.22%
9s
0.4523
0.20%
19s
0.3595
0.19%
1.3m
GIME-P
0.3560
0.00%
9s
0.4533
-0.02%
21s
0.3602
0.00%
1.3m
CNH
0.3556
0.11%
18s
0.4527
0,1 11%
27s
0.3598
0.11% %
1.2m
GIMF-C
0,3560
0.00%
18s
0,4532
0.00%
29s
0.3602
0.00%
1.4m
Tri-TSP20
Tri-TSP50
Tri-TSPI00
Method
HVT
Gap
Time|
HVT
Gapl
Time.
HVT
Gap
Time!
WS-LKH
0.4712
-0.13%
12m
0.4440
-0.54 %
1.9h
0.5076
-1.00%
6.6h
MOEA/D
0,4702
0.08%
1.9h
0.4314
2.31%
2.2h
0.4511
10.16%
2.4h
NSGA-II
0.4238
9.94%
7.1h
0.2858
35.28%
7.5h
0.2824
43.76%
9.0h
MOGLS
0,4701
0.11%
1.5h
0,4211
4.64%
4.1h
0.4254
15.28%
13h
PPLS/D-C
0.4698
0.17%
1.4h
0.4174
5.48%
3,9h
0.4376
12.85%
14h
DRI-MOA
0.4699
0.15%
6s
0.4303
2.56%
9s
0,4806
4.28%
19s
MDRL
0.4699
0.15%
5s
0.4317
2.24%
9s
0.4852
3.37%
16s
EMNH
0,4699
0.15%
5s
0.4324
2.08%
9s
0.4866
3.09%
16s
PMOCO
0.4693
0.28%
5s
0.4315
2.29%
8s
0.4858
3.25%
GIMF-P
0.4702
0.08%
6s
0.4354
1.40%
10s
0.4927
1.87%
23s
CNH
0.4698
0.17%
10s
0.4358
1.31%
14s
0.4931
1.79%
26s
GIME-C
0,4702
0.08%
12s
0.4384
0.72%
0.4971
1.00%
29s
MDRL-Aug
0.4712
-0.13%
2.6m
0.4408
0.18%
25m
0.4958
1,25%
1.7h
EMNH-Aug
0.4712
-0.13%
2.6m
0,4418
-0.5%%
25m
0.4973
0.96%
1.7h
PMOCO-Aug
0.4712
-0.13%
5.1m
0.4409
0.16%
28m
0.4956
1.29%
1.7h
GIMF-P-Aug
0.4712
-0.13%
13m
0.4415
0.02%
42m
0.5001
0.40%
2.7h
CNH-Aug
0.4704
0.04%
8.0m
0.4409
0.16%
33m
0.4996
0.50%
2.1h
GIMF-C-Aug
0.4706
0.00%
16m
0.4416
0.00%
44m
0.5021
0.00%
2.9h
KcoAHI0
KraAB150
KreA
IMDCO (ANTS)
PMERO (IN:
100
PMOCCO GEV: 8.7033)
CIMER P JERV 817313
(.RA3)
70
CNELGIV: (LT250)
CEMPCC OTV: (.WD)
GINICC 0.6R3)
SIV. 0.7297)
10-
62
30-
40-
10.
33
20
60 100
Figure 3: Pareto fronts of benchmark instances, KroAB100/150/2 (left/middlerrightt).
these variants, we set W - // [100/ X consistent with the size when 100. As shown in Figure 5, PSAR leads to a slight performance improvement on the in-distribution Bi-TSPI00. More importantly, it significantly boosts the out-of-diitribbutin performance for both GIMF and VSA. No- tably, without PSAR, GIMF and VSA even fall below CNH's generalization capability. These results underscore the critical role of the PSAR strategy in enhancing out-of-distribution performance.

---

Published as a conference paper at ICLR 2025
Table Out-of-distribution generalization larger-size problems with 200 random instances.
Bi-TSPI50
Bi-TSP200
Method
HVT
Gapl
Timel
HVT
Gapl
Time!
WS-LKH
0.7149
-1.65%
13h
0.7490
-1.74%
22h
MOEA/D
0.6809
3.18%
2,4h
0.7139
3.03%
2.7h
NSGA-II
0.6659
5.32%
6.8h
0.7045
4.31%
6.9h
MOGLS
0,6768
3.77%
22h
0.7114
3,37%
38h
PPLS/D-C
0.6784
3,54%
21h
0.7106
3,48%
32h
DRL-MOA
0.6901
1.88%
45s
0.7219
1.94%
1.5m
MDRL
0,6922
1.58%
40s
0.7251
1.51%
1.4m
EMNH
0.6930
1.46%
40s
0.7260
1.39%
1.4m
PMOCO
0.6910
1.75%
50s
0.7231
1.78%
1.5m
GIMF-P
0.6958
1.07%
60s
0.7267
1.29%
2.1m
CNH
0.6985
0.68%
1.1m
0.7292
0.95%
1.9m
GIMF-C
0.6993
0.57%
1.2m
0.7325
0.50%
2.2m
MDRL-Aus 0.6976
0.81%
47m
0.7299
0.86%
1.6h
EMNH-Aug
0.6983
0.71%
47m
0.7307
0.75%
1.6h
PMOCO-AU
0.6967
0,94%
47m
0.7283
1.07%
1.6h
GIMF-P-Aug
0.7003
0.43%
1.0h
0.7311
0.69%
2.
CNH-Aug
0.7025
0.11%
52m
0.7343
0.26%
1.7h
C-Au
0.7033
0.00%
1.1h
0.7362
0.00%
2.2h
Bi-TSP190
0,735
Bi-TSP200 (Out of distribuution)
Bi-TSPI00
B B3-TSP200 (Out distrbbtiin)
97312
873 6.90
ATOX 02940
07723
A724
0.705
0.72
0,30
cull
FLBC
RBcc
a
2
cwfl
HSA-C
vode
RBc
usc
P5DR
Gladi Fold
0.7
Cefl
754
GaM
Figure 4: Effects of multimodal fusion.
Figure 5: Effects of the PSAR strategy.
Hyperparameter study. We conducted experiments to investigate the impact of hyperparameters. The detailed results, provided Appendix H, indicate that both the number of multimodal fusion layers and the configuration of bottlenecks can influence the performance of multimodal fusion. For the problems we study, L' ni = ni, 10, and w 16 are the desirable settings.
CONCLUSION
This paper proposes generic GIMF framework that integrates complementary graph and image information for neural MOCO. We first construct an instance image to introduce structured image data, and the PSAR strategy during image construction is designed enhance out-of-distribution generalization. Then, we develop a multimodal fusion mechanism with MSB to efficiently fuse graph and image information. Our GIMF framework deployed with two state-of-the-arr neural MOCO methods. Experimental results confirm its effectiveness, and the ablation study highlights the necessity of both PSAR and MSB, particularly for improving --sttriibititiiion performance. A limitation of our current approach is its generalization performance on real-world scenarios and various MOCO problems. In future work, we plan to address this by exploring the hierarchical approach (Goh et al., 2024) and multi-task learning technique (Zhou al., 2024).
Another potential limitation of our method is that constructing images requires problem-specific de- signs to a certain extent, and incorporating images slightly increases the demand for computational resources. However, the resulting performance improvements are substantial, making this trade-ofi worthwhile. Furthermore, while the problems studied in this paper well-suited for image repre- sentation, there may be some other MOCO problems for which generating simple yet meaningful images challenging. In these cases, the applicability of method remains open question.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS AND DISCLOSURE OF FUNDING
This work is supported in part by the National Natural Science Foundation of China (62472461), and the Guangdong Basic and Applied Basic Research Foundation (2025A151501012)); in part by the National Research Foundation, Singapore under its Al Singapore Programme (AISG Award No. AISG3-RP-2022-031)
REFERENCES
Charles Audet, Jean Bigeon, Dominique Cartier, Sébastien Le Digabel, and Ludovic Salomon. Per- formance indicators in multiobjective optimization. European Journal of Operational Research, 292(2):397 2021.
Jieyi Bi, Yining Ma, Jiahai Wang, Zhiguang Cao, Jinbiao Chen, Yuan Sun, and Yeow Meng Chee. Learning generalizable models for vehicle routing problems via knowledge distillation. In Ad- vances in Neural Information Processing Systems, 2022.
Felix Chalumeau, Shikha Surana, Clément Bonnet, Nathan Grinsztajn, Arnu Pretorius, Alexandre Laterre, and Tom Barrett. Combinatorial optimization with policy adaptation using latent space search. In Advances in Neural Information Processing Systems, 2023.
Jinbiao Chen, Huanhuan Huang, Zizhen Zhang, and Jiahai Wang. Deep reinforcement learning with two-stage training strategy for practical electric vehicle routing problem with time windows. In International Conference on Parallel Problem Solving from Nature, 2022.
Jinbiao Chen, Jiahai Wang, Zizhen Zhang, Zhiguang Cao, Te Ye, and Siyuan Chen. Efficient meta neural heuristic for multi-objective combinatorial optimization. In Advances in Neural Informa- fion Processing Systems, 2023a.
Jinbiao Chen, Zizhen Zhang, Zhiguang Cao, Yaoxin Wu, Yining Ma. Te Ye, and Jiahai Wang. Neural multi-objective combinatorial optimization with diversity enhancement. In Advances Neural Information Processing Systems, 2023b.
I Das and Dennis. Normal-boundary intersection: new method for generating pareto-optimal points in multieriteria optimization problems. SIAM Journal on Optimization, 8(3):631-657, 1998.
Kalyanmoy Deb and Himanshu Jain. An evolutionary many-objective optimization algorithm using reference-point-oee nondominated sorting approach, part I: solving problems with box con- straints. IEEE Transactions on Evolutionary Computation, 18(4):577-601, 2013.
Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT Meyarivan. A fast and elitist multi- objective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2): 182-197, 2002.
Wu Deng, Xiaoxiao Zhang, Yongquan Zhou, Yi Liu, Xiangbing Zhou, Huiling Chen, and Huimin Zhao. enhanced fast non-dominated solution sorting genetic algorithm for multi-objective problems. Information Sciences, 385:441-455 2022.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, al. An im- age is worth 16x16 words: Transformers for image recognition at scale. International Confer- ence on Learning Representations, 2021.
Darko Drakulic, Sofia Michel, Florian Mai, Arnadd Sors, and Jean-Mare Andreoli. BQ-NCO: Bisimulation quotienting for efficient neural combinatorial optimization. Advances Neu- ral Information Processing Systems, 2023.
Matthias Ehrgott and Xavier Gandibleux. A survey and annotated bibliography of multiobjective combinatorial optimization. OR-spettrum, 22(4):425 460, 2000.

---

Published as a conference paper at ICLR 2025
Matthias Ehrgott, Xavier Gandibleux, and Anthony Przybylski. Exact methods for multi-objective combinatorial optimisation. Multiple criteria decision analysis: State of the art surveys, pp. 817- 850, 2016.
Mingfeng Fan, Yaoxin Wu, Zhiguang Cao, Wen Song. Guillaume Sartoretti, Huan Liu, and Guohua Wu. Conditional neural heuristic for multiobjective vehicle routing problems. IEEE Transactions on Neural Networks and Learning Systems, 2024.
Zhanhong Fang, Jinbiao Chen, Zizhen Zhang, and Dawei Su. Learning node-pair insertion for the pickup and delivery problem with time windows. In 2024 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pp. 1678-1683. IEEE, 2024.
José Rui Figueira, Carlos M Fonseca, Pascal Halffmann, Kathrin Klamroth, Luís Paquete, Stefan Ruzika, Britta Schulze, Michael Stiglmayr, and David Willems. Easy to say they are hard, but hard to they masy-towards a categorization of tractable multiobjective combinatorial op- timization problems. Journal of Multi-Criteri Decision Analysis, 24(1 (12-2))2--98, 2017.
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 Knowledge Discovery and Data Mining, pp. 894-895,20 2024.
Nathan Grinsztajn, Daniel Furelos-Blanco, Shikha Surana, Clément Bonnet, and Tom Barrett. Win- ner takes it all: Training performant rl populations for combinatorial optimization. In Advances in Neural Information Processing Systems, 2023.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In IEEE Conference Computer Vision and Pattern Recognition, pp- 770-778. 2016.
Hisao Ishibuchi, Naoya Akedo, and Yusuke Nojima. Behavior of multiobjective evolutionary algo- rithms on many- objeetbee knapsack problems. IEEE Transactions on Evolutionary Computation, 19(2):264-288 2015.
Andrzej Jaszkiewicz. Genetic local search for multi-objective combinatorial optimization. European Journal of Operational Research, 137(1):50-71, 2002.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In International Conference on Learning Representations, 2015.
Detian Kong, Yining Ma, Zhiguang Cao, Tianshu Yu, and Jianhua Xiao. Efficient neural collab- orative search for pickup and delivery problems. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference Learning Representations, 2019.
Ycong-Dae Kwon, Jinho Choo. Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. POMO: Policy optimization with multiple optima for reinforcement learning. In Advances in Neural Information Processing Systems, 2020.
Kaiwen Li, Tao Zhang, and Rui Wang. Deep reinforcement learning for multiobjective optimization. IEEE Transactions Cybernetics, 51(6):3103-1114 2021.
Xi Lin, Zhiyuan Yang, and Qingfu Zhang. Pareto set learning for neural multi-objective combinato- rial optimization. In International Conference on Learning Representations, 2022.
Fei Liu, Xi Lin, Zhenkun Wang, Qingfu Zhang, Tong Xialiang, and Mingxuan Yuan. Multi-task learning for routing problem with cross-problem zero-shot generalization. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1898-1908, 2024.
Qi Liu, Xiaofeng Li, Haitao Liu, and Zhaoxia Guo. Multi-objective metaheuristies for discrete optimization problems: A review of the of Applied Soft Computing, 93: 93:106382, 2020.
12

---

Published as a conference paper at ICLR 2025
Thibaut Lust and Jacques Teghem. The multiobjective traveling salesman problem: A survey and new approach. In Advances in Multi- Sultti-Objeetive Nature Inspired Computing, pp. 119-141, 2010.
Arsha Nagrani, Shan Yang, Anurag Arnab, Aren Jansen, Cordelia Schmid, and Chen Sun. Atten- tion bottlenecks for multimodal fusion. In Advances in neural information processing systems, volume 34, pp. 14200-14213, 2021.
Yutao Qi, Xiaoliang Ma, Fang Liu, Licheng Jiao, Jianyong Sun, and Jianshe Wu. MOEA/D with adaptive weight adjustment. Evooutionary Computation, 22(2):231-264 2014.
Gerhard Reinelt. TSPLIB traveling salesman problem library. ORSA Journal on Computing, 3 (4):376-384, 1991.
Jialong Shi, Qingfu Zhang, and Jianyong Sun. PPLS/D: Parallel pareto local search based on de- composition. IEEE Transactions on Cybernetics, 10(3):1060-11 2020.
Jialong Shi, Jianyong Sun, Qingfu Zhang, Haotian Zhang, and Ye Fan. Improving pareto local search using cooperative parallelism strategies for multiobjective combinatorial optimization. IEEE Transactions on Cybernetics, 54(4):2369-2382, 2024.
Jiwoo Son, Minsu Kim, Hyeonah Kim, and Jinkyoo Park. Meta-SAGE: Scale meta-learning sched- uled adaptation with guided exploration for mitigating scale shift on combinatorial optimization. In International Conference on Machine Learning, pp. 32194-32210. PMLR, 2023.
Dawei Su, Zizhen Zhang, Jinbiao Chen, and Zhanhong Fang. A discrete diffusion- bassd approach for solving multi-objective traveling salesman problem. In 2024 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pp. 374-379. IEEE, 2024.
Renato Tinós, Keld Helsgaun, and Darrell Whitley. Efficient recombination in the tin-kernighan- helsgaun traveling salesman heuristic. In International Conference on Parallel Problem Solving from Nature, pp. 95-107, 2018.
Alper Türkyılmaz, Özlem Senvar, irem Ünal, and Serol Bulkan. research survey: heuristic ap- proaches for solving multi objective flexible job shop problems. Journal of Intelligent Manufac- turing, 31:1949-1988, 2020.
Dmitry Ulyanov, Andrea Vedaldi, and Victor S Lempitsky. Instance normalization: The missing ingredient for fast stylization. arXiv preprint arXiv: w:Xivv/607.08022 2016.
Shanu Verma, Millie Pant, and Vaclav Snasel. A comprehensive review on nsga-ii for multi-objective combinatorial optimization problems. IEEE access, 9:57757-57799 2021.
Chenguang Wang. Zhouliang Yu, Stephen McAleer, Tianshu Yu, and Yaodong Yang. ASP: Learn universal neural solver! IEEE Transactions on Pattern Analysis and Machine Intelligence, 46 (06):4102-41) 222-41144 14, 2024.
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8:229-256, 1992.
Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, Abhishek Gupta, and Mingyan Lin. Graph learn- ing assisted multi-objective integer programming. In Advances in Neural Information Processing Systems, volume 35, pp. 17774-17787, 2022.
Pei Xiao, Zizhen Zhang, Jinbiao Chen, and Jiahai Wang. Neural model embedded heuristics for ro- bust traveling salesman problem with interval uncertainty. In 2024 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pp. 4193-4198, IEEE, 2024a.
Pei Xiao, Zizhen Zhang, Jinbiao Chen, Jiahai Wang, and Zhenzhen Zhang. Neural combinatorial optimization for robust routing problem with uncertain travel times. In Advances in Neural Infor- mation Processing Systems, 2024b.
Yubin Xiao, Di Wang. Boyang Li, Mingzhao Wang, Xuan Wu, Changliang Zhou, and You Zhou. Distilling autoregressive models to obtain regh-performace non-autoregressvve solvers for ve- hicle routing problems with faster inference speed. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 20274-20283 2024c.
13

---

Published as a conference paper at ICLR 2025
Te Ye, Zizhen Zhang, Jinbiao Chen, and Jiahai Wang. Weight-specific-decoder attention model to solve multiobjective combinatorial optimization problems. In 2022 IEEE International Confer- on Systems, Man, and Cybermetics, pp. 21-228822888 2844. IEEE, 2022.
Te Ye, Zizhen Zhang, Qingfu Zhang, Jinbiao Chen, and Jiahai Wang. Solving multiobjective com- binatorial optimization via learning to improve method. IEEE Transactions on Emerging Topics in Computational Intelligence. 2025.
Yuan Yuan, Hua Xu, Bo Wang. Bo Zhang, and Xin Yao. Balancing convergence and diversity in décomposition-aasee many-objective optimizers. IEEE Transactions on Evolutionary Computa- tion, 20(2):1804 10-198, 2016.
Sandra Zajac and Sandra Huber. Objectives and methods in multi-objective routing problems: a survey and classification scheme. European Journal of Operational Research, 290(1):1-25, 2021.
Hang Zhang, Zizhen Zhang, Jinbiao Chen, and Jiahai Wang. Solving quadratic traveling salesman problem with deep reinforcement learning. In 2022 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pp. 2508-2511 IEEE, 2022.
Qingfu Zhang and Hui Li. MOEA/D: multiobjective evolutionary algorithm based on decompo- sition. IEEE Transactions Evolutionary Computation, 11(6):712- 2007.
Yongxin Zhang, Jiahai Wang, Zizhen Zhang, and Yalan Zhou. MODRL/D-F Multiobjective deep reinforcement learning with evolutionary learning for multiobjective optimization. In Interna- fional Joint Conference Neural Networks, 2021.
Zizhen Zhang, Zhiyuan Wu, Hang Zhang, and Jiahai Wang. Meta-leaming--aas based deep reinforce- ment learning for multiobjective optimization problems. IEEE Transactions on Neural Networks and Learning Systems, (4(10):7978-799) 2023.
Jianan Zhou, Zhiguang Cao, Yaoxin Wu, Wen Song, Yining Ma, Jie Zhang, and Chi Xu. MV- MoE: Multi-task vehicle routing solver with mixture-of -f-exerss In International Conference Machine Learning. 2024.
14

---

Published as a conference paper at ICLR 2025
A DETAILED STATEMENTS OF THE STUDIED MOCO PROBLEMS
Multi-objective traveling salesman problem (MOTSP) In the M-objective traveling salesman problem with nodes, each node i E I,.,, Ti is associated with M groups of 2-dimensional coordi- nates. The Euclidean distance Gj between nodes i and j is determined by their coordinates for objec- tive m. The task is find a tour that visits all nodes while minimizing the total distances for each of the M objectives. Specifically, the objective is to minimize f(T) (TT(T)) (2( JM (T)). where (T) Li=1 Ca, + Ca,a Vm {I,..., M). The instances are generated by uni- formly sampling coordinates within the range [0, 1|2M
Multi-objective capacitated vehicle routing problem (MOCVRP) We study the bi-objective capacitated vehicle routing problem (Bi-CVRP), which involves customer nodes and one depot node. Each node has 2-dimensional coordinate, and each customer is associated with a demand. A fleet of homogeneous vehicles, all with the same capacity, is based at the depot and must serve all customers before returning. When serving a customer, the vehicle's remaining capacity must at least equal to the customer's demand. The two confficting objectives length and the makespan, defined as the longest route. For Bi-CVRP instances, the coordinates of both the depot and customers are uniformly sampled from the range [0, 1J2, while demands are drawn from the set f1.....9 9}. Vehicle capacity is set at 30, 40, and 50 for 20 S n < 40, 40 S n < 70, and 70 & I 100, respectively. All demands are normalized by the vehicle capacity for consistency.
minimize the total tour
Multi-objective knapsack problem (MOKP) In the multi-objective knapsack problem with M objectives and n items, each item has weight and M distinct values. The items are represented as nodes in the instance graph. The objective is to select items that maximize all M objectives simul- taneously, while ensuring the total weight does not exceed the knapsack capacity. The instances are generated by sampling the weight and values of each item from uniform distribution over [0, 1]. The knapsack capacity set to 12.5 for 50 I n < 100 and 25 for 100 S n S 200, respectively.
B ARCHITECTURE OF THE GRAPH TRANSFORMER
The MOCO instance graph can be processed by a graph Transformer (Kool et al., 2019) based on an encoder-decoder architecture. Given n nodes with z-dimensional features W1...., Un E R the en- coder first transforms them to the initial node embeddings h ...., h E Rd via linear projection h (0) W bb, Vi (1.....,)) n.,, and then compute the final node embeddings h1 ..... h via L Transformer layer. Each Transformer layer sequentially comprises a multi-head self-attention (MHSA) block with 8 attention heads, residual connection and instance normalization (IN) block, a feed-forward (FF) block, and another residual connection and IN block. The node embeddings
( (h1) (h....... .....
( are updated follows,
=NIN (1 (HISA(H"-))
(5)
H IN
The decoder take the derived node embeddings as inputs to calculate the selection probabilities for candidate nodes in an autoregressive manner with T steps. Specifically, at decoding step t E (I...,T), T), the glimpse qo is first computed using a problem-specific context embedding he as follows,
(7) where MHCA(X, (XY) the multi-head cross-attention with X as the querys and with Y as the keys and values. The number of attention heads is set to 8. The definition of h is provided in Appendix C. Then, the compatibility is calculated by the attention mechanism, as follows,
= MHCA(h,, H()),,
if node i is masked otherwise
C tanh 9. (W n
Vd
where = 10 is use to clip the result. Finally, the probabilities of node selection obtained using softmax function.
15

---

Published as a conference paper at ICLR 2025
C CONTEXT EMBEDDING
For MOTSP, the context embedding he at each decoding step is constructed by concatenating the embeddings of the first and last visited nodes, with all visited nodes masked when calculating node selection probabilities. In MOCVRP, the context embedding he consists of the embedding of the last visited node and the remaining vehicle capacity, and nodes already visited or with demands exceeding the remaining capacity masked during probability computation. For MOKP, the con- text embedding h. combines the graph embedding h = > h:/n with the remaining knapsack capacity. masking selected items and those with weights larger than the remaining capacity during probability calculations.
D ARCHITECTURES OF GIMF-C AND GIMF-P
D.1 GIMF-C
Following CNH (Fan et al., 2024), GIMF-C also employs multi-head dual-attention (MHDA) mechanism to handle the given weight vector and uses a size-aware decoder to capture the feature of the problem size. Thus,
adopt the multi-head dual-attention mechanism with 8 attention heads for each modality in our multimodal fusion model. Specifically, the initial embedding of " and patch embeddings H' {h', (0) ...., h', { are first obtained using separate linear projections. Then, in each single-modal Transformer layer 1, VI E {1...., L L'}. the multi-head self-attention (MHSA) is replaced by the
the weight vector hn+1, node embeddings H (h)
(0)
MHDA, as follows.
(H (H, = IN((H( A ( + MHDA(H (
(H 1HWhh IN((H, h + FF (F
(10)
H h n+1) IN[(H (111)) , (1-1)) MHDA(H 11,"), h (-11))),
(11)
(H ,h ()) IN(UEE,, fi' + FF( k(+1))),
(12)
where hh++1 (0) h 1 MHDA(X, Y) is formulated by integrating the MHSA and multi-head cross-attention (MHCA) mechanisms, follows,
MHDA(X, Y) {(HSSA{(X, Y)). MHCA(X, Y)), MHIS
(13)
After T.- T.' single-modal Transformer layers, the embeddings are updated by T'' multimodal fusion layers. The multimodal fusion layers involve additional ni graph bottlenecks B = {b), ................................ bmg + and n/, image bottlenecks B' = (b,....,66 .,, In each layer I, V. E LL, L}. the embeddings are updated through the graph-guided and image-guided dual-attention. In this process, the MHSA mechanism in MHDA (see Equation 13) is substituted with our multimodal meati-head cross-attention mechanism (see Equation 3), as follows,
H = MHCA((B (--1) H(-1), "(--",A"""" 1 (B H (-1) B((
(14)
( H 2 (H.,g (H mm:-1 + MHCA(H (111) (L- (--)))); )) H H_1),
(15)
H' = MHCA( (1-1) (111)) 1 (111),, (1))) 11111) Wn41 (1-1) B (1 ((1-))))
(16)
(B U W ()) (H''
m (H' 16:1 MHCA(H k (1 (1-1))) H' -1).
(17)
In the decoder, the size-injected node embeddings (L) are obtained by adding the problem size embedding (Fan al., 2024) to the node embeddings. Then, the glimpse is derived as follows,
qe MHCA(h.. (H((), ((
(18)
Finally, the probabilities of node selection can be computed the same.
16

---

Published as a conference paper at ICLR 2025
Table 4: Reference points and ideal points for the MOCO problems.
Problem
Size
r
20
(20, 20)
(0, 0)
50
(35, 35)
(0, 0)
Bi-TSP
100
(65, 65)
(0, 0)
150
(85, 85)
(0, 0)
200
(115, 115)
(0, 0)
20
(30, 4)
(0, 0)
Bi-CVRP
50
(45, 4)
(0, 0)
100
(80, 4)
(0, 0)
50
(5, 5)
(30, 30)
Bi-KP
100
(20, 20)
(50, 50)
200
(30, 30)
(75, 75)
20
(20, 20, 20)
(0, 0)
Tri-TSP
50
(35, 35, 35)
(0, 0)
100
(65, 65, 65)
(0, 0)
D.2 GIMF-P
Following PMOCO (Lin al., 2022), GIMF-P directly uses the multimodal fusion model as the base model. To manage each scalarized suproblem associated with weight vector, GIMF-P employs hypernetwork with multi-layer perceptron (MLP) structure generate decoder parameters, using the weight vector as input.
E HYPERVOLUME
Hypervolume (HV) is widely used indicator for evaluating the performance of MOCO methods, as it effectively measures both the convergence and diversity of the obtained Pareto front without requiring ground truth. The HV of a Pareto front F with respect to reference point r RM denoted as HV,, is defined as:
HV. =
UUU ( f(m)EF
(19)
where represents the Lebesgue measure, and [f( r] refers to an M-dimensional hypercube, ie.. [f(T),, rl [f()))
x (TT, rM].. The HV is normalized as HV' HV'r(F) HVr(F)/ II i=l Ir z/. where z is an ideal point such that 2; < min[f((T)))(( E F} (or 24 > max (
F} for maximization), Vi (l...., M). According to prior literature (Chen et al., 2023a;b), the same r and z are used across all methods for given MOCO problem, as summarized in 4
(f(
F MULTI-OBJECTIVE INSTANCE AUGMENTATION
During the inference phase, instance augmentation (Lin et al., 2022) can be used to improve per- formance by transforming an instance into multiple variations that all share the same optimal solu- tion. Each transformed instance is then solved, and the best solution among them is chosen. For Bi-CVRP, there are possible transformations based on the 2-dimensional coordinates, such as (a, y), (v) (x. y), (v. 1 z), (1 x, y), (1 y, x). (1 M-objective TSP, this leads to 8 transformations, as each of the groups of coordinates can be permuted independently. For KP, this instance augmentation is not applicable.
y), (1 y, 2). For the
17

---

Published as a conference paper at ICLR 2025
Table 5: Detailed results benchmark instances.
KreAB100
KroAB150
KroAB200
Method
HVT
Gapl.
Time
HVT
Gap!.
Time|
HV1
Gap!
Time!
WS-LKH
0.7022
-0.30%
2.3m
0.7017
-1.01%
4.0m
0.7430
-1.43%
5.6m
MOEA/D
0.6836
2.36%
5.8m
0.6710
3.41%
7.1m
0.7106
2.99%
7.3m
NSGA-II
0.6676
4.64%
7.0m
0.6552
5.69%
7.9m
0.7011
4.29%
8.4m
MOGLS
0.6817
2.63%
52m
0.6671
3.97%
1.3h
0.7083
3.30%
1.6h
PPLS/D-C
0.6785
3.09%
38m
0.6659
4.15%
1.4h
0.7100
3.07%
3.8h
DRL-MOA
0.6903
1.40%
10s
0.6794
2.20%
18s
0.7185
1.91%
23s
MDRL
0.6881
1.71%
10s
0,6831
1.67%
17s
0.7209
1.58%
233
EMNH
0.6900
1.44%
9s
0.6832
1.66%
16s
0.7217
1.47%
2.3%
PMOCO
0.6878
1.76%
98
0.6819
1.84%
0.7193
1.80%
GIMF-P
0.6936
0.93%
11s
0.6878
0.99%
21s
0.7231
1.28%
26s
0.6947
0.77%
25s
0.6892
0.79%
35s
0.7250
1.02%
41s
GIMF-C
0.6972
0.41%
25s
0.6895
0.75%
35s
0.7297
0.38%
42s
MDRL-Aug
0.6950
0.73%
13s
0.6890
0.82%
19s
0.7261
0.87%
28s
FMNH-AU Aug
0.6958
0.61%
12%
0.6892
0.79%
18s
0.7270
0.75%
27%
PMOCO-AIu
0,6937
0.91%
12s
0.6886
0.88%
19s
0.7251
1.01%
328
GIMF-P-Aug
0.6971
0.43%
15s
0.6924
0.33%
26s
0.7271
0.74%
45s
CNH-Aug
0.6980
0.30%
30s
0.6938
0.13%
37s
0.7303
0.30%
54s
GIMF-C-Aug
0.7001
0.00%
30s
0.6947
0.00%
39s
0.7325
0.00%
59s
Bi-TSP100
Bi-TSP200 (Out of distribution)
0.7042
0.734
0.7041
0.7325
0.7040
0.7040
0.7040
0.732
0.7311
BV
0,7039
0.7301
0.730
0,7038
0.7038
7281
0.728
0.7037
0.726
0.7036
3
L
Figure 6: Effects of the number of fusion layers.
G GENERALIZATION RESULTS ON BENCHMARK INSTANCES
The detailed out-of-distributioo generalization results are presented Table 5, further confirming the exceptional generalization ability of our GIME.
H HYPERPARAMETER STUDY
Effects of the number of multimodal fusion layers We vary the number of multimodal fusion layers L' while keeping the total number of layers fixed at L 6. The results in Figure 6 show that the model performs best when L' 3. If L' is too small, there may be insufficient fusion of multimodal information. Conversely, if L' is too large, the model's ability to learn from single modalities may weaken, reducing its performance. Therefore, selecting an appropriate value for L' is essential to achieve balance between multimodal fusion and single-modality learning, ultimately improving the model's performance.
Effects of the number of bottlenecks For the number n& (where set ni, n4) of bottlenecks introduced for multimodal fusion, the model performs best when n, is set to 10. as shown in Figure 7. Introducing many bottlenecks can increase the model's complexity, making effective learning
18

---

Published as a conference paper at ICLR 2025
0.7042
Bi-TSPI00
0.734
Bi-TSP200 (Out distribution)
0.7041
0.733
0.7325
0.7040
0.7040
0.7040
0,7040
0.7040
0.732
HV
0,731
0.7312
0.7312
0.7039
0.7039
0.731
0.7304
0.7038
0.730
0.7037
0.729
10
15
20
25
15
20
No. "ia
no. n
Figure 7: Effects of the number of bottlenecks.
0.7042
Bi-TSPI00
0.734
Bi-TSP200 (Out distribution)
0.733
0.7323
0.7325
0.7040
0.7040
0.7040
0.732
0.7040
HV
0.731
0.7039
0.7039
0, A22298
0.730
0.7292
0.7038
0.729
0.728
12
16
20
24
12
16
20
24
w,
Figure 8: Effects of the patch size.
more difficult, while too few bottlenecks may hinder the proper fusion of multimodal information, limiting the model's capabilities. Thus, selecting an appropriate number of bottlenecks ensures effective multimodal fusion and improves the model's performance.
Effeets of the patch size Different patch sizes correspond to different ways dividing the image, and selecting appropriate patch size is crucial. A large patch size results in smaller number of coarse coarse-grained patches, which may overlook some global information from the image, thereby affecting performance negatively. Conversely, a small patch size provides finer- finer-grained division, capturing more local details, but the resulting increase in the number patches can raise learning difficulty and computational cost, ultimately harming performance. As shown in Figure 8, both excessively large and excessively small patch sizes lead to performance deterioration. Setting 16 strikes desirable balance and yields the best results.
I ANALYSIS OF NEURAL NETWORK SIZE
While incorporating additional images increases neural network size, the experimental results demonstrate considerable performance improvements that justify this trade-off. To further rein- force this conclusion, comparisons between GIMF-C (or GIMF-P) and CNH (or PMOCO) under comparable model parameter settings presented in Table 6. Specifically, number of model parameters by adjusting the embedding dimension d, which was originally set to 128 following the previous works such CNH and PMOCO. The results strongly indicate that
control similar
19

---

Published as a conference paper at ICLR 2025
Table 6: Comparisons between GIMF-C (or GIME-P) and CNH (or PMOCO) under comparable
model parameter settings.
Method
Bi-TSP20
Bi-TSP50
Bi-TSPI00
Small-size
#(Parameter)
HVT
Gapl
HVT
Gapl
HV1
Gapl
PMOCO
1.42M
0,6259
0.18%
0.6351
0,94%
0.6957
1.53%
GIMF-P-S
1.49M
0.6265
0.08%
0.6368
0.67%
0.6993
1.02%
CNH
1.63M
0.6270
0.00%
0.6387
0.37%
0.7019
0.65%
GIME-C-S
1.66M
0.6270
0.00%
0.6391
0.31%
0.7028
0.52%
Large-size
#(Parameter)
HV1
Gapl
HVT
Gapl
HVT
Gapl
PMOCO-L
2.67M
0,6265
0.08%
0.6364
0.73%
0.6988
1.09%
GIME-P
2.69M
0.6266
0.06%
0.6374
0.58%
0.7006
0.84%
CNH-L
3.22M
0.6271
-0.02%
0.6393
0.28%
0.7027
0.54%
GIMF-C
3.20M
0.6270
0.00%
0.6397
0.22%
0.7040
0.35 %
the performance improvements stem primarily from the GIMF framework itself, rather than merely from an increase in neural network size. The results are summarized follows:
We reduce d to 80 for the small-size versions of GIMF-C and GIMF-P, referred to GIMF- C-S and GIMF-P-S, aligning the number of their model parameters closely with CNH and PMOCO, respectively. The results, detailed in the table below, indicate that both GIMF-C- S and GIMF-P-S consistently outperform their respective backbones with the close number of model parameters.
Besides, explore large-size by raise d to 200 for CNH and PMOCO, referred to as CNH-L and PMOCO-L, making the number their model parameters close to GIMF- C and GIMF-P, respectively. The results this large-size case consistently highlight the superiority of our GIME.
Notably, the small-size GIMF-P-S even surpasses the large-size PMOCO, while the small- size GIMF-CC HIMF-C-S performs comparably to the large-size CNH.
20


Reviews:
[{"review_id": "vAWmiux6ri", "reviewer": "Reviewer_QYyp", "summary": "This paper aims to fully leverage the intrinsic features of problem instances by proposing a novel graph-image multimodal fusion framework for solving multi-objective combinatorial optimization (MOCO). The authors introduce the concept of \"image\" for MOCO to better capture the spatial structure of problem instances, enhancing the learning process. They also propose a problem-size adaptive resolution strategy to improve generalization. Finally, the paper presents a multimodal fusion mechanism with modality-specific bottlenecks to efficiently integrate graph and image information.", "questions": "1. What's the training loss of the GIMF?\n\n2. Can GIMF obtain a Pareto set of solutions?\n\n3. I noticed the authors used multi-modal fusion, but I don't quite understand this part. Does it mean that each subproblem requires training a single model and then performing model fusion at the end?", "limitations": "", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The writing is good.\n\n2. The experiments are detailed, and the results are competitive.", "weaknesses": "1. I believe the role of the image concept in CO is questionable. To some extent, using images in CO results in information loss and requires more space to represent. As far as I know, many Euclidean TSP models, like [1, 2], use positions directly as input, which requires less space and provides more precise information.\n\n2. Compared to typical neural MOCO methods, GIMF uses sparse matrix images as input, resulting in larger neural network sizes and an inability to handle larger-scale routing problems.", "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": "koOwHg8AXK", "reviewer": "Reviewer_3Wbv", "summary": "The paper presents a novel graph-image multimodal fusion (GIMF) framework that aims to enhance neural multi-objective combinatorial optimization (MOCO) methods. The GIMF framework integrates graph and image information of problem instances, which is designed to overcome the limitations of existing neural MOCO methods that rely solely on graph-modal information. The main contribution of the proposed method is the coordinate image construction, which provides complementary information to the graph representation.To improve the model's generalization across different problem sizes, a Problem-size Adaptive Resolution (PSAR) strategy is proposed during the image construction process, which helps maintain a stable density for both the image and patches. A multimodal fusion mechanism with Modality-Specific Bottlenecks (MSB) is designed to efficiently couple graph and image information. \n\nThe GIMF framework is implemented with two state-of-the-art neural MOCO backbones, namely CNH and PMOCO. Experimental results on classic MOCO problems demonstrate that GIMF can improve neural MOCO methods by providing image-modal information and exhibits superior generalization capability.", "questions": "In Table 1 and Table 2, the reported times of GIMF-P and GIMF-C are sometimes smaller than PMOCO and CHN, what is the reason for this phenomenon?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The major contribution of this paper is its integration of both graph and image modalities to enhance the representation learning for MOCO problems. The construction of coordinate images and the use of PSAR strategy are innovative steps that address the limitations of relying solely on graph information. The proposed MSB in multimodal fusion mechanism is also a novel contribution.\n\n2. The paper is well-organized and written in a clear and concise manner. The introduction effectively sets the stage by outlining the challenges in MOCO and the motivation behind the GIMF framework. The preliminary section clearly describes the definition of the MOCO problem and related concepts, as well as the graph transformer for MOCO. The methodology section is detailed, providing a clear explanation of the image construction process, the PSAR strategy, and the multimodal fusion mechanism.\n\n3. The significance mainly comes from its novelty.Specifically, leveraging a multimodal approach that incorporates image-modal information, which has the potential to improve many existing neural MOCO methods. The paper is also likely to inspire further research in constructing and learning from images of MOCO problems.\n\n4. The experimental results suggest that GIMF does not obviously increase computational time of the neural MOCO basebone. The major innovations PSAR and MSB are validated by ablation study.", "weaknesses": "The proposed method could improve the performance of CNH and PMOCO, as well as their augment variants. However, sometimes the improvement seems marginal. In Table 1 and Table 2, the reported improvements are all mostly less than 0.001, and sometimes are as small as 0.0001. Meanwhile, the reported best results can not significantly outperform SOTA baselines.", "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": "sTqr923mtn", "reviewer": "Reviewer_SVeH", "summary": "This paper presents a novel Graph-Image Multimodal Fusion (GIMF) framework designed to enhance multi-objective combinatorial optimization (MOCO) methods. By integrating both graph and image information from problem instances, the framework effectively addresses the limitations associated with relying solely on graph-modal information, particularly in the context of bi- and tri-objective traveling salesman problems (TSP).", "questions": "- Is this analogous to a game played on a chessboard? Are the authors providing definitions and citations related to reinforcement learning? Are you aiming to transform the graph problem into a gameplay problem on a chessboard?\n- Has reinforcement learning for MOCO in chessboard games been well studied elsewhere? If MOCO, such as TSP, is defined within the context of a chessboard game, isn’t it relatively straightforward? Does this require a graph modality, or can the image modality defined by the authors alone be sufficient to address the MOCO problems?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The main novelty of this paper lies in defining the image modality alongside the graph modality, offering a new perspective for addressing challenges in MOCO.\n- This approach enhances conventional heuristic algorithms by leveraging the combined information from both modalities.", "weaknesses": "- If the image modality has been defined, why still continue to use the graph modality? How could one approach solving an MOCO problem using only the image modality? Additionally, could you provide ablation studies to support this?\n- Since the graph can also be viewed as a transition matrix, what is the relationship between reinforcement learning and the authors' algorithm?", "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": "ZKHbYdC2RY", "reviewer": "Reviewer_hYPJ", "summary": "This paper proposes a generic graph-image multimodal fusion (GIMF) framework that integrates graph and image information of the problem instances to enhance neural MOCO. The framework consists of three main components: (1) a constructed coordinate image (2) a problem-size adaptive resolution strategy and (3) a multimodal fusion mechanism. Experimental results demonstrate its effectiveness.", "questions": "1. What does \"$\\bm{\\pi_i}$\" represent in the formula for calculating $\\nabla\\mathcal{L}(\\bm{\\theta})$ on line 136, or should it be changed to \"$\\pi_i$\"?\n\n2. What is the meaning of the line from $\\pi_t$ to $h_c$ in Figure 2? The authors should supplement the relationship between $\\pi_t$ and $h_c$ in the main text.\n\n3. Why choose the dimension of patch as $w=h=16$? The authors should provide an explanation or conduct ablation experiments.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1.\tThis paper is well-organized and clear writing.\n2.\tThe proposed method demonstrates novelty.\n3.\tExperiments show that GIMF performs better on classic MOCO problems.", "weaknesses": "Some details and parameter settings were not explained clearly (see Questions below).", "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": "pIg0qAcfYZ", "reviewer": "Reviewer_4hxj", "summary": "This paper introduces a novel approach for MOCO through graph-image multimodal fusion. The framework incorporates a constructed coordinate image and efficient multimodal fusion. Experimental results on MOCO problems show the advance of the proposed GIMF.", "questions": "N/A.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. The GIMF framework successfully combines graph and image information, enriching representation learning for MOCO problems. \n\nS2. The PSAR strategy and modality-specific bottlenecks for multimodal fusion are well-justified and empirically validated.\n\nS3. Extensive experiments are conducted.", "weaknesses": "W1. The improvement achieved by the proposed methods appears to be marginal.\n\nW2. The computational cost of the proposed GIMF framework seems considerably higher than state-of-the-art methods like EMNH. It seems that the performance gains come from a cost of efficiency. \n\nW3. Constructing images seems relatively straightforward for TSP problems, but how does this approach generalize to other real-world scenarios? For some tasks, image construction may be challenging—how do the authors envision addressing this limitation?", "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)