Γロバスト最適化における最悪シナリオ

• Item type: SIG Technical Reports(1)
• 公開日: 2018-05-18
• タイトル: Γロバスト最適化における最悪シナリオ
• タイトル / 言語: en
• タイトル: Worst-Case Scenario Lemma for Γ-Robust Optimization
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 名古屋大学
• 著者所属: 成蹊大学
• 著者所属: 名古屋大学
• 著者所属(英): en
• 著者所属(英): Nagoya University
• 著者所属(英): en
• 著者所属(英): Seikei University
• 著者所属(英): en
• 著者所属(英): Nagoya University
• 著者名: 張, 佳宝; 呉, 偉; 柳浦, 睦憲
• 著者名(英): Jiabao, Zhang; Wei, Wu; Mutsunori, Yagiura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 解のロバスト性を考慮した組合せ最適化問題に関する研究が近年盛んになっており，経済，建築，都市計画，化学など多くの分野で応用されている．本研究では，max-min 評価基準の下で，入力データの摂動レベルを考慮したロバスト組合せ問題に対する汎用的な最悪シナリオ補題を提案する．また，この補題を用いた厳密解法と発見的解法を Γ ロバスト max-min ナップサック問題に対して提案し，その性能を計算実験により評価する．厳密解法に対する計算実験では，アイテム数 2000 以下の全ての問題例に対して，2 時間以内に最適解が得られた．発見的解法に対する計算結果より，提案手法が高速であり，アイテム数 10000 までの大規模な問題例に対しても 3 分以内に解が得られること，および最適値が分かっている問題例の全てに対して厳密な最適解を得ており，解の精度が高いことが確認できた．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Robust optimization is motivated by practical applications and deals with optimization problems in which some input parameters are uncertain. In this paper, we consider Γ-robust combinatorial optimization problems under max-min criterion. For this type of problem, we propose and prove a general lemma that we call the worst-case-scenario lemma : it specifies a worst-case scenario for a given solution. Based on the worst-case-scenario lemma, we propose an exact dynamic programming algorithm and a heuristic algorithm for the Γ-robust knapsack problem under the max-min criterion. Furthermore, we propose some lemmas to reduce the running time of the dynamic programming algorithm. The computational results show that our exact algorithm solves the Γ-robust knapsack problem exactly in reasonable time (less than two hours) for instances with up to 2000 items, and the heuristic algorithm obtains high-quality solutions in less than three minutes for instances with up to 10000 items.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2018-AL-168, 号 3, p. 1-6, 発行日 2018-05-18
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会