Augmentative Message Passing for Traveling Salesman Problem and Graph Partitioning
원문 초록
The cutting plane method is an augmentative constrained optimization procedure that is often used with continuous-domain optimization techniques such as linear and convex programs. We investigate the viability of a similar idea within message passing -- which produces integral solutions -- in the context of two combinatorial problems: 1) For Traveling Salesman Problem (TSP), we propose a factor-graph based on Held-Karp formulation, with an exponential number of constraint factors, each of which has an exponential but sparse tabular form. 2) For graph-partitioning (a.k.a., community mining) using modularity optimization, we introduce a binary variable model with a large number of constraints that enforce formation of cliques. In both cases we are able to derive surprisingly simple message updates that lead to competitive solutions on benchmark instances. In particular for TSP we are able to find near-optimal solutions in the time that empirically grows with N^3, demonstrating that augmentation is practical and efficient.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
A random-key GRASP for combinatorial optimization
Neural Improvement Heuristics for Graph Combinatorial Optimization Problems
PGT-I: Scaling Spatiotemporal GNNs with Memory-Efficient Distributed Training
Demystifying Distributed Training of Graph Neural Networks for Link Prediction
DistMLIP: A Distributed Inference Platform for Machine Learning Interatomic Potentials
Collaborative Problem-Solving in an Optimization Game
토론
이 논문과 연결된 포럼 글이 아직 없습니다.