論文の概要: Advanced Quantum Annealing for the Bi-Objective Traveling Thief Problem: An $\varepsilon$-Constraint-based Approach
- arxiv url: http://arxiv.org/abs/2603.18038v1
- Date: Fri, 13 Mar 2026 05:26:25 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-20 17:19:05.710642
- Title: Advanced Quantum Annealing for the Bi-Objective Traveling Thief Problem: An $\varepsilon$-Constraint-based Approach
- Title（参考訳）: 両目的トラベリングティーフ問題に対する高度な量子アニーリング:$\varepsilon$-Constraint によるアプローチ
- Authors: Nguyen Hoang Viet, Nguyen Xuan Tung, Trinh Van Chien, Won-Joo Hwang,
- Abstract要約: Bi-Objective Traveling Thief Problem (BI-TTP)は、旅行コストとアイテム利益の同時最適化を必要とする。
BI-TTPの従来の手法は、ルーティングとパッケージ決定の複雑な相互依存のため、しばしば深刻なスケーラビリティの問題に直面する。
本稿では量子アニール法(QA)と$varepsilon$-constraint法を組み合わせた高度なハイブリッド手法を提案する。
- 参考スコア（独自算出の注目度）: 7.06690496634166
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper addresses the Bi-Objective Traveling Thief Problem (BI-TTP), a challenging multi-objective optimization problem that requires the simultaneous optimization of travel cost and item profit. Conventional methods for the BI-TTP often face severe scalability issues due to the complex interdependence between routing and packing decisions, as well as the inherent complexity and large problem size. These difficulties render classical computing approaches increasingly inapplicable. To tackle this, we propose an advanced hybrid approach that combines quantum annealing (QA) with the $\varepsilon$-constraint method. Specifically, we reformulate the bi-objective problem into a single-objective formulation by restricting the second objective through adjustable $\varepsilon$-levels, determined within established upper and lower bounds. The resulting subproblem involves a sum of fractional terms, which is reformulated with auxiliary variables into an equivalent form. Subsequently, the equivalent formulation is transformed into a Quadratic Unconstrained Binary Optimization (QUBO) model, enabling direct solution via a quantum annealing (QA) solver. The solutions obtained from the quantum annealer are subsequently refined using a tailored heuristic procedure to further enhance overall performance. By leveraging the flexibility in selecting $\varepsilon$ parameters, our approach effectively captures a broad Pareto front, enhancing solution diversity. Experimental results on benchmark instances demonstrate that the proposed method effectively balances two objectives and outperforms baseline approaches in time efficiency.
- Abstract（参考訳）: 本稿では,旅行コストと商品利益の同時最適化を必要とする多目的最適化問題であるBI-TTP(Bi-Objective Traveling Thief Problem)に対処する。
BI-TTPの従来の手法は、ルーティングとパッケージ決定の複雑な相互依存、および固有の複雑さと大きな問題サイズによって、しばしば深刻なスケーラビリティの問題に直面する。
これらの困難は、古典コンピューティングのアプローチをますます適用不能にしている。
これを解決するために、量子アニール法(QA)と$\varepsilon$-constraint法を組み合わせた高度なハイブリッドアプローチを提案する。
具体的には、固定可能な$\varepsilon$-levelsによって2番目の目的を制限し、確立された上と下の境界内で決定された双対象問題を1つの対象の定式化に再構成する。
結果として得られる部分プロブレムは分数項の和を含み、補助変数によって同値な形式に再構成される。
その後、等価な定式化を準非拘束バイナリ最適化(QUBO)モデルに変換し、量子アニーリング(QA)ソルバによる直接解法を可能にする。
その後、量子アニールから得られる溶液は、全体的な性能を高めるために、調整されたヒューリスティック法を用いて精製される。
$\varepsilon$パラメータを選択する際の柔軟性を活用することで、我々のアプローチはPareto前線を効果的に捉え、ソリューションの多様性を高めます。
ベンチマーク実験の結果、提案手法は2つの目的を効果的にバランスさせ、時間効率においてベースラインアプローチより優れていることが示された。
関連論文リスト
- Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。
既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。
これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-04-21T17:15:48Z) - Two-Step QAOA: Enhancing Quantum Optimization by Decomposing K-hot Constraints in QUBO Formulations [0.0]
Two-Step QAOAは、k-hotエンコーディングQUBO定式化の問題を分解することで、QAOAの有効性を向上させることを目的としている。
ソフト制約をハード制約に変換し、初期条件の生成を単純化する。
論文 参考訳（メタデータ） (2024-08-09T23:38:28Z) - Optimized QUBO formulation methods for quantum computing [0.4999814847776097]
実世界の金融シナリオにインスパイアされたNPハード最適化問題に対して,我々の手法を適用する方法について述べる。
2つのD波量子異方体にこの問題の事例を提出し、これらのシナリオで使用される標準手法と新しい手法の性能を比較した。
論文 参考訳（メタデータ） (2024-06-11T19:59:05Z) - Lagrangian Duality in Quantum Optimization: Overcoming QUBO Limitations for Constrained Problems [0.0]
本稿では,ラグランジアン双対性の概念を断熱量子計算の枠組みに組み込むことにより,制約付き最適化問題の解法を提案する。
回路モデル-フォールトトレラント量子計算の設定において、本手法が回路深さの2次改善を実現し、制約非依存の回路幅を維持することを実証する。
論文 参考訳（メタデータ） (2023-10-06T19:09:55Z) - Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
余分なスラック変数を必要としない代替手法を提案する。
我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。
この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
論文 参考訳（メタデータ） (2022-11-25T06:05:18Z) - A Study of Scalarisation Techniques for Multi-Objective QUBO Solving [0.0]
量子および量子に着想を得た最適化アルゴリズムは、学術ベンチマークや実世界の問題に適用した場合に有望な性能を示す。
しかし、QUBOソルバは単目的解法であり、複数の目的による問題の解法をより効率的にするためには、そのような多目的問題を単目的問題に変換する方法を決定する必要がある。
論文 参考訳（メタデータ） (2022-10-20T14:54:37Z) - Algorithm for Constrained Markov Decision Process with Linear
Convergence [55.41644538483948]
エージェントは、そのコストに対する複数の制約により、期待される累積割引報酬を最大化することを目的としている。
エントロピー正規化ポリシーとベイダの二重化という2つの要素を統合した新しい双対アプローチが提案されている。
提案手法は(線形速度で)大域的最適値に収束することが示されている。
論文 参考訳（メタデータ） (2022-06-03T16:26:38Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳（メタデータ） (2021-07-02T16:21:52Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。