PaperlayerView exact revision on arXiv

Source-linked AI summary

Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization

Minsu Kim, Junyoung Park, Jinkyoo Park

arXiv:2205.13209v2cs.LGstat.ML

TL;DR

COP solvers need fast near-optimal solutions, but general DRL-NCO training schemes that exploit shared structure remain limited. The paper introduces Sym-NCO, a regularization-based method using problem and solution symmetricities, and reports improved DRL-NCO performance across four CO tasks, including results against a conventional PCTSP solver. Its scope is currently centered on rotational symmetricity for Euclidean COPs.

  • Problem

    COPs are difficult because of NP-hardness, while DRL-NCO still lacks a general training scheme that exploits symmetricities shared across problems.

  • Method

    Sym-NCO regularizes existing DRL-NCO methods by using rotational problem symmetricity and solution symmetricity through specially designed REINFORCE baselines.

  • Results

    Sym-NCO improves existing DRL-NCO methods across TSP, CVRP, PCTSP, and OP, including a 0.95% TSP gap with greedy rollout and reported superiority to ILS in PCTSP.

  • Takeaways & Limitations

    The method can improve powerful CO models without architecture-level redesign, while exploiting symmetricities to support compact training and generalization.

  • Takeaways & Limitations

    The study uses rotational symmetricity for Euclidean COPs and leaves additional symmetricities and non-Euclidean graph COPs for future research.

Abstract

from arXiv · show

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.

1 Introduction

Combinatorial optimization requires fast near-optimal solutions because exact optimization is difficult, while existing DRL-NCO methods lack a general training scheme that exploits shared problem structure. Sym-NCO addresses this gap by regularizing existing solvers with problem and solution symmetricities.

  • COPs are NP-hard, making fast computation of near-optimal solutions practically important across applications such as routing, drug discovery, and semiconductor design.
  • NCO uses deep learning to solve COPs and includes reinforcement-learning methods among its major training schemes.
  • Sym-NCO is a general regularization-based training scheme that leverages problem and solution symmetricities in Euclidean COPs.
  • Problem symmetricity comes from rotational invariance, while solution symmetricity means distinct solutions can have identical output values.
  • Symmetricity provides a compact training space and an invariant representation that can improve training and generalization to unseen CO problems.
  • The method improves existing CO models without requiring architecture-level redesign, unlike equivariant neural-network schemes.

2 Symmetricity in Combinatorial Optimization Markov Decision Process

The CO-MDP formulates combinatorial optimization as sequential solution construction, with a policy selecting actions and receiving objective-based rewards. Within this framework, problem and solution symmetricities characterize equivalent instances and equal-valued solutions.

  • The CO-MDP represents a COP as sequential construction of a solution for a given problem instance.
  • A state contains the partial solution, node coordinates, and features, while an action selects an unvisited node.
  • The solver defines a probability distribution over complete solutions by multiplying the policy probabilities across construction steps.
  • Problem symmetricity holds when two problem instances have identical optimal solution sets.
  • Solution symmetricity holds when two solutions on the same problem have equal objective values.
  • Rotational problem symmetricity applies across Euclidean COPs, whereas solution symmetricity depends on the specific properties of each COP.

3 Symmetric Neural Combinatorial Optimization

Sym-NCO is a regularization-based training scheme that improves NCO solvers by exploiting solution and problem symmetricities. It combines symmetricity-aware REINFORCE baselines with invariant-representation regularization.

  • Sym-NCO framework: Sym-NCO leverages solution and problem symmetricities to improve existing CO models through a regularization-based training scheme.The scheme is designed to work with existing solver architectures rather than requiring architecture-level redesign.
  • Solution symmetricity: The solution-symmetricity loss uses a shared baseline equal to the average reward from multiple solutions sampled for the same problem.This creates competition among sampled rewards while reducing reward deviation within the solution group.
  • Relation to prior methods: POMO similarly seeks symmetric solutions by varying initial cities, but its reward sensitivity to first-city selection limits its standalone advantage beyond TSP.The paper identifies Lss as a way to further improve POMO on tasks including CVRP.
  • Problem symmetricity: The problem-symmetricity loss samples K solutions from each of L randomly rotated problems and averages their rewards into a shared baseline.Rotated problems are constructed with sampled orthogonal matrices because the original and rotated problems have identical solutions.
  • Invariant representation: Linv regularizes projected representations g(h(x)) and g(h(Q(x))) to impose rotational invariance while preserving encoder flexibility.The method penalizes differences after an MLP projection head rather than directly constraining hidden representations.
  • Invariant representation: Applying Linv improves projected-representation cosine similarity, whereas directly enforcing similarity on h degrades performance.The ablation supports preserving the encoder’s expression power while inducing invariance in the projected representation.

