Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization

Minsu KimJunyoung ParkJinkyoo Park

article2022NeurIPS197 citations

Proposes a general reinforcement learning training scheme that exploits rotational and reflectional symmetries across combinatorial optimization problems, significantly boosting solver generalization across tasks like the traveling salesman and vehicle routing problems without requiring domain-specific heuristics.

Listen

Combinatorial optimization problems, such as vehicle routing and scheduling, are central to industrial operations in logistics, supply chains, and semiconductor design. While deep reinforcement learning methods have emerged as promising tools to solve these complex problems rapidly without relying on handcrafted rules or labeled training data, they continue to lag behind traditional solvers in solution quality and generalizability. Closing this performance gap is crucial for organizations seeking automated, highly efficient decision-making systems.

The article introduces and evaluates Sym-NCO, a training scheme designed to improve the performance of deep reinforcement learning models on combinatorial optimization tasks. The method systematically embeds universal geometric symmetries—specifically rotational invariance in problem layouts and solution symmetries—into existing neural network solvers without requiring alterations to their underlying neural architectures.

The authors implemented Sym-NCO across multiple standard neural models and evaluated them on 10,000 benchmark instances across four classic problem types: the traveling salesman problem, capacitated vehicle routing, prize-collecting traveling salesman, and orienteering problems, comparing results against leading traditional heuristics and deep learning baselines.

The evaluation produced several key findings. First, Sym-NCO consistently established state-of-the-art performance among neural constructive methods across all four evaluated problem domains. Second, in the prize-collecting traveling salesman problem, Sym-NCO matched and slightly exceeded the solution quality of a leading conventional heuristic, iterative local search, while operating approximately 240 times faster. Third, in real-world benchmark tests, Sym-NCO achieved tighter optimality gaps than existing reinforcement learning models while remaining on the best time-versus-cost trade-off curve across all test scenarios.

These results demonstrate that enforcing symmetric geometric relationships during training allows neural solvers to achieve higher solution quality and faster inference speeds without costly structural redesigns. For enterprise operations, this translates to faster operational turnaround times, lower computational costs, and potential reductions in logistics expenses and carbon emissions, while mitigating the need to maintain cumbersome problem-specific heuristics.

Organizations developing or deploying neural optimization systems should consider adopting regularizer-based symmetry training to enhance existing models. Further research should focus on extending symmetry regularization to non-Euclidean problem domains, such as asymmetric routing, and scaling the method to larger problem sizes via curriculum- or meta-learning approaches.

While confidence in the reported performance gains is supported by standardized benchmarks, the primary limitations include a current focus on two-dimensional Euclidean problems with rotational symmetries and problem instances capped around 100 to 250 nodes. Decision-makers should validate performance on their specific large-scale or non-Euclidean operational datasets before broad deployment.

Korea Advanced Institute of Science and Technology combinatorial optimization combinatorial problems optimization problems Symmetric Neural Combinatorial Optimization Sym-NCO combinatorial optimization problems

arXiv: 2205.13209 alstn12088/Sym-NCO

Paper: Attention, Learn to Solve Routing Problems!, Wouter Kool et al. (2018). This foundational paper establishes the attention-based encoder-decoder and reinforcement learning framework for routing problems (TSP, CVRP, PCTSP, OP) that Sym-NCO directly adopts and enhances with symmetry regularizers.
Paper: Neural Combinatorial Optimization with Reinforcement Learning, Irwan Bello et al. (2016). It pioneers the neural combinatorial optimization (NCO) framework using policy gradients to train neural solvers without supervised labels, forming the direct conceptual basis of DRL-NCO.
Paper: Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon, Yoshua Bengio et al. (2018). This survey provides a comprehensive methodological taxonomy of machine learning methods applied to discrete optimization that underpins the formulation and problem scope studied in Sym-NCO.
Paper: Learning Combinatorial Optimization Algorithms over Graphs, Elias Boutros Khalil et al. (2017). It introduces deep reinforcement learning over graph embeddings to solve combinatorial problems greedily, establishing key principles for graph-based NCO representations.

Paper: Combinatorial Optimization and Reasoning with Graph Neural Networks, Quentin Cappart et al. (2023). This survey analyzes subsequent advancements in graph neural networks for combinatorial optimization, explicitly examining how symmetry and algorithmic reasoning can be generalized across primal and dual solver pipelines.

