論文の概要: A Quantum Inspired Bi-level Optimization Algorithm for the First
Responder Network Design Problem
- arxiv url: http://arxiv.org/abs/2401.12463v1
- Date: Tue, 23 Jan 2024 03:22:05 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-24 16:52:39.134392
- Title: A Quantum Inspired Bi-level Optimization Algorithm for the First
Responder Network Design Problem
- Title（参考訳）: 最初の応答ネットワーク設計問題に対する量子インスパイア二レベル最適化アルゴリズム
- Authors: Anthony Karahalios, Sridhar Tayur, Ananth Tenneti, Amirreza Pashapour,
F. Sibel Salman, Bar{\i}\c{s} Y{\i}ld{\i}z
- Abstract要約: トルコの交通・インフラ省からの提案では、ファースト・レスポンダーズのみが使用する道路セグメントのサブセットを割り当てることになっている。
本稿では,この1次応答器ネットワーク設計問題に対する混合整数非線形プログラミングの定式化について述べる。
FRとエスキューパスのフローバランスの制約を用いて、部分的なグラバーベースを得るために、擬似非拘束バイナリ最適化(QUBO)モデルを用いる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the aftermath of a sudden catastrophe, First Responders (FR) strive to
promptly reach and rescue immobile victims. Simultaneously, other mobile
individuals take roads to evacuate the affected region, or access shelters. The
escalated traffic congestion significantly hinders critical FR operations if
they share some of the same roads. A proposal from the Turkish Ministry of
Transportation and Infrastructure being discussed for implementation is to
allocate a subset of road segments for use by FRs only, mark them clearly, and
pre-communicate them to the citizens. For the FR paths under consideration: (i)
there should exist an FR path from designated entry points to each demand point
in the network, and (ii) evacuees try to leave the network (through some exit
points following the selfish routing principle) in the shortest time possible
when they know that certain segments are not available to them. We develop a
mixed integer non-linear programming formulation for this First Responder
Network Design Problem (FRNDP). We solve FRNDP using a novel hybrid
quantum-classical heuristic building on the Graver Augmented Multi-Seed
Algorithm (GAMA). Using the flow-balance constraints for the FR and evacuee
paths, we use a Quadratic Unconstrained Binary Optimization (QUBO) model to
obtain a partial Graver Bases to move between the feasible solutions of FRNDP.
To efficiently explore the solution space for high-quality solutions, we
develop a novel bi-level nested GAMA within GAMA: GAGA. We test GAGA on random
graph instances of various sizes and instances related to an expected Istanbul
earthquake. Comparing GAGA against a state-of-the-art exact algorithm for
traditional formulations, we find that GAGA offers a promising alternative
approach. We hope our work encourages further study of quantum (inspired)
algorithms to tackle complex optimization models from other application
domains.
- Abstract（参考訳）: 突然の大惨事の後、ファースト・レスポンダーズ(FR)は即刻、不動の犠牲者を救助しようと試みた。
同時に、他の移動体は道路を利用して被災地や避難所を避難する。
交通渋滞の増大は、同じ道路を共有している場合、重要なFRの運行を著しく妨げる。
実施のために議論されているトルコ交通インフラ省からの提案は、FRが使用する道路セグメントのサブセットを割り当て、それらを明確にマークし、それらを市民に事前通信することである。
検討中のFRパスについて
(i)指定エントリポイントからネットワーク内の各需要ポイントまでのFRパスが存在しなければならない。
(ii)避難者は、特定のセグメントが利用可能でないことを知っていれば、できるだけ短時間で(利己的なルーティング原則に従って、いくつかの出口ポイントを通して)ネットワークを離れようとします。
本稿では、この第一応答型ネットワーク設計問題(FRNDP)に対する混合整数非線形計画法を開発した。
我々は,Graver Augmented Multi-Seed Algorithm (GAMA) を用いた新しい量子古典的ヒューリスティック・ビルディングを用いてFRNDPを解く。
FRと避難経路のフローバランス制約を用いて、FRNDPの実現可能な解の間を移動する部分的なグラバーベースを得るために、擬似非拘束バイナリ最適化(QUBO)モデルを用いる。
高品質なソリューションのための解空間を効率的に探索するために,GAMA: GAGA内に2レベルネスト付きGAMAを新たに開発する。
Istanbul地震に関連する様々な大きさのランダムグラフのインスタンスについてGAGAを検証した。
GAGAを従来の定式化のための最先端の正確なアルゴリズムと比較すると,GAGAは有望な代替手法であることがわかった。
私たちの研究は、他のアプリケーションドメインから複雑な最適化モデルに取り組むために、量子(インスパイアされた)アルゴリズムのさらなる研究を促進することを願っています。
関連論文リスト
- Hierarchical Neural Constructive Solver for Real-world TSP Scenarios [27.986011761759567]
本稿では,産業環境に関連する現実的なトラベリングセールスマン問題(TSP)について紹介する。
我々の階層的アプローチは、古典的モデルと最近のトランスモデルの両方と比較して優れたパフォーマンスをもたらす。
論文 参考訳（メタデータ） (2024-08-07T06:44:47Z) - Rethinking PGD Attack: Is Sign Function Necessary? [131.6894310945647]
本稿では,このような手話に基づく更新アルゴリズムが段階的攻撃性能にどのように影響するかを理論的に分析する。
本稿では,手話の使用を排除したRGDアルゴリズムを提案する。
提案したRGDアルゴリズムの有効性は実験で広く実証されている。
論文 参考訳（メタデータ） (2023-12-03T02:26:58Z) - Genetic Algorithms with Neural Cost Predictor for Solving Hierarchical Vehicle Routing Problems [20.684353068460375]
車両の経路決定が高次決定と連動する場合、結果の最適化問題は計算に重大な課題をもたらす。
本稿では,ニューラルコスト予測器を用いた遺伝的アルゴリズム(GANCP)という,ディープラーニングに基づく新しいアプローチを提案する。
特に,提案するニューラルネットワークは,静電容量化車両ルーティング問題を解決するHGS-CVRPオープンソースパッケージの目的値について学習する。
論文 参考訳（メタデータ） (2023-10-22T02:46:37Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Generalized Universal Domain Adaptation with Generative Flow Networks [76.1350941965148]
Generalized Universal Domain Adaptationは、未知のカテゴリを含む全てのターゲットラベルの正確な予測を実現することを目的としている。
GUDAはラベル分布シフトベースとラベル空間ミスマッチベースとのギャップを埋める。
本稿では,報酬関数に比例した確率を持つ多種多様なサンプルを選択する,GFlowDAというドメイン適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-05-08T05:34:15Z) - A generalized network level disruption strategy selection model for
urban public transport systems [16.64085440434604]
ディスラプションからの迅速な回復は、トランジットシステムの信頼性にとって極めて重要である。
本研究は, 交通破壊対策を包括的かつ階層的に実施する試みである。
論文 参考訳（メタデータ） (2023-05-07T16:34:25Z) - Dense Hybrid Proposal Modulation for Lane Detection [72.49084826234363]
レーン検出のための高密度ハイブリッド提案変調(DHPM)法を提案する。
我々は、トポロジカルかつ空間的に高品質なレーン予測を生成するために、全ての提案を密に調整する。
我々のDHPMは4つの人気のあるデータセットで非常に競争力のあるパフォーマンスを実現しています。
論文 参考訳（メタデータ） (2023-04-28T14:31:11Z) - LHNN: Lattice Hypergraph Neural Network for VLSI Congestion Prediction [70.31656245793302]
格子ハイパーグラフ(格子ハイパーグラフ)は、回路のための新しいグラフ定式化である。
LHNNは、F1スコアのU-netやPix2Pixと比べて、35%以上の改善を常に達成している。
論文 参考訳（メタデータ） (2022-03-24T03:31:18Z) - Optimal Solving of Constrained Path-Planning Problems with Graph
Convolutional Networks and Optimized Tree Search [12.457788665461312]
本稿では,機械学習モデルと最適解法を併用したハイブリッド問題解決プランナを提案する。
我々は現実的なシナリオで実験を行い、GCNのサポートにより、より難しい問題に対して、大幅なスピードアップとスムーズなスケーリングが可能になることを示す。
論文 参考訳（メタデータ） (2021-08-02T16:53:21Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - Routing Towards Discriminative Power of Class Capsules [7.347145775695176]
本稿では,効率よく解ける正規化二次計画問題を含むルーティングアルゴリズムを提案する。
mnist,mnist-fashion,cifar-10の実験を行い,既存のカプセルネットワークと比較して競合分類結果を示す。
論文 参考訳（メタデータ） (2021-03-07T05:49:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。