基数制約を持つ多重線形集合の凸化:構造特性,入れ子の場合および拡張【JST・京大機械翻訳】

Chen Rui; Dash Sanjeeb; Gunluk Oktay

プレプリント

J-GLOBAL ID：202202209785583281 整理番号：21P0042060

基数制約を持つ多重線形集合の凸化:構造特性,入れ子の場合および拡張【JST・京大機械翻訳】

Convexifying Multilinear Sets with Cardinality Constraints: Structural Properties, Nested Case and Extensions

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

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

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

二値変数の多重線形関数を最小化する問題は,よく研究されたNP困難問題である。この問題の標準線形化の解の集合は,多重線形集合と呼ばれる。著者らは,非ゼロ変数の数に関して上限および下限を有するそれの基本的制約バージョンを研究した。この問題の標準的線形化の解の集合を,基本制約を持つ多重線形集合と呼ぶ。これらの多重線形項(適切性)に関する一連の条件を特性化し,これらの条件下で,集合の凸包記述は拡張定式化により扱いやすいことを観察した。次に,多重線形項が入れ子構造を持つときの凸包の明示的多面体記述を与えた。この記述は,多項式時間で分離できる不等式の指数数を持つ。最後に,これらの不等式を一般化事例に対して有効な不等式を得るために一般化した。【JST・京大機械翻訳】

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

数理計画法

, , , , ,

前のページに戻る