組合せ最適化におけるアプリケーションを有する整数SDPのためのChv’atal-Gomory手順【JST・京大機械翻訳】

de Meijer Frank; Sotirov Renata

プレプリント

J-GLOBAL ID：202202211973327912 整理番号：22P0279384

組合せ最適化におけるアプリケーションを有する整数SDPのためのChv’atal-Gomory手順【JST・京大機械翻訳】

The Chv\'atal-Gomory Procedure for Integer SDPs with Applications in Combinatorial Optimization

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (2件)： ,
資料名：
発行年： 2022年01月25日プレプリントサーバーでの情報更新日： 2023年09月26日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

本論文では,整数半定値プログラム(ISDP)のクラスのためのよく知られたChv’atal-Gomory(CG)手順を研究した。この手順を反復することによって得られた緩和の階層構造に関するいくつかの結果を証明した。また,スペクトル面体の基本閉鎖の異なる定式化を研究した。SDPに対する全二重積分を利用して,特定のタイプのスペクトル面体に対する基本閉包の多面体記述を導いた。さらに,ISDPのための分岐およびカットフレームワークにおいて(強化)CGカットをいかに活用するかを示した。文献における既存のアルゴリズムとは異なり,著者らのアプローチにおける分離ルーチンは,半定値および積分制約の両方を利用する。組合せ最適化問題から生じる2成分SDPのいくつかの共通クラスに対する分離ルーチンを提供した。本論文の第2部では,二次巡回セールスマン問題(QTSP)に対する著者らのアプローチの包括的な応用を示した。有向ハミルトニアンサイクルの代数的連結性に基づいて,QTSPをモデル化する2つのISDPを導入した。これらの定式化から生じるCGカットは,切断面のいくつかのよく知られたファミリーを含むことを示した。数値結果により,代替ISDPソルバより性能が優れ,最適性に対する大きなQTSPインスタンスを解決できる,分岐およびカットアルゴリズムにおけるCGカットの実用的強度を説明した。【JST・京大機械翻訳】

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

数理計画法 , 人工知能 , 長さ,面積,断面,体積,容積,角度の計測法・機器

, , ,

前のページに戻る