論文の概要: Indirect Job-Shop coding using rank: application to QAOA (IQAOA)
- arxiv url: http://arxiv.org/abs/2402.18280v1
- Date: Wed, 28 Feb 2024 12:17:21 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-29 15:04:50.048507
- Title: Indirect Job-Shop coding using rank: application to QAOA (IQAOA)
- Title(参考訳): ランクを用いた間接ジョブショップコーディング:QAOA(IQAOA)への適用
- Authors: Eric Bourreau, Gerard Fleury, Phlippe Lacomme
- Abstract要約: ジョブショップスケジューリング問題(JSSP)は、スケジューリングにおける最も有名な課題の1つです。
この問題を解決する複雑さは、解を表す可分グラフが非巡回でなければならないという要求から生じる。
本稿では,BierwithのベクトルをQuantum Approximate Optimization Algorithm (QAOA)に統合して,ジョブショップ問題に対処する方法を示す。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Job-Shop Scheduling Problem (JSSP) stands as one of the most renowned
challenges in scheduling. It is characterized as a disjunctive problem, wherein
a solution is fully depicted through an oriented disjunctive graph, with
earliest starting times computed using a longest path algorithm. The complexity
of solving this problem arises in part from the requirement that disjunctive
graphs representing solutions must be acyclic. Consequently, enumerating these
graphs is feasible for small-scale instances only. A significant advancement in
this field, credited to (Bierwith, 1995), is the introduction of the 'vector by
repetition' (commonly known as Bierwith's vector). Notably, this vector
possesses the property that it can be mapped to an acyclic disjunctive graph,
thereby enabling the mapping of a vector to a solution. This property has
facilitated the development of highly efficient resolution schemes, as it
allows the enumeration of solutions only i.e. acyclic disjunctive graphs. Our
objective is to demonstrate how Bierwith's vector can be integrated into a
Quantum Approximate Optimization Algorithm (QAOA) to tackle the job-shop
problem using a novel quantum approach.
- Abstract(参考訳): ジョブショップスケジューリング問題(JSSP)は、スケジューリングにおける最も有名な課題の1つです。
解は、最も長い経路アルゴリズムを用いて計算された最初期の始点時間で、向き付けられた可解グラフを通して完全に表現される。
この問題を解決する複雑さは、解を表す可分グラフが非巡回でなければならないという要求から生じる。
したがって、小規模インスタンスのみの場合、これらのグラフを列挙することは可能である。
この分野における重要な進歩は (Bierwith, 1995) と名付けられ、「反復によるベクトル」 (一般には Bierwith のベクトルとして知られている) の導入である。
特に、このベクトルは非巡回可除グラフに写像できる性質を持ち、したがってベクトルの解への写像を可能にする。
この性質は、解の列挙、すなわち非環状不連結グラフのみを可能にするため、高効率な解決スキームの開発を促進する。
我々の目的は、新しい量子アプローチを用いてジョブショップ問題に取り組むために、Bierwithのベクトルを量子近似最適化アルゴリズム(QAOA)に統合する方法を実証することである。
関連論文リスト
- ATOM: An Efficient Topology Adaptive Algorithm for Minor Embedding in
Quantum Computing [18.594343052664335]
ハードウェアグラフの拡張可能な部分グラフである適応トポロジーの新たな概念を導入する。
ATOMは論理グラフからノードを反復的に選択し、ハードウェアグラフの適応トポロジーに埋め込む。
実験の結果、ATOMは最先端技術よりもはるかに少ない実行時間で実現可能な埋め込みを実現することができることがわかった。
論文 参考訳(メタデータ) (2023-07-04T17:45:07Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳(メタデータ) (2023-06-14T09:21:15Z) - Kernelized multi-graph matching [0.0]
本稿では,グラフの属性とエッジの両方を扱う,新しいカーネル化されたマルチグラフマッチング手法を提案する。
結果の安定性の向上につながるプロジェクタをいくつか提案する。
論文 参考訳(メタデータ) (2022-10-11T07:22:47Z) - LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale
Combinatorial Optimisation [6.316693022958222]
ユークリッド部分グラフの埋め込みを地図として用いて,可能な部分グラフの空間をナビゲートする方法を学習する強化学習アルゴリズムを提案する。
LeNSEは、グラフ全体への埋め込みの実行によって見いだされたソリューションに匹敵するソリューションをもたらす小さなサブグラフを識別するが、全体の実行時間のごく一部にはならない。
論文 参考訳(メタデータ) (2022-05-20T11:54:03Z) - Gaussian Amplitude Amplification for Quantum Pathfinding [0.0]
逐次連結な二部グラフの幾何学に焦点をあて、ガウス分布によって記述可能な解空間を自然に生み出す。
本稿では,これらの分布を符号化したオラクルを用いて振幅増幅による最適経路を解く方法を示す。
論文 参考訳(メタデータ) (2021-12-15T14:41:14Z) - Improved Acyclicity Reasoning for Bayesian Network Structure Learning
with Constraint Programming [0.0]
離散データからベイズネットワーク(BNSL)の構造を学習することはNPハードタスクであることが知られている。
本研究では,可能なクラスタカットのサブセットを発見するための新しい時間アルゴリズムを提案する。
最適ではないにもかかわらず、性能は桁違いに向上することを示す。
結果として得られる解法は、BNSL問題に対する最先端の解法である GOBNILP と好意的に比較できる。
論文 参考訳(メタデータ) (2021-06-23T09:46:11Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。
本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。
Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文 参考訳(メタデータ) (2021-05-06T17:59:38Z) - Boosting Data Reduction for the Maximum Weight Independent Set Problem
Using Increasing Transformations [59.84561168501493]
最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。
驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。
提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
論文 参考訳(メタデータ) (2020-08-12T08:52:50Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳(メタデータ) (2020-06-24T11:37:33Z) - Competitive Mirror Descent [67.31015611281225]
制約のある競合最適化には、制約の対象となる競合する目的を最小化しようとする複数のエージェントが含まれる。
本稿では, 競合ミラー降下法(CMD)を提案する。
特別の場合として、正の円錐上の問題に対する新しい競合乗法重みアルゴリズムを得る。
論文 参考訳(メタデータ) (2020-06-17T22:11:35Z) - Wasserstein-based Graph Alignment [56.84964475441094]
我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。
提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
論文 参考訳(メタデータ) (2020-03-12T22:31:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。