Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning

2019-11-12 · Qiang Ma, Suwen Ge, Danyang He, Darshan Thaker, Iddo Drori

In this work, we introduce Graph Pointer Networks (GPNs) trained using reinforcement learning (RL) for tackling the traveling salesman problem (TSP). GPNs build upon Pointer Networks by introducing a graph embedding layer on the input, which captures relationships between nodes. Furthermore, to approximate solutions to constrained combinatorial optimization problems such as the TSP with time windows, we train hierarchical GPNs (HGPNs) using RL, which learns a hierarchical policy to find an optimal city permutation under constraints. Each layer of the hierarchy is designed with a separate reward function, resulting in stable training. Our results demonstrate that GPNs trained on small-scale TSP50/100 problems generalize well to larger-scale TSP500/1000 problems, with shorter tour lengths and faster computational times. We verify that for constrained TSP problems such as the TSP with time windows, the feasible solutions found via hierarchical RL training outperform previous baselines. In the spirit of reproducible research we make our data, models, and code publicly available.

📄 PDF Abstract BibTeX arXiv:1911.04936

Code (2)

qiang-ma/graph-pointer-network 공식 구현 pytorch

danifuertes/top_transformer pytorch

Tasks

Combinatorial OptimizationGraph Embedding Hierarchical Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)Traveling Salesman Problem

Hybrid Pointer Networks for Traveling Salesman Problems Optimization

2021-10-06 · Ahmed Stohy, Heba-Tullah Abdelhakam, Sayed Ali, Mohammed Elhenawy 외

In this work, a novel idea is presented for combinatorial optimization problems, a hybrid network, which results in a superior outcome. We applied this method to graph pointer networks [1], expanding its capabilities to …

Combinatorial Optimization Graph Embedding Traveling Salesman Problem

Solving the QAP by Two-Stage Graph Pointer Networks and Reinforcement Learning

2024-03-31 · Satoko Iida, Ryota Yasudo

Quadratic Assignment Problem (QAP) is a practical combinatorial optimization problems that has been studied for several years. Since it is NP-hard, solving large problem instances of QAP is challenging. Although heuristi…

Combinatorial Optimization Deep Learning Deep Reinforcement Learning Traveling Salesman Problem

Learning to Branch in Combinatorial Optimization with Graph Pointer Networks

2023-07-04 · Rui Wang, Zhiming Zhou, Tao Zhang, Ling Wang 외

Branch-and-bound is a typical way to solve combinatorial optimization problems. This paper proposes a graph pointer network model for learning the variable selection policy in the branch-and-bound. We extract the graph f…

Combinatorial Optimization Graph Neural Network Variable Selection

Multi-objective Pointer Network for Combinatorial Optimization

2022-04-25 · Le-yang Gao, Rui Wang, Chuang Liu, Zhao-hong Jia

Multi-objective combinatorial optimization problems (MOCOPs), one type of complex optimization problems, widely exist in various real applications. Although meta-heuristics have been successfully applied to address MOCOP…

Combinatorial Optimization Deep Reinforcement Learning reinforcement-learning Reinforcement Learning (RL)+1

Pointer Networks with Q-Learning for Combinatorial Optimization

2023-11-05 · Alessandro Barro

We introduce the Pointer Q-Network (PQN), a hybrid neural architecture that integrates model-free Q-value policy approximation with Pointer Networks (Ptr-Nets) to enhance the optimality of attention-based sequence genera…

Combinatorial Optimization Graph Embedding Q-Learning Reinforcement Learning (RL)