4 Related Works

Prior neural combinatorial optimization work includes deep construction heuristics and equivariant architectures. Sym-NCO differs by learning symmetricity through regularization without hard architectural constraints.

  • Deep construction heuristics: Deep NCO construction heuristics progressed from PointerNet actor-critic models to Transformer-based attention models that solve multiple routing problems.Attention Model is described as the de-facto standard NCO method and as problem-agnostic across routing tasks.
  • Equivariant deep learning: Equivariant NCO methods encode input symmetries through specialized GNN or Transformer architectures, whereas Sym-NCO uses regularization with existing CO models.The paper contrasts its approach with rule-based or architecture-level constraints used by prior equivariant methods.

5 Experiments

Experiments evaluate Sym-NCO across four CO tasks, multiple neural baselines, classical solvers, greedy and multi-start inference, real-world TSPLIB instances, and time-performance trade-offs. Sym-NCO consistently improves neural baselines, achieves strong solution quality and speed, and reaches the Pareto frontier in multi-start analysis.

  • Experimental setup: Experiments apply Sym-NCO to POMO, AM, and PointerNet across TSP, CVRP, PCTSP, and OP, including N = 100 benchmark problems and real-world TSPLIB instances.The study uses original network architectures and training hyperparameters for fair comparisons.
  • TSP and CVRP: Sym-NCO outperforms NCO baselines in TSP and CVRP under both greedy rollout and multi-start settings, with the fastest inference speed.In greedy TSP, Sym-NCO achieves a 0.95% gap and solves 10,000 instances in a few seconds.
  • PCTSP and OP: Sym-NCO outperforms NCO baselines in PCTSP and OP under both greedy rollout and multi-start settings, also surpassing the classical PCTSP baseline in multi-start evaluation.The supplied result passage reports a 43200… comparison but does not provide the complete value.
  • Generalization and time-performance: Sym-NCO significantly improves existing DRL-NCO methods and achieves the Pareto frontier across all benchmark datasets in time-performance analysis.The Pareto frontier represents the best solution quality among baselines within a given time consumption.

6 Discussion

The discussion finds that Sym-NCO’s projected-representation regularization improves symmetricity learning, while EGNN underperforms and fails to converge. The authors identify extensions to additional symmetricities, larger problems, and non-Euclidean graph COPs as future work.

  • Ablation Study of Linv: Linv increases cosine similarity of projected representations and contributes to performance improvements.Applying similarity directly to h degrades performance, so the encoder’s expression power should be preserved.
  • Comparison with EGNN: EGNN significantly underperforms Sym-NCO and fails to converge on the evaluated CO setting.The authors attribute this to the need for equivariant architectures tailored to fully connected Euclidean CO graphs with informative coordinates.
  • Comparison with EGNN: Sym-NCO can improve existing powerful NCO models without fine modification of their neural-network architectures.The discussion contrasts this with equivariant schemes that require architecture-level redesign.
  • Extended problem symmetricities: Scaling and translating problem coordinates are additional symmetricities that may further enhance Sym-NCO but remain future work.The current work employs rotational symmetricity as its problem symmetricity.
  • Large scale adaptation: Large-scale adaptation is demonstrated using effective active search, while curriculum and meta-learning are suggested for larger problems.The authors frame Sym-NCO as having scale-adaptation capability but identify broader generalization to larger sizes as an open direction.
  • Extension to the graph COP: Universal symmetricities for non-Euclidean COPs and their application to graph COP models remain open research directions.The paper specifically identifies asymmetric TSP and existing graph-COP NCO models as settings for future extension.

A Proof of Theorem 2.1

The proof establishes that orthogonal transformations preserve the optimal value and solution set of Euclidean combinatorial optimization problems. It uses reward dependence on solution sequences, pairwise distances, and node features to show invariance under transformation.

  • Theorem statement: For an orthogonal matrix Q, the transformed problem Q(P) has the same optimal solutions as P.The transformation satisfies QQ^T = Q^TQ = I.
  • Reward invariance: The reward depends on solution sequences, pairwise distances, and node features.This structure enables the proof to compare rewards before and after orthogonal transformation.
  • Optimal-value invariance: Orthogonal transformation preserves the optimal value because Euclidean pairwise distances remain unchanged.The proof equates the transformed reward with the original reward for an optimal solution.
  • Solution-set equivalence: Every optimal solution of Q(P) has the same optimal value as P, and conversely every optimal solution of P has the same value under Q(P).The two directions establish equality of the optimal solution sets.

