論文の概要: Relative-Interior Solution for (Incomplete) Linear Assignment Problem
with Applications to Quadratic Assignment Problem
- arxiv url: http://arxiv.org/abs/2301.11201v1
- Date: Thu, 26 Jan 2023 16:22:01 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-27 13:17:58.123558
- Title: Relative-Interior Solution for (Incomplete) Linear Assignment Problem
with Applications to Quadratic Assignment Problem
- Title(参考訳): 二次割当て問題に対する(不完全)線形割当て問題に対する相対的相互解法と応用
- Authors: Tom\'a\v{s} Dlask and Bogdan Savchynskyy
- Abstract要約: 線形代入問題(LAP)の双対線形プログラミング定式化の最適解の集合について検討する。
この集合の相対的な内部から解を計算する方法を提案する。
- 参考スコア(独自算出の注目度): 4.113591581607196
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the set of optimal solutions of the dual linear programming
formulation of the linear assignment problem (LAP) to propose a method for
computing a solution from the relative interior of this set. Assuming that an
arbitrary dual-optimal solution and an optimal assignment are available (for
which many efficient algorithms already exist), our method computes a
relative-interior solution in linear time. Since LAP occurs as a subproblem in
the linear programming relaxation of quadratic assignment problem (QAP), we
employ our method as a new component in the family of dual-ascent algorithms
that provide bounds on the optimal value of QAP. To make our results applicable
to incomplete QAP, which is of interest in practical use-cases, we also provide
a linear-time reduction from incomplete LAP to complete LAP along with a
mapping that preserves optimality and membership in the relative interior. Our
experiments on publicly available benchmarks indicate that our approach with
relative-interior solution is frequently capable of providing superior bounds
and otherwise is at least comparable.
- Abstract(参考訳): 本稿では,線形代入問題 (LAP) の線形計画法を最適化した最適解の集合について検討し,その集合の相対的内部から解を計算する方法を提案する。
任意の双対最適解と最適代入(多くの効率的なアルゴリズムがすでに存在する)が可能であると仮定すると、線形時間で相対的中間解を計算する。
LAPは2次代入問題(QAP)の線形プログラミング緩和のサブプロブレムとして発生するため、この手法はQAPの最適値のバウンダリを提供する2進アルゴリズムの族における新しい成分として用いられる。
また,本研究の結果を,実用上興味のある不完全QAPに適用するために,不完全LAPから完全LAPへの線形時間短縮と,相対内部における最適性とメンバシップを維持するマッピングも提供する。
私たちの公開ベンチマーク実験は、相対対話型ソリューションを用いたアプローチは、しばしば優れた境界を提供することができ、それ以外は少なくとも同等であることを示している。
関連論文リスト
- Learning Constrained Optimization with Deep Augmented Lagrangian Methods [60.94111369773497]
機械学習(ML)モデルは、制約付き最適化ソルバをエミュレートするために訓練される。
本稿では,MLモデルを用いて2つの解推定を直接予測する手法を提案する。
これにより、双対目的が損失関数であるエンドツーエンドのトレーニングスキームと、双対上昇法をエミュレートした原始的実現可能性への解推定を可能にする。
論文 参考訳(メタデータ) (2024-03-06T04:43:22Z) - Towards Efficient Pareto-optimal Utility-Fairness between Groups in
Repeated Rankings [7.6275971668447005]
消費者と生産者のパレート最適バランスを保証し、ランキングの列を計算する問題に対処する。
本稿では,全ての項目が露出する点を表すペルムタヘドロンであるExpohedronを用いて,上記の問題に対する新しいアプローチを提案する。
さらに,Expohedronの囲む$n$-sphereの最適化問題を緩和し,実行時間を大幅に改善する効率的な手法を提案する。
論文 参考訳(メタデータ) (2024-02-22T05:48:54Z) - Oracle Complexity Reduction for Model-free LQR: A Stochastic
Variance-Reduced Policy Gradient Approach [4.422315636150272]
離散時間線形擬似レギュレータ(LQR)問題に対する$epsilon$-approximateソリューションの学習問題について検討する。
本手法は,二ループ分散推定アルゴリズムにおいて,一点推定と二点推定を併用する。
論文 参考訳(メタデータ) (2023-09-19T15:03:18Z) - Convex Q Learning in a Stochastic Environment: Extended Version [1.680268810119084]
本稿では,関数近似を用いたマルコフ決定過程に対する凸Q-ラーニングの最初の定式化について紹介する。
提案アルゴリズムは収束し, 平均二乗感覚における収束率を求める新しい手法が導入された。
この理論は古典的な在庫管理問題への応用として説明されている。
論文 参考訳(メタデータ) (2023-09-10T18:24:43Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳(メタデータ) (2023-07-17T20:11:56Z) - A New Inexact Proximal Linear Algorithm with Adaptive Stopping Criteria
for Robust Phase Retrieval [6.407536646154451]
本稿では,非平滑かつ非最適化問題であるロバスト検索問題を考察する。
本稿では,2つのコントリビューションでサブプロブレムを解くことを目的とした,新しい不正確な近位線形アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-04-25T02:29:33Z) - Maximum Optimality Margin: A Unified Approach for Contextual Linear
Programming and Inverse Linear Programming [10.06803520598035]
我々は、下流最適化の最適条件によって機械学習損失関数が機能する最大最適マージンと呼ばれる問題に対する新しいアプローチを開発する。
論文 参考訳(メタデータ) (2023-01-26T17:53:38Z) - Fully Stochastic Trust-Region Sequential Quadratic Programming for
Equality-Constrained Optimization Problems [62.83783246648714]
目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。
アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
論文 参考訳(メタデータ) (2022-11-29T05:52:17Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳(メタデータ) (2022-01-28T05:53:28Z) - Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。
本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
論文 参考訳(メタデータ) (2020-12-09T20:19:32Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳(メタデータ) (2020-07-14T12:38:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。