Cover for Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization

Abstract

Deep reinforcement learning (DRL)-based combinatorial optimization (CO) methods (i.e., DRL-NCO) have shown significant merit over the conventional CO solvers as DRL-NCO is capable of learning CO solvers less relying on problem-specific expert domain knowledge (heuristic method) and supervised labeled data (supervised learning method). This paper presents a novel training scheme, Sym-NCO, which is a regularizer-based training scheme that leverages universal symmetricities in various CO problems and solutions. Leveraging symmetricities such as rotational and reflectional invariance can greatly improve the generalization capability of DRL-NCO because it allows the learned solver to exploit the commonly shared symmetricities in the same CO problem class. Our experimental results verify that our Sym-NCO greatly improves the performance of DRL-NCO methods in four CO tasks, including the traveling salesman problem (TSP), capacitated vehicle routing problem (CVRP), prize collecting TSP (PCTSP), and orienteering problem (OP), without utilizing problem-specific expert domain knowledge. Remarkably, Sym-NCO outperformed not only the existing DRL-NCO methods but also a competitive conventional solver, the iterative local search (ILS), in PCTSP at 240× faster speed. Our source code is available at https://github.com/alstn12088/Sym-NCO.

Topics

combinatorial optimization combinatorial problems optimization problems

Keywords

Symmetric Neural Combinatorial Optimization Sym-NCO combinatorial optimization problems symmetricity regularization deep constructive heuristics policy optimization iterative local search pointer network

1 Introduction
2 Symmetricity in Combinatorial Optimization Markov Decision Process
2.1 Combinatorial Optimization Markov Decision Process
2.2 Symmetricities in CO-MDP
3 Symmetric Neural Combinatorial Optimization
3.1 Regularizing REINFORCE with Problem and Solution Symmetricities via L_sym-RL
3.2 Learning Invariant Representation with Pre-identified Symmetricity: L_inv
4 Related Works
5 Experiments
5.1 Tasks and Baseline Selections
5.2 Experimental Setting
5.3 Performance Metrics
5.4 Experimental Results
6 Discussion
6.1 Discussion of Regularization-Based Symmetricity Learning
6.2 Limitations & Future Directions
6.3 Social Impacts
Acknowledgments and Disclosure of Funding
References

Knowls

Knowl 1 — Sym-NCO joint regularized training objective
model/method
Symmetric Neural Combinatorial Optimization (Sym-NCO) is a training scheme for an existing encoder-decoder deep reinforcement-learning combinatorial optimizer. For solver parameters $\theta$ , Sym-NCO minimizes a weighted sum of three losses:
$L_{\mathrm{total}}(\theta)=L_{\mathrm{ps}}(\theta)+\beta L_{\mathrm{ss}}(\theta)+\alpha L_{\mathrm{inv}}(\theta),$
where $L_{\mathrm{ss}}$ is a REINFORCE loss using multiple solutions of one problem to exploit solution symmetricity, $L_{\mathrm{ps}}$ is a REINFORCE loss using multiple rotationally transformed versions of a problem to exploit problem symmetricity, and $L_{\mathrm{inv}}$ encourages rotationally invariant encoder representations. The coefficients $\alpha,\beta\in[0,1]$ control the strengths of the representation-invariance and solution-symmetricity terms. Sym-NCO changes the training losses rather than requiring a specially designed equivariant network architecture, so it can be applied to existing neural combinatorial optimization solvers.
Knowl 2 — Problem and solution symmetricity in Euclidean combinatorial optimization
theoretical result
Let a Euclidean combinatorial optimization instance be $P=(x,f)$ , where $x=\{x_i\}_{i=1}^{N}$ contains the coordinates of $N$ nodes and $f=\{f_i\}_{i=1}^{N}$ contains their node features. Two problem instances are problem-symmetric when their sets of optimal solutions are identical. Two candidate solutions $\pi^i$ and $\pi^j$ are solution-symmetric on instance $P$ when they have the same objective value:
$R(\pi^i;P)=R(\pi^j;P),$
where $R$ is the reward corresponding to the optimization objective.

