A Generative Graph Method to Solve the Travelling Salesman Problem

• URL: http://arxiv.org/abs/2007.04949v1
• Date: Thu, 9 Jul 2020 17:23:55 GMT
• Title: A Generative Graph Method to Solve the Travelling Salesman Problem
• Authors: Amal Nammouchi, Hakim Ghazzai, and Yehia Massoud
• Abstract summary: We propose to use the novel Graph Learning Network (GLN), a generative approach, to approximately solve the Travelling Salesman Problem (TSP) GLN model learns directly the pattern of TSP instances as training dataset, encodes the graph properties, and merge the different node embeddings to output node-to-node an optimal tour.
• Score: 1.552282932199974
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Travelling Salesman Problem (TSP) is a challenging graph task in combinatorial optimization that requires reasoning about both local node neighborhoods and global graph structure. In this paper, we propose to use the novel Graph Learning Network (GLN), a generative approach, to approximately solve the TSP. GLN model learns directly the pattern of TSP instances as training dataset, encodes the graph properties, and merge the different node embeddings to output node-to-node an optimal tour directly or via graph search technique that validates the final tour. The preliminary results of the proposed novel approach proves its applicability to this challenging problem providing a low optimally gap with significant computation saving compared to the optimal solution.

Related papers

• A GREAT Architecture for Edge-Based Graph Problems Like TSP [8.922883855120416]
  Graph neural networks (GNNs) are not well suited to operate on dense graphs, such as in routing problems. We propose a novel GNN-related edge-based neural model called Graph Edge Attention Network (GREAT) We show GREAT can produce sparse graphs while keeping most of the optimal edges.
  arXiv  Detail & Related papers  (2024-08-29T17:07:43Z)
• A GAN Approach for Node Embedding in Heterogeneous Graphs Using Subgraph Sampling [33.50085646298074]
  We propose a novel framework that combines Graph Neural Network (GNN) and Generative Adrial Network (GAN) to enhance classification for underrepresented node classes. The framework incorporates an advanced edge generation and selection module, enabling the simultaneous creation of synthetic nodes and edges.
  arXiv  Detail & Related papers  (2023-12-11T16:52:20Z)
• Symmetry-preserving graph attention network to solve routing problems at multiple resolutions [1.9304772860080408]
  We introduce the first-ever completely equivariant model and training to solve problems. It is essential to capture the multiscale structure of the input graph. We propose a Multiresolution scheme in combination with Equi Graph Attention network (mEGAT) architecture.
  arXiv  Detail & Related papers  (2023-10-24T06:22:20Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Deep Manifold Learning with Graph Mining [80.84145791017968]
  We propose a novel graph deep model with a non-gradient decision layer for graph mining. The proposed model has achieved state-of-the-art performance compared to the current models.
  arXiv  Detail & Related papers  (2022-07-18T04:34:08Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• GLAN: A Graph-based Linear Assignment Network [29.788755291070462]
  We propose a learnable linear assignment solver based on deep graph networks. The experimental results on a synthetic dataset reveal that our method outperforms state-of-the-art baselines. We also embed the proposed solver into a popular multi-object tracking (MOT) framework to train the tracker in an end-to-end manner.
  arXiv  Detail & Related papers  (2022-01-05T13:18:02Z)
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
  Data association across frames is at the core of Multiple Object Tracking (MOT) task. Existing methods mostly ignore the context information among tracklets and intra-frame detections. We propose a novel learnable graph matching method to address these issues.
  arXiv  Detail & Related papers  (2021-03-30T08:58:45Z)
• Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings [53.58077686470096]
  We propose an end-to-end graph learning framework, namely Iterative Deep Graph Learning (IDGL) for jointly and iteratively learning graph structure and graph embedding. Our experiments show that our proposed IDGL models can consistently outperform or match the state-of-the-art baselines.
  arXiv  Detail & Related papers  (2020-06-21T19:49:15Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  Graph representation learning has achieved a remarkable success in many graph-based applications, such as node classification, prediction, and community detection. However, for some kind of graph applications, such as graph compression and edge partition, it is very hard to reduce them to some graph representation learning tasks. In this paper, we propose to attack the graph ordering problem behind such applications by a novel learning approach.
  arXiv  Detail & Related papers  (2020-01-18T09:14:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.