論文の概要: Relative-Interior Solution for (Incomplete) Linear Assignment Problem
with Applications to Quadratic Assignment Problem
- arxiv url: http://arxiv.org/abs/2301.11201v2
- Date: Wed, 1 Nov 2023 21:49:45 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-03 18:08:47.837225
- 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)の双対線形プログラミング定式化の最適解の集合について検討する。
この集合の相対的な内部から解を計算する方法を提案する。
- 参考スコア（独自算出の注目度）: 2.5391160354531697
- 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への線形時間短縮と,相対内部における最適性とメンバシップを維持するマッピングも提供する。
私たちの公開ベンチマーク実験は、相対対話型ソリューションを用いたアプローチは、しばしば優れた境界を提供することができ、それ以外は少なくとも同等であることを示している。
関連論文リスト
- 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) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - 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) - Proximal Point Imitation Learning [48.50107891696562]
我々は、無限地平線模倣学習のための厳密な効率保証を備えた新しいアルゴリズムを開発した。
我々は、最適化、特に近点法(PPM)と双対平滑化から古典的ツールを活用する。
線形関数とニューラルネットワーク関数の近似の双方に対して、説得力のある経験的性能を実現する。
論文 参考訳（メタデータ） (2022-09-22T12:40:21Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Learning to Reformulate for Linear Programming [11.628932152805724]
本稿では,リニアプログラミング(LP)の強化学習に基づく再構成手法を提案する。
本研究では,2つの公共研究用LPデータセットと,実運用シナリオから収集した大規模LPデータセットに対して提案手法を実装した。
論文 参考訳（メタデータ） (2022-01-17T04:58:46Z) - Logistic Q-Learning [87.00813469969167]
MDPにおける最適制御の正規化線形プログラミング定式化から導いた新しい強化学習アルゴリズムを提案する。
提案アルゴリズムの主な特徴は,広範に使用されているベルマン誤差の代わりとして理論的に音声として機能する,政策評価のための凸損失関数である。
論文 参考訳（メタデータ） (2020-10-21T17:14:31Z) - Integrated Cutting and Packing Heterogeneous Precast Beams Multiperiod
Production Planning Problem [0.0]
我々は、ICP-HPBMPP(ICP-HPBMPP)と呼ばれる新規な切断・充填不均質ビーム製造計画法を導入する。
我々は、ICP-HPBMPPの整数線形プログラミングモデルと、その最適目的関数値の下位境界を提案する。
また,代替解法としてICP-HPBMPPの遺伝的手法を提案する。
論文 参考訳（メタデータ） (2020-08-25T23:10:37Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。