For every orthogonal matrix $Q\in\mathbb{R}^{d\times d}$ satisfying $Q^{\mathsf T}Q=I_d$ , define the rotated instance by
$Q(P)=\big(\{Qx_i\}_{i=1}^{N},f\big).$
The original instance $P$ and the rotated instance $Q(P)$ are problem-symmetric: they have identical optimal solution sets because orthogonal transformations preserve Euclidean distances. This rotational symmetricity is the pre-identified problem symmetry used by Sym-NCO.
Knowl 3 — Competitive REINFORCE for solution symmetricity
equation
For a fixed combinatorial optimization instance $P$ , the solution-symmetricity loss is the negative expected reward under solver policy $F_\theta$ :
$L_{\mathrm{ss}}=-\mathbb{E}_{\pi\sim F_\theta(\cdot\mid P)}[R(\pi;P)].$
During training, sample $K$ solutions $\{\pi^k\}_{k=1}^{K}$ from the same policy and the same instance, and use their mean reward as a shared baseline,
$b(P)=\frac{1}{K}\sum_{k=1}^{K}R(\pi^k;P).$
The REINFORCE gradient is estimated as
$\nabla_\theta L_{\mathrm{ss}}\approx -\frac{1}{K}\sum_{k=1}^{K}\left[R(\pi^k;P)-\frac{1}{K}\sum_{j=1}^{K}R(\pi^j;P)\right]\nabla_\theta\log F_\theta(\pi^k\mid P).$
Here $R(\pi^k;P)$ is the reward of sampled solution $\pi^k$ , and $\log F_\theta(\pi^k\mid P)$ is its policy log-likelihood. The sampled advantages sum to zero, so the solutions compete against one another: low-reward solutions are pushed upward while higher-reward solutions are also encouraged to improve. The intended effect is a solution group with high rewards and smaller reward variation, approximating solution symmetricity without requiring problem-specific knowledge about which solutions should be equivalent.
Knowl 4 — Rotationally augmented REINFORCE for problem symmetricity
equation
Let $Q$ be a distribution over random orthogonal matrices, and sample $L$ matrices $Q_1,\ldots,Q_L$ . For each transformed instance $Q_l(P)$ , sample $K$ solutions $\pi^{l,1},\ldots,\pi^{l,K}$ from $F_\theta(\cdot\mid Q_l(P))$ . Because rotation preserves the Euclidean objective, the problem-symmetricity loss evaluates these solutions on the original instance objective:
$L_{\mathrm{ps}}=-\mathbb{E}_{Q}\,\mathbb{E}_{\pi\sim F_\theta(\cdot\mid Q(P))}[R(\pi;P)].$
Its Monte Carlo REINFORCE gradient uses one baseline shared across all $LK$ samples:
$\nabla_\theta L_{\mathrm{ps}}\approx -\frac{1}{LK}\sum_{l=1}^{L}\sum_{k=1}^{K}\left[R(\pi^{l,k};P)-\frac{1}{LK}\sum_{u=1}^{L}\sum_{v=1}^{K}R(\pi^{u,v};P)\right]\nabla_\theta\log F_\theta(\pi^{l,k}\mid Q_l(P)).$
The shared baseline creates competition not only among solutions sampled from the same rotated instance but also among solutions generated from different rotations. Thus, the solver is trained to produce similarly strong solutions for rotationally equivalent inputs while simultaneously exploiting solution symmetricity through the multiple samples per rotation.
Knowl 5 — Projected rotational-invariance regularization
model/method
Let $h_\theta(x)$ be the encoder representation of node coordinates $x$ , let $Q(x)=\{Qx_i\}_{i=1}^{N}$ be a rotated coordinate set, and let $g$ be an MLP projection head. Sym-NCO adds the loss
$L_{\mathrm{inv}}=-S_{\mathrm{cos}}\big(g(h_\theta(x)),g(h_\theta(Q(x)))\big),$
where $S_{\mathrm{cos}}(a,b)=a^{\mathsf T}b/(\lVert a\rVert\lVert b\rVert)$ is cosine similarity for nonzero vectors $a$ and $b$ . Minimizing this loss makes the projected representations of an instance and its rotation similar. The similarity constraint is imposed after the projection head rather than directly on $h_\theta$ , allowing the encoder representation to retain task-relevant diversity while encouraging the invariant information needed by the policy.
Knowl 6 — Combinatorial optimization Markov decision process used for training
model/method
The solver treats solution construction as a finite-horizon Markov decision process. A problem instance is $P=(x,f)$ with $N$ nodes; at construction step $t$ , the state contains the partially selected sequence $a_{1:t-1}$ together with all coordinates and node features, and the action $a_t$ selects one unvisited node from
$\mathcal{A}_t=\{1,\ldots,N\}\setminus\{a_1,\ldots,a_{t-1}\}.$
The completed sequence is the solution $\pi=(a_1,\ldots,a_T)$ , where $T$ is the maximum number of construction steps. An instance-conditioned policy factors as
$F_\theta(\pi\mid P)=\prod_{t=1}^{T}p_\theta(a_t\mid s_t),$
where $s_t$ is the partial solution state and $p_\theta$ is the action distribution. The training objective is
$\theta^*=\arg\max_\theta\;\mathbb{E}_{P\sim\rho}\,\mathbb{E}_{\pi\sim F_\theta(\cdot\mid P)}[R(\pi;P)],$
with $\rho$ the problem-generation distribution. The reward depends on the selected sequence, pairwise Euclidean distances, and node features. It is negative tour length for TSP, CVRP, and PCTSP, and total collected prize for OP.
Knowl 7 — Experimental protocol across four routing problems
experimental setup
Sym-NCO was evaluated on four Euclidean routing tasks with $N=100$ : traveling salesman problem (TSP), capacitated vehicle routing problem (CVRP), prize-collecting TSP (PCTSP), and orienteering problem (OP). It was applied on top of POMO for TSP and CVRP, on top of the Attention Model (AM) for PCTSP and OP, and additionally on top of PointerNet for TSP. The underlying network architectures and training hyperparameters were kept the same as those of the corresponding base methods.