B Implementation of Baselines

The implementation reproduces PointerNet, AM, and POMO as baseline DRL-NCO methods, using their established architectures and hyperparameter settings for the relevant routing tasks.

  • Baseline methods: The study directly reproduces POMO, AM, and PointerNet as competitive DRL-NCO baselines.These methods cover the baseline architectures used throughout the experiments.
  • PointerNet: PointerNet uses an LSTM encoder-decoder trained with an actor-critic approach.The implementation follows the corresponding open-source instructions and hyperparameters.
  • AM: AM is a transformer-based encoder-decoder model evaluated on TSP, CVRP, PCTSP, and OP.Its implementation follows the open-source instructions and specified hyperparameters.
  • POMO: POMO is a high-performance DRL-NCO model for TSP and CVRP built on AM.The implementation follows POMO’s open-source instructions and hyperparameters.

C.1 Training Hyperparameters

Sym-NCO is integrated with existing DRL-NCO models by replacing the REINFORCE baseline with symmetry-aware terms and sampling transformed instances. The implementation combines problem and solution symmetricity according to task knowledge, while limited hyperparameter tuning slightly favors α = 0.2 over α = 0.1.

  • Integration: Sym-NCO preserves the baseline architectures and hyperparameters except for the proposed REINFORCE baseline.It is attached on top of PointerNet, AM, and POMO rather than requiring new solver architectures.
  • POMO settings: POMO uses β = 1 to impose solution symmetricity on top of its existing baseline.The implementation follows POMO’s first-node restriction only for TSP.
  • Loss design: Lps combines problem and solution symmetricity, while β controls the additional solution-symmetricity term Lss.β = 1 is recommended when task-specific solution symmetricity is known; β = 0 is used without such domain knowledge.
  • Instance augmentation: Sym-NCO samples multiple solutions from rotated, reflected, or randomly orthogonally transformed instances.Random orthogonal transformations are used for PCTSP and OP with M = 200.
  • Projection head: The projection head is a two-layer ReLU MLP with input, output, and hidden dimensions equal to 128.The dimensions match the encoder embedding dimension.
  • Training resources: Training requires substantial compute, including approximately two weeks for POMO + Sym-NCO and three days for AM + Sym-NCO.POMO uses one A100 GPU, while AM uses four A100 GPUs.
  • Hyperparameter tuning: α = 0.2 gives slightly better CVRP performance than α = 0.1, but tuning α appears not sensitive.The study reports only a simple α ablation because training resources limited broader hyperparameter tuning.

D.2 Performance Evaluation on TSPLIB

Sym-NCO is evaluated on real-world TSPLIB instances, with the section reporting a comparison against POMO.

  • Sym-NCO outperforms POMO on TSPLIB instances with N < 250.The evaluation uses multi-start sampling with width M = N × 20.

D.3 Performance Evaluation of Transferability to Large Scale Problems

Sym-NCO transfers to large-scale problems and improves performance or adaptation efficiency relative to relevant neural and conventional baselines. The method also compares favorably with prior symmetry-aware approaches while covering diverse CO tasks without labeled data.

  • Large-scale transfer: Sym-NCO outperforms POMO in large-scale CVRP, with only a small performance gap relative to LKH3.The evaluation uses ten randomly generated CVRP instances.
  • Large-scale transfer: 5 × reduced training shot K is sufficient for Sym-NCO to achieve better large-scale-task performance than POMO.The result concerns few-shot adaptation after transfer learning.
  • Comparison with improvement heuristics: Sym-NCO outperforms state-of-the-art deep improvement heuristics with the fastest speed.The comparison varies the number of iterations I and samples per instance s; speed evaluations use different GPUs across methods.
  • Comparison with improvement heuristics: Sym-NCO and improvement heuristics are complementary and can support each other.Sym-NCO is characterized as a constructive method, whereas the compared approach is an improvement method.
  • Comparison with symmetric NCO models: Unlike a prior rule-based equivariant approach, Sym-NCO approximately imposes symmetricity through a regularization loss term and is intended as a more general approach.The paper notes that not every task can be represented using relative position from the first visited city.
  • Comparison with symmetric NCO models: Sym-NCO covers the widest range of CO tasks among the compared methods without requiring labeled data.The paper reports that Sym-NCO outperforms all relevant related baselines.
Loading 2205.13209v2…