Fugu-MT 論文翻訳(概要): Complex matter field universal models with optimal scaling for solving combinatorial optimization problems

論文の概要: Complex matter field universal models with optimal scaling for solving combinatorial optimization problems

arxiv url: http://arxiv.org/abs/2201.10595v1
Date: Tue, 18 Jan 2022 21:53:47 GMT
ステータス: 処理完了
システム内更新日: 2023-02-28 20:20:21.308695
Title: Complex matter field universal models with optimal scaling for solving combinatorial optimization problems
Title（参考訳）: 組合せ最適化問題を解くための最適スケーリングを伴う複素体場ユニバーサルモデル
Authors: Natalia G. Berloff
Abstract要約: 我々は、多くの実生活NP-ハード最適化問題の最適マッピングを可能にする普遍モデルを開発する。グラフカラー化、旅行セールスマン、モジュラーN-クエンス問題という3つの有名な問題に対して、1対1のマッピングを明示的に定式化する。
参考スコア（独自算出の注目度）: 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.
Abstract（参考訳）: 我々は、スピンハミルトニアンを最小化する問題への多くの実数NP-ハード組合せ最適化問題の最適写像を可能にする古典的複素体場に基づく普遍モデルを開発する。グラフカラー、トラベルセールスマン、モジュラー n-queens 問題という3つの有名な問題に対して、一対一のマッピングを明示的に定式化する。このような定式化は, 標準イジング定式化と比較して, グローバル最小値の探索において数桁の改善が可能であることを示す。同時に、振幅ダイナミクスは局所的なミニマから脱出する。

関連論文リスト

Towards Geometry-Aware Pareto Set Learning for Neural Multi-Objective Combinatorial Optimization [19.631213689157995]
多目的多様性最適化(MOCO)問題は、様々な現実世界の応用で広く用いられている。既存のほとんどのニューラルMOCO法は、MOCO問題を一連のSinge-Objective diversity enhancement (SOCO)問題に変換するために問題に依存する。これらの手法はしばしば、不明瞭で時間を要する正確な超体積計算のため、前面の部分領域を近似する。
論文参考訳（メタデータ） (2024-05-14T13:42:19Z)
SIGMA: Scale-Invariant Global Sparse Shape Matching [50.385414715675076]
非剛体形状の正確なスパース対応を生成するための新しい混合整数プログラミング(MIP)法を提案する。いくつかの挑戦的な3Dデータセットに対して,スパースな非剛性マッチングの最先端結果を示す。
論文参考訳（メタデータ） (2023-08-16T14:25:30Z)
Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文参考訳（メタデータ） (2022-11-16T18:59:54Z)
NeuroPrim: An Attention-based Model for Solving NP-hard Spanning Tree Problems [0.0]
我々は,グラフ上の一般的な最適化問題に対して,決定過程(MDP)を定義することによって,様々な木にまたがる問題を解く新しいフレームワークであるNeuroPrimを提案する。この枠組みをユークリッド空間上の3つの難しい問題に適用する: Degree-constrained Minimum Spanning Tree (DCMST) 問題、最小コストスパンニングツリー (MRCST) 問題、ルーティンググラフ (STP) におけるスタイナーツリー問題。
論文参考訳（メタデータ） (2022-10-22T13:49:29Z)
A quantum-inspired tensor network method for constrained combinatorial optimization problems [5.904219009974901]
本稿では,一般に局所的に制約された最適化問題に対する量子インスパイアされたテンソルネットワークに基づくアルゴリズムを提案する。我々のアルゴリズムは、興味のある問題に対してハミルトニアンを構築し、量子問題に効果的にマッピングする。本研究は,本手法の有効性と応用の可能性を示すものである。
論文参考訳（メタデータ） (2022-03-29T05:44:07Z)
Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-09-30T19:17:35Z)
Bilinear Classes: A Structural Framework for Provable Generalization in RL [119.42509700822484]
Bilinear Classesは強化学習の一般化を可能にする新しい構造フレームワークである。このフレームワークは、サンプルの複雑さが達成可能な、ほとんどすべての既存のモデルを取り込んでいる。我々の主な成果は、双線形クラスのためのサンプル複雑性を持つRLアルゴリズムである。
論文参考訳（メタデータ） (2021-03-19T16:34:20Z)
Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
データ駆動最適化の問題を検討し、一定の点セットでクエリのみを与えられた関数を最大化する必要がある。この問題は、関数評価が複雑で高価なプロセスである多くの領域に現れる。我々は,提案手法を高容量ニューラルネットワークモデルに拡張可能なトラクタブル近似を提案する。
論文参考訳（メタデータ） (2021-02-16T06:04:27Z)
Complementary Composite Minimization, Small Gradients in General Norms, and Applications to Regression Problems [14.759688428864157]
複合最小化は大規模凸最適化における強力なフレームワークである。補完的複合最小化のための新しいアルゴリズムフレームワークを提案する。我々は,フレームワークから得られるアルゴリズムが,ほとんどの標準最適化設定においてほぼ最適であることを証明した。
論文参考訳（メタデータ） (2021-01-26T19:21:28Z)
Complexity continuum within Ising formulation of NP problems [0.0]
イジング・ハミルトニアンの最小化は、ある相互作用行列類に対するNPハード問題であることが知られている。我々は、最適化単純度基準で計算学的に単純なインスタンスを特定することを提案する。このような単純さはスピングラスからk規則の最大カット問題まで幅広いモデルで見られる。
論文参考訳（メタデータ） (2020-08-02T11:36:38Z)
MINA: Convex Mixed-Integer Programming for Non-Rigid Shape Alignment [77.38594866794429]
非剛体形状マッチングのための凸混合整数プログラミングの定式化。効率的な低次元離散モデルに基づく新しい形状変形モデルを提案する。
論文参考訳（メタデータ） (2020-02-28T09:54:06Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。