The experiments used the benchmark instance distribution employed by the AM work, Nvidia A100 GPUs for neural training, and an Intel Xeon E5-2630 CPU together with an Nvidia RTX2080Ti GPU for inference-time comparisons. Average objective values were computed over 10,000 benchmark instances. Neural solvers were evaluated both with greedy decoding, which measures single-start performance, and with multi-start sampling or post-processing, which trades additional inference time for solution quality. Real-world generalization was also evaluated on TSPLIB instances with $50<N<250$ .
Knowl 8 — Sym-NCO performance on TSP and CVRP
data/table
The following key entries compare classical solvers and neural constructive solvers on 10,000 randomly generated instances with $N=100$ . Cost and optimality gap are minimized; time is inference time. Greedy decoding uses one rollout, while multi-start entries use the indicated sampling or search procedure. The gaps are relative to the best classical reference for each task.
Could not parse LaTeX table
Sym-NCO improves on the neural baselines in both decoding regimes. In greedy decoding it retains the fastest neural inference times while reducing the TSP gap to $0.94\%$ and the CVRP gap to $2.88\%$ . With multi-start sampling, it obtains the best neural costs shown for both tasks without increasing the time over POMO: $7.79$ for TSP in $13\text{s}$ and $15.87$ for CVRP in $16\text{s}$ .
Knowl 9 — Sym-NCO performance on PCTSP and OP
data/table
On $N=100$ PCTSP and OP instances, Sym-NCO was compared with the classical baselines ILS and Compass and with AM and MDAM. PCTSP cost and gap are minimized; OP collected objective and gap are maximized. Greedy results use zero-shot single decoding, while multi-start results use post-processing or repeated sampling.
Could not parse LaTeX table
Sym-NCO is the strongest neural method in both decoding regimes. Its multi-start PCTSP cost is $5.98$ with a reported gap of $-0.02\%$ , matching or slightly exceeding the ILS reference while taking $3\text{m}$ instead of $12\text{h}$ . This corresponds to approximately $240\times$ faster inference. On OP, Sym-NCO reaches objective $33.04$ with a $0.45\%$ gap in $3\text{m}$ , improving on the neural baselines while remaining much faster than their multi-start procedures.
Knowl 10 — Generalization, architecture transfer, and ablation findings
empirical result
Sym-NCO improved three different base neural solvers—PointerNet, AM, and POMO—when applied to TSP with $N=100$ , showing that the gains are not tied to one particular encoder-decoder architecture. On real-world TSPLIB instances, the reported optimality gap was $1.62\%$ for Sym-NCO versus $1.87\%$ for POMO. Across TSP, CVRP, PCTSP, and OP, time-versus-quality comparisons placed Sym-NCO on the observed Pareto frontier: for a given inference-time budget, it achieved the best solution quality among the compared methods.

