Gomory混合整数カットの分岐-カットと学習可能性の構造解析【JST・京大機械翻訳】

Balcan Maria-Florina; Prasad Siddharth; Sandholm Tuomas; Vitercik Ellen

プレプリント

J-GLOBAL ID：202202206145609366 整理番号：22P0332600

Gomory混合整数カットの分岐-カットと学習可能性の構造解析【JST・京大機械翻訳】

Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts

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

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

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

分岐および切断として知られる分岐および結合アルゴリズム内の切断面の組み込みは,現代の整数計画ソルバのバックボーンを形成する。これらのソルバは,離散最適化問題を解くための最上の方法であり,従って,機械学習,操作研究,および他の多くの分野での応用の広大な配列を持っている。切削面の選択は,整数計画の理論と実践における主要な研究題目である。著者らは,アルゴリズムのあらゆるステップが入力整数プログラムに加えられた切断面を定義するパラメータの変化によってどのように影響を受けるかを突き止める分岐とカットの新しい構造解析を行った。この解析の主な応用は,切断面が分岐とカットの間に適用するために,機械学習を使用するためのサンプル複雑性保証を導くことである。これらの保証は,整数計画ソルバの主なブレークスルー高速化の原因となるGomory混合整数カットのファミリーのような切断面の無限ファミリーに適用する。解析における分岐とカットの幾何学と組合せ構造を利用して,分岐とカットの最近の一般化理論のために重要な欠測部分を提供した。【JST・京大機械翻訳】

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

数理計画法 , 化学プロセスの解析

, , ,

前のページに戻る