# Learning Geometric Combinatorial Optimization Problems using Self-attention and Domain Knowledge

arXiv: https://arxiv.org/abs/2107.01759 · HTML: https://mlsanity.com/paper/2107.01759/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 42 references that are in the map.
- First posted on arXiv 5 Jul 2021.

## Builds on (most cited first, 19 of 19)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Sequence to Sequence Learning with Neural Networks](https://mlsanity.com/paper/1409.3215/) (2014)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Exploring Self-attention for Image Recognition](https://mlsanity.com/paper/2004.13621/) (2020)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Order Matters: Sequence to sequence for sets](https://mlsanity.com/paper/1511.06391/) (2015)
- [Pay Less Attention with Lightweight and Dynamic Convolutions](https://mlsanity.com/paper/1901.10430/) (2019)
- [The Transformer Network for the Traveling Salesman Problem](https://mlsanity.com/paper/2103.03012/) (2021)
- [Deep Reinforcement Learning for Combinatorial Optimization: Covering Salesman Problems](https://mlsanity.com/paper/2102.05875/) (2021)
- [Deep Choice Model Using Pointer Networks for Airline Itinerary Prediction](https://mlsanity.com/paper/1803.05976/) (2018)
- [Real-Time Neural Network Scheduling of Emergency Medical Mask Production during COVID-19](https://mlsanity.com/paper/2007.14055/) (2020)
- [S-hull: a fast radial sweep-hull routine for Delaunay triangulation](https://mlsanity.com/paper/1604.01428/) (2016)

## Abstract (arXiv)

Combinatorial optimization problems (COPs) are an important research topic in various fields. In recent times, there have been many attempts to solve COPs using deep learning-based approaches. We propose a novel neural network model that solves COPs involving geometry based on self-attention and a new attention mechanism. The proposed model is designed such that the model efficiently learns point-to-point relationships in COPs involving geometry using self-attention in the encoder. We propose efficient input and output sequence ordering methods that reduce ambiguities such that the model learns the sequences more regularly and effectively. Geometric COPs involve geometric requirements that need to be satisfied. In the decoder, a new masking scheme using domain knowledge is proposed to provide a high penalty when the geometric requirement of the problem is not satisfied. The proposed neural net is a flexible framework that can be applied to various COPs involving geometry. We conduct experiments to demonstrate the effectiveness of the proposed model for three COPs involving geometry: Delaunay triangulation, convex hull, and the planar Traveling Salesman problem. Our experimental results show that the proposed model exhibits competitive performance in finding approximate solutions for solving these problems.