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.
翻译:组合优化问题是各个领域的重要研究主题。近年来,利用基于深度学习的方法解决组合优化问题的尝试不断增加。我们提出了一种新颖的神经网络模型,通过自注意力和全新的注意机制解决几何组合优化问题。该模型通过在编码器中使用自注意力,高效地学习了几何组合优化问题中的点与点之间的关系。我们提出了有效的输入和输出序列排序方法,以减少不明确性并更为规律和高效地学习序列。同时,几何组合优化问题需要满足几何要求。因此在解码器中,我们提出了一种利用领域知识的新型掩模机制,当问题的几何要求不符合时,给出了高罚分。该模型是一个灵活的框架,可应用于各种涉及几何的组合优化问题。我们进行了实验证明了该模型在三个涉及几何的组合优化问题:德劳内三角剖分,凸包和平面旅行商问题的近似解求解中展现出了竞争性的性能。