スパースMaxCutおよびQUBO問題の高速厳密解【JST・京大機械翻訳】

Rehfeldt Daniel; Koch Thorsten; Shinano Yuji

プレプリント

J-GLOBAL ID：202202213081184699 整理番号：22P0284917

スパースMaxCutおよびQUBO問題の高速厳密解【JST・京大機械翻訳】

Faster exact solution of sparse MaxCut and QUBO problems

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

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

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

最大カット問題は組合せ最適化における基本的問題の1つである。量子コンピュータの出現により,最大カットと等価二次制約なしバイナリ最適化問題は,近年多くの興味を経験した。本論文は,ディジタルコンピュータに関する数学的プログラミング技術を用いて,両方の問題の厳密解における最先端技術の進展を狙った。主な焦点は,高密度なものも解くことができるが,スパース問題事例にある。縮小技術と切断面分離アルゴリズムのようないくつかのアルゴリズム成分を強化し,それらを正確な分岐とカットソルバに結合させた。さらに,並列実装を提供した。新しいソルバは,スパースMaxCutとQUBOインスタンスに対して既存の最先端のソフトウェアを大幅に凌ぐことを示した。さらに,7番目のDIMACSチャレンジとQPLIBからいくつかのインスタンスに対する最良の既知限界を改善し,それらの幾つか(初めて)を最適に解いた。【JST・京大機械翻訳】

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

その他のオペレーションズリサーチの手法 , ネットワーク法 , 計算理論

前のページに戻る