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

• URL: http://arxiv.org/abs/2107.01759v2
• Date: Fri, 14 Apr 2023 01:41:00 GMT
• Title: Learning Geometric Combinatorial Optimization Problems using Self-attention and Domain Knowledge
• Authors: Jaeseung Lee, Woojin Choi, Jibum Kim
• Abstract summary: 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. 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Geometrically Inspired Kernel Machines for Collaborative Learning Beyond Gradient Descent [36.59087823764832]
  This paper develops a novel mathematical framework for collaborative learning by means of geometrically inspired kernel machines. For classification problems, this approach allows us to learn bounded geometric structures around given data points.
  arXiv  Detail & Related papers  (2024-07-05T08:20:27Z)
• A hybrid numerical methodology coupling Reduced Order Modeling and Graph Neural Networks for non-parametric geometries: applications to structural dynamics problems [0.0]
  This work introduces a new approach for accelerating the numerical analysis of time-domain partial differential equations (PDEs) governing complex physical systems. The methodology is based on a combination of a classical reduced-order modeling (ROM) framework and recently-parametric Graph Neural Networks (GNNs)
  arXiv  Detail & Related papers  (2024-06-03T08:51:25Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• Probabilistic partition of unity networks for high-dimensional regression problems [1.0227479910430863]
  We explore the partition of unity network (PPOU-Net) model in the context of high-dimensional regression problems. We propose a general framework focusing on adaptive dimensionality reduction. The PPOU-Nets consistently outperform the baseline fully-connected neural networks of comparable sizes in numerical experiments.
  arXiv  Detail & Related papers  (2022-10-06T06:01:36Z)
• Geometric Methods for Sampling, Optimisation, Inference and Adaptive Agents [102.42623636238399]
  We identify fundamental geometric structures that underlie the problems of sampling, optimisation, inference and adaptive decision-making. We derive algorithms that exploit these geometric structures to solve these problems efficiently.
  arXiv  Detail & Related papers  (2022-03-20T16:23:17Z)
• Hybrid neural network reduced order modelling for turbulent flows with geometric parameters [0.0]
  This paper introduces a new technique mixing up a classical Galerkin-projection approach together with a data-driven method to obtain a versatile and accurate algorithm for the resolution of geometrically parametrized incompressible turbulent Navier-Stokes problems. The effectiveness of this procedure is demonstrated on two different test cases: a classical academic back step problem and a shape deformation Ahmed body application.
  arXiv  Detail & Related papers  (2021-07-20T16:06:18Z)
• Decentralized Personalized Federated Learning for Min-Max Problems [79.61785798152529]
  This paper is the first to study PFL for saddle point problems encompassing a broader range of optimization problems. We propose new algorithms to address this problem and provide a theoretical analysis of the smooth (strongly) convex-(strongly) concave saddle point problems. Numerical experiments for bilinear problems and neural networks with adversarial noise demonstrate the effectiveness of the proposed methods.
  arXiv  Detail & Related papers  (2021-06-14T10:36:25Z)
• Fusing the Old with the New: Learning Relative Camera Pose with Geometry-Guided Uncertainty [91.0564497403256]
  We present a novel framework that involves probabilistic fusion between the two families of predictions during network training. Our network features a self-attention graph neural network, which drives the learning by enforcing strong interactions between different correspondences. We propose motion parmeterizations suitable for learning and show that our method achieves state-of-the-art performance on the challenging DeMoN and ScanNet datasets.
  arXiv  Detail & Related papers  (2021-04-16T17:59:06Z)
• Isometric Multi-Shape Matching [50.86135294068138]
  Finding correspondences between shapes is a fundamental problem in computer vision and graphics. While isometries are often studied in shape correspondence problems, they have not been considered explicitly in the multi-matching setting. We present a suitable optimisation algorithm for solving our formulation and provide a convergence and complexity analysis.
  arXiv  Detail & Related papers  (2020-12-04T15:58:34Z)
• Belief Propagation Reloaded: Learning BP-Layers for Labeling Problems [83.98774574197613]
  We take one of the simplest inference methods, a truncated max-product Belief propagation, and add what is necessary to make it a proper component of a deep learning model. This BP-Layer can be used as the final or an intermediate block in convolutional neural networks (CNNs) The model is applicable to a range of dense prediction problems, is well-trainable and provides parameter-efficient and robust solutions in stereo, optical flow and semantic segmentation.
  arXiv  Detail & Related papers  (2020-03-13T13:11:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.