Ablations showed that adding $L_{\mathrm{inv}}$ improved optimization and increased cosine similarity between projected representations of original and rotated inputs. Applying the similarity constraint directly to the encoder representation $h$ rather than through the projection head degraded performance, supporting the use of an MLP projection head to preserve encoder expressiveness. A comparison using an EGNN encoder with six layers and 128 hidden dimensions, while retaining the POMO decoder, substantially underperformed Sym-NCO and failed to converge reliably. The results therefore support the paper's claim that regularization can exploit rotational symmetry while retaining a strong non-equivariant neural architecture.

Coverage note — Omitted the paper's future directions on additional symmetries, larger-scale adaptation, non-Euclidean graph problems, and social impacts because they are limitations or prospective extensions rather than demonstrated core contributions.

References

1.Stefan Irnich, Paolo Toth, and Daniele Vigo. Chapter 1: The Family of Vehicle Routing Problems, pages 1–33.
2.Matthew Veres and Medhat Moussa. Deep learning for intelligent transportation systems: a survey of emerging trends. IEEE Transactions on Intelligent Transportation Systems, 21(8):3152–3168, 2020.
3.Sungsoo Ahn, Junsu Kim, Hankook Lee, and Jinwoo Shin. Guiding deep molecular optimization with genetic exploration. Advances in neural information processing systems, 33:12008–12021, 2020.
4.Sungsoo Ahn, Binghong Chen, Tianzhe Wang, and Le Song. Spanning tree-based graph generation for molecules. In International Conference on Learning Representations, 2021.
5.Azalia Mirhoseini, Hieu Pham, Quoc V. Le, Benoit Steiner, Rasmus Larsen, Yuefeng Zhou, Naveen Kumar, Mohammad Norouzi, Samy Bengio, and Jeff Dean. Device placement optimization with reinforcement learning. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 2430–2439. PMLR, 06–11 Aug 2017.
6.Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Jiang, Ebrahim M. Songhori, Shen Wang, Young-Joon Lee, Eric Johnson, Omkar Pathak, Sungmin Bae, Azade Nazi, Jiwoo Pak, Andy Tong, Kavya Srinivasa, William Hang, Emre Tuncer, Anand Babu, Quoc V. Le, James Laudon, Richard C. Ho, Roger Carpenter, and Jeff Dean. Chip placement with deep reinforcement learning. CoRR, abs/2004.10746, 2020.
7.Haiguang Liao, Qingyi Dong, Xuliang Dong, Wentai Zhang, Wangyang Zhang, Weiyi Qi, Elias Fallon, and Levent Burak Kara. Attention routing: track-assignment detailed routing using attention-based reinforcement learning, 2020.
8.Minsu Kim, Hyunwook Park, Seongguk Kim, Keeyoung Son, Subin Kim, Kyunjune Son, Seonguk Choi, Gapyeol Park, and Joungho Kim. Reinforcement learning-based auto-router considering signal integrity. In 2020 IEEE 29th Conference on Electrical Performance of Electronic Packaging and Systems (EPEPS), pages 1–3, 2020.
9.Minsu Kim, Hyunwook Park, Keeyoung Son, Seongguk Kim, Haeyeon Kim, Jihun Kim, Jinwook Song, Youngmin Ku, Jounggyu Park, and Joungho Kim. Imitation learning for simultaneous escape routing. In 2021 IEEE 30th Conference on Electrical Performance of Electronic Packaging and Systems (EPEPS), pages 1–3, 2021.
10.Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28, pages 2692–2700. Curran Associates, Inc., 2015.
11.Chaitanya K. Joshi, Quentin Cappart, Louis-Martin Rousseau, Thomas Laurent, and Xavier Bresson. Learning tsp requires rethinking generalization, 2020.
12.Wouter Kool, Herke van Hoof, Joaquim A. S. Gromicho, and Max Welling. Deep policy dynamic programming for vehicle routing problems. CoRR, abs/2102.11756, 2021.
13.Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize a small pre-trained model to arbitrarily large tsp instances, 2020.
14.André Hottung, Bhanu Bhandari, and Kevin Tierney. Learning a latent search space for routing problems using variational autoencoders. In International Conference on Learning Representations, 2020.
15.André Hottung and Kevin Tierney. Neural large neighborhood search for the capacitated vehicle routing problem. CoRR, abs/1911.09539, 2019.
16.Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuristics for solving routing problems, 2020.
17.Paulo R d O da Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akcay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In Sinno Jialin Pan and Masashi Sugiyama, editors, Proceedings of The 12th Asian Conference on Machine Learning, volume 129 of Proceedings of Machine Learning Research, pages 465–480, Bangkok, Thailand, 18–20 Nov 2020. PMLR.
18.Sungsoo Ahn, Younggyo Seo, and Jinwoo Shin. Learning what to defer for maximum independent sets. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 134–144. PMLR, 13–18 Jul 2020.
19.Minsu Kim, Jinkyoo Park, and Joungho Kim. Learning collaborative policies to solve np-hard routing problems. In Advances in Neural Information Processing Systems, 2021.
20.Irwan Bello, Hieu Pham, Quoc V. Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning, 2017.
21.Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019.
22.Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. Advances in neural information processing systems, 31, 2018.
23.Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:21188–21198, 2020.
24.Junyoung Park, Jaehyeong Chun, Sang Hun Kim, Youngkook Kim, and Jinkyoo Park. Learning to schedule job-shop problems: representation and policy learning using graph neural network and reinforcement learning. International Journal of Production Research, 59(11):3360–3377, 2021.
25.Yining Ma, Jingwen Li, Zhiguang Cao, Wen Song, Le Zhang, Zhenghua Chen, and Jing Tang. Learning to iteratively solve routing problems with dual-aspect collaborative transformer. Advances in Neural Information Processing Systems, 34, 2021.
26.Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Multi-decoder attention model with embedding glimpse for solving vehicle routing problems. In Proceedings of 35th AAAI Conference on Artificial Intelligence, pages 12042–12049, 2021.
27.Junyoung Park, Sanjar Bakhtiyar, and Jinkyoo Park. Schedulenet: Learn to solve multi-agent scheduling problems with reinforcement learning. arXiv preprint arXiv:2106.03051, 2021.
28.Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. In Advances in Neural Information Processing Systems, 2019.
29.Hansen Wang, Zefang Zong, Tong Xia, Shuyu Luo, Meng Zheng, Depeng Jin, and Yong Li. Rewriting by generating: Learn heuristics for large-scale vehicle routing problems, 2021.
30.Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3):229–256, 1992.
31.Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pages 1597–1607. PMLR, 2020.
32.Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30, pages 5998–6008. Curran Associates, Inc., 2017.
33.Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permutation invariant graph generation via score-based generative modeling. In International Conference on Artificial Intelligence and Statistics, pages 4474–4484. PMLR, 2020.
34.Fabian Fuchs, Daniel Worrall, Volker Fischer, and Max Welling. Se (3)-transformers: 3d roto-translation equivariant attention networks. Advances in Neural Information Processing Systems, 33:1970–1981, 2020.
35.Vıéctor Garcia Satorras, Emiel Hoogeboom, and Max Welling. E (n) equivariant graph neural networks. In International Conference on Machine Learning, pages 9323–9332. PMLR, 2021.
36.Elise van der Pol, Daniel Worrall, Herke van Hoof, Frans Oliehoek, and Max Welling. Mdp homomorphic networks: Group symmetries in reinforcement learning. Advances in Neural Information Processing Systems, 33:4199–4210, 2020.
37.Wenbin Ouyang, Yisen Wang, Paul Weng, and Shaochen Han. Generalization in deep rl for tsp problems via equivariance and local search. arXiv preprint arXiv:2110.03595, 2021.
38.Benjamin Hudson, Qingbiao Li, Matthew Malencia, and Amanda Prorok. Graph neural network guided local search for the traveling salesperson problem. arXiv preprint arXiv:2110.05291, 2021.
39.Vašek Chvátal David Applegate, Robert Bixby and William Cook. Concorde tsp solver.
40.Keld Helsgaun. An extension of the lin-kernighan-helsgaun tsp solver for constrained traveling salesman and vehicle routing problems. 12 2017.
41.Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30, pages 6348–6358. Curran Associates, Inc., 2017.
42.Gorka Kobeaga, María Merino, and Jose A Lozano. An efficient evolutionary algorithm for the orienteering problem. Computers & Operations Research, 90:42–59, 2018.
43.Gerhard Reinelt. Tsplib—a traveling salesman problem library. ORSA journal on computing, 3(4):376–384, 1991.
44.André Hottung, Yeong-Dae Kwon, and Kevin Tierney. Efficient active search for combinatorial optimization problems. arXiv preprint arXiv:2106.05126, 2021.
45.Michal Lisicki, Arash Afkanpour, and Graham W Taylor. Evaluating curriculum learning strategies in neural combinatorial optimization. arXiv preprint arXiv:2011.06188, 2020.
46.Thomas Barrett, William Clements, Jakob Foerster, and Alex Lvovsky. Exploratory combinatorial optimization with reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3243–3250, 2020.
47.Iddo Drori, Anant Kharkar, William R Sickinger, Brandon Kates, Qiang Ma, Suwen Ge, Eden Dolev, Brenda Dietrich, David P Williamson, and Madeleine Udell. Learning to solve combinatorial optimization problems on real-world graphs in linear time. In 2020 19th IEEE International Conference on Machine Learning and Applications (ICMLA), pages 19–24. IEEE, 2020.
48.Thomas D Barrett, Christopher WF Parsonson, and Alexandre Laterre. Learning to solve combinatorial graph partitioning problems via efficient exploration. arXiv preprint arXiv:2205.14105, 2022.
49.Shenshen Gu and Yue Yang. A deep learning algorithm for the max-cut problem based on pointer network structure with supervised learning and reinforcement learning strategies. Mathematics, 8(2), 2020.
50.Kenshin Abe, Zijian Xu, Issei Sato, and Masashi Sugiyama. Solving np-hard problems on graphs with extended alphago zero. arXiv preprint arXiv:1905.11623, 2019.
51.Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. Advances in neural information processing systems, 31, 2018.

