N重整数計画法の評価とチューニング【JST・京大機械翻訳】

Altmanova Katerina; Knop Dusan; Koutecky Martin

文献

J-GLOBAL ID：202002274109701335 整理番号：20A0777595

N重整数計画法の評価とチューニング【JST・京大機械翻訳】

Evaluating and Tuning n-fold Integer Programming

出版者サイト複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=20A0777595&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=20A0777595&from=J-GLOBAL&jstjournalNo=W5676A") }}

著者 (3件)： , ,
資料名：
巻： 24 号： 1 ページ： 1-22 発行年： 2019年
JST資料番号： W5676A ISSN： 1084-6654 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

近年,ストリング学,計算社会選択,スケジューリングなどにおけるアルゴリズム的ブレークスルーが,いわゆるn倍整数計画法の理論を適用することによって達成された。n倍整数計画(IP)は非常に均一なブロック構造化制約行列を有する。Hemmecke,Onn,およびRomanchuk[Math.Program,2013]は,Δが最大係数,r,s,およびtが制約行列のブロックの次元であり,nがIPの全次元である,実行時間ΔO(rst+r~2s)n~3のアルゴリズムを示した。したがって,ブロックが小さいサイズで小さい係数を持つならば,アルゴリズムは効率的である。このアルゴリズムは,逐次的に拡張ステップで実行可能な解を改善することにより動作し,n倍のIPは,ステップがノードから大規模な近傍に存在するように保証される特別な性質を持つ。しかし,このアルゴリズムは実装され,評価されていない。このアルゴリズムを実装し,次の方法に従って学習した。元のアルゴリズムは実用的には使用できないが,その評価を可能にする一連の改良を発見した。決定的に,アルゴリズムにおける一定の定数を同調パラメータとして扱うことができることを観察し,それは効率的な発見的(本質的にはより小さい保証された近傍での探索)をもたらす。さらに,このアルゴリズムは「最良」ステップを見出すために非常に高価な戦略を用いるが,「近似的に最良」ステップのみを見出すことは非常に安価であるが,急速な収束には十分である。この洞察を用いて,n~3からn~2log nへのnへの漸近依存性を改善した。最終的に,著者らは調整パラメータの様々な値によるアルゴリズムの挙動と改善段階を発見する種々の戦略をテストした。最初に,同調パラメータを減少させることにより,収束に必要な反復数が増加し,最終的には,期待通りに,局所最適化においてスタックを得ることができることを示した。しかしながら,パラメータの驚くほど小さい値は,既に良好な挙動を示し,一方,アルゴリズムが単一反復当たりに費やす時間を著しく低下させる。第二に,「近似的に最も良い」ステップを見出すための新しい戦略は,本来の構築よりも優れている。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

, , , , , ,
, , , 【Automatic Indexing@JST】

著者キーワード (5件)： , , , ,

数理計画法

, ,

前のページに戻る