Complex matter field universal models with optimal scaling for solving combinatorial optimization problems

• URL: http://arxiv.org/abs/2201.10595v1
• Date: Tue, 18 Jan 2022 21:53:47 GMT
• Title: Complex matter field universal models with optimal scaling for solving combinatorial optimization problems
• Authors: Natalia G. Berloff
• Abstract summary: We develop a universal model that allows the optimal mapping of many real-life NP-hard optimisation problems. We explicitly formulate one-to-one mapping for three famous problems: graph colouring, the travelling salesman, and the modular N-queens problem.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We develop a universal model based on the classical complex matter fields that allow the optimal mapping of many real-life NP-hard combinatorial optimisation problems into the problem of minimising a spin Hamiltonian. We explicitly formulate one-to-one mapping for three famous problems: graph colouring, the travelling salesman, and the modular N-queens problem. We show that such a formulation allows for several orders of magnitude improvement in the search for the global minimum compared to the standard Ising formulation. At the same time, the amplitude dynamics escape from the local minima.

Related papers

• Towards Geometry-Aware Pareto Set Learning for Neural Multi-Objective Combinatorial Optimization [19.631213689157995]
  Multi-objective diversity optimization (MOCO) problems are prevalent in various real-world applications. Most existing neural MOCO methods rely on problem to transform an MOCO problem into a series of singe-objective diversity enhancement (SOCO) problems. These methods often approximate partial regions of the front because of ambiguous and time-consuming precise hypervolume calculation.
  arXiv  Detail & Related papers  (2024-05-14T13:42:19Z)
• Feature selection in linear SVMs via a hard cardinality constraint: a scalable SDP decomposition approach [3.7876216422538485]
  We study the embedded feature selection problem in linear Support Vector Machines (SVMs) in which a cardinality constraint is employed. The problem is NP-hard due to the presence of the cardinality constraint, even though the original linear SVM amounts to a solvable problem in time. To handle the hard problem, we first introduce two mixed-integer formulations for which novel semidefinite relaxations are proposed.
  arXiv  Detail & Related papers  (2024-04-15T19:15:32Z)
• SIGMA: Scale-Invariant Global Sparse Shape Matching [50.385414715675076]
  We propose a novel mixed-integer programming (MIP) formulation for generating precise sparse correspondences for non-rigid shapes. We show state-of-the-art results for sparse non-rigid matching on several challenging 3D datasets.
  arXiv  Detail & Related papers  (2023-08-16T14:25:30Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• NeuroPrim: An Attention-based Model for Solving NP-hard Spanning Tree Problems [0.0]
  We propose NeuroPrim, a novel framework for solving various spanning tree problems by defining a Decision Process (MDP) for general optimization problems on graphs. We apply our framework to three difficult problems on Euclidean space: the Degree-constrained Minimum Spanning Tree (DCMST) problem, the Minimum Cost Spanning Tree (MRCST) problem, and the Steiner Tree Problem in Routing graphs (STP)
  arXiv  Detail & Related papers  (2022-10-22T13:49:29Z)
• A quantum-inspired tensor network method for constrained combinatorial optimization problems [5.904219009974901]
  We propose a quantum-inspired tensor-network-based algorithm for general locally constrained optimization problems. Our algorithm constructs a Hamiltonian for the problem of interest, effectively mapping it to a quantum problem. Our results show the effectiveness of this construction and potential applications.
  arXiv  Detail & Related papers  (2022-03-29T05:44:07Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• Bilinear Classes: A Structural Framework for Provable Generalization in RL [119.42509700822484]
  Bilinear Classes is a new structural framework which permits generalization in reinforcement learning. The framework incorporates nearly all existing models in which a sample complexity is achievable. Our main result provides an RL algorithm which has sample complexity for Bilinear Classes.
  arXiv  Detail & Related papers  (2021-03-19T16:34:20Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  We consider data-driven optimization problems where one must maximize a function given only queries at a fixed set of points. This problem setting emerges in many domains where function evaluation is a complex and expensive process. We propose a tractable approximation that allows us to scale our method to high-capacity neural network models.
  arXiv  Detail & Related papers  (2021-02-16T06:04:27Z)
• Complementary Composite Minimization, Small Gradients in General Norms, and Applications to Regression Problems [14.759688428864157]
  Composite minimization is a powerful framework in large-scale convex optimization. We introduce a new algorithmic framework for complementary composite minimization. We prove that the algorithms resulting from our framework are near-optimal in most of the standard optimization settings.
  arXiv  Detail & Related papers  (2021-01-26T19:21:28Z)
• Complexity continuum within Ising formulation of NP problems [0.0]
  Minimisation of the Ising Hamiltonian is known to be NP-hard problem for certain interaction matrix classes. We propose to identify computationally simple instances with an optimisation simplicity criterion' Such simplicity can be found for a wide range of models from spin glasses to k-regular maximum cut problems.
  arXiv  Detail & Related papers  (2020-08-02T11:36:38Z)
• MINA: Convex Mixed-Integer Programming for Non-Rigid Shape Alignment [77.38594866794429]
  convex mixed-integer programming formulation for non-rigid shape matching. We propose a novel shape deformation model based on an efficient low-dimensional discrete model.
  arXiv  Detail & Related papers  (2020-02-28T09:54:06Z)

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.