Citation

MLA

Kim, M., et al. “Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization”. Advances in Neural Information Processing Systems, vol. 35, 2022, pp. 1936–49, https://proceedings.neurips.cc/paper_files/paper/2022/file/0cddb777d3441326544e21b67f41bdc8-Paper-Conference.pdf.

APA

Kim, M., Park, J., & Park, J. (2022). Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization. Advances in Neural Information Processing Systems, 35, 1936–1949. https://proceedings.neurips.cc/paper_files/paper/2022/file/0cddb777d3441326544e21b67f41bdc8-Paper-Conference.pdf

Chicago

Kim, M., J. Park, and J. Park. 2022. “Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization”. Advances in Neural Information Processing Systems 35: 1936–49. https://proceedings.neurips.cc/paper_files/paper/2022/file/0cddb777d3441326544e21b67f41bdc8-Paper-Conference.pdf.

Harvard

Kim, M., Park, J. and Park, J. (2022) “Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization”, Advances in Neural Information Processing Systems. Curran Associates, Inc., pp. 1936–1949. Available at: https://proceedings.neurips.cc/paper_files/paper/2022/file/0cddb777d3441326544e21b67f41bdc8-Paper-Conference.pdf.

Vancouver

1. Kim M, Park J, Park J (2022) Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization. In: Advances in Neural Information Processing Systems. Curran Associates, Inc., pp 1936–1949

BibTeX

@inproceedings{kim2022sym,
  title = {Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization},
  author = {Kim, Minsu and Park, Junyoung and Park, Jinkyoo},
  year = {2022},
  booktitle = {Advances in Neural Information Processing Systems},
  publisher = {Curran Associates, Inc.},
  volume = {35},
  pages = {1936-1949},
  url = {https://proceedings.neurips.cc/paper_files/paper/2022/file/0cddb777d3441326544e21b67f41bdc8-Paper-Conference.pdf}
}

Metadata:DOI registry

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Authors

Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Sym-NCO joint regularized training objective

Knowl 2 — Problem and solution symmetricity in Euclidean combinatorial optimization

Knowl 3 — Competitive REINFORCE for solution symmetricity

Knowl 4 — Rotationally augmented REINFORCE for problem symmetricity

Knowl 5 — Projected rotational-invariance regularization

Knowl 6 — Combinatorial optimization Markov decision process used for training

Knowl 7 — Experimental protocol across four routing problems

Knowl 8 — Sym-NCO performance on TSP and CVRP

Knowl 9 — Sym-NCO performance on PCTSP and OP

Knowl 10 — Generalization, architecture transfer, and ablation findings

References

Citation

BibTeX

Source Code

Access the Paper