P分割定式化:離接制約のためのbig-Mおよび凸包間の中間定式化のクラス【JST機械翻訳】

Kronqvist Jan; Misener Ruth; Tsay Calvin

プレプリント

J-GLOBAL ID：202202208930072790 整理番号：22P0287810

P分割定式化:離接制約のためのbig-Mおよび凸包間の中間定式化のクラス【JST機械翻訳】

P-split formulations: A class of intermediate formulations between big-M and convex hull for disjunctive constraints

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

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

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

緩和強度に関して,big-Mおよび凸包定式化の中間の選言的制約条件のための混合整数定式化のクラスを開発した。主なアイデアは,big-Mおよび凸包定式化の両者の最良値,すなわちタイトな緩和を持つ計算的に軽量な定式化を獲得することにある。ε/P分割ε/ε定式化は,凸加法的に分離可能な制約をP分割に分割し,線形化および分割分離の凸包を形成するリフティング変換に基づいている。各論理和内で凸制約を持つ選言的制約に対して,π/P分割π/π定式化を導出し,論理和内で非凸制約を持つ場合に対する結果を一般化した。P分割定式化の連続緩和を解析し,ある仮定の下で,定式化はビッグM等価から始まり,凸包に収束する階層を形成することを示した。P分割定式化の目標は,計算的に単純な定式化により凸包の強い近似を形成することである。344の試験例において,P分割定式化をbig-Mおよび凸包定式化と計算的に比較した。テスト問題は,K-meansクラスタリング,半教師つきクラスタリング,P_ball問題,および訓練されたReLUニューラルネットワーク上での最適化を含む。計算結果は,P-分割定式化の有望な可能性を示した。多くの試験問題に対して,P分割定式化を凸包定式化と同様な数の探索ノードで解き,一方,解時間を1桁減らし,探索ノードの時間と数の両方でbig-Mを凌いだ。【JST機械翻訳】

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

数理計画法 , 図形・画像処理一般

, , , ,

前のページに戻る