A Pointer Network Based Deep Learning Algorithm for the Max-Cut Problem

被引：7
作者：
Gu, Shenshen [1 ]
Yang, Yue [1 ]
机构：
[1] Shanghai Univ, Sch Mechatron Engn & Automat, Shanghai, Peoples R China
来源：
NEURAL INFORMATION PROCESSING (ICONIP 2018), PT I | 2018年 / 11301卷
基金：
美国国家科学基金会;
关键词：
Max-cut problem; Pointer network; Supervised learning;
D O I：
10.1007/978-3-030-04167-0_22
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
The max-cut problem is one of the classic NP-hard combinatorial optimization problems. In order to solve this problem efficiently, the paper mainly studies the topic of using the pointer network to build a training model to solve the max-cut problem. Then, the network model is trained with supervised learning. The experimental results show that the network trained by this algorithm can obtain the approximate solution to the max-cut problem.
引用
收藏
页码：238 / 248
页数：11
相关论文
共 17 条
[1]  
[Anonymous], 2014, COMPUT SCI
[2]  
[Anonymous], 2018, INT C ADV COMP INT I
[3]  
[Anonymous], 2015, COMPUTER SCI
[4]   EXPERIMENTS IN QUADRATIC 0-1 PROGRAMMING [J].
BARAHONA, F ;
JUNGER, M ;
REINELT, G .
MATHEMATICAL PROGRAMMING, 1989, 44 (02) :127-137
[5]  
Bie T.D., 2006, J MACH LEARN RES, V7, P1409
[6]   An exact algorithm for MAX-CUT in sparse graphs [J].
Della Croce, F. ;
Kaminski, M. J. ;
Paschos, V. Th. .
OPERATIONS RESEARCH LETTERS, 2007, 35 (03) :403-408
[7]  
Deng L, 2013, INT CONF ACOUST SPEE, P8604, DOI 10.1109/ICASSP.2013.6639345
[8]  
Funabiki N, 1997, 1997 IEEE INTERNATIONAL CONFERENCE ON NEURAL NETWORKS, VOLS 1-4, P1260, DOI 10.1109/ICNN.1997.616215
[9]   The Implementation of a Pointer Network Model for Traveling Salesman Problem on a Xilinx PYNQ Board [J].
Gu, Shenshen ;
Hao, Tao ;
Yang, Shaofu .
ADVANCES IN NEURAL NETWORKS - ISNN 2018, 2018, 10878 :130-138
[10]   A semidefinite programming based polyhedral cut and price approach for the maxcut problem [J].
Krishnan, K ;
Mitchell, JE .
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2006, 33 (01) :51-71
12