| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2018-05-26 14:30 Γロバスト最適化における最悪シナリオ 張 佳宝（名大）・○呉 偉（成蹊大）・柳浦睦憲（名大）  COMP2018-1 |
|
| 抄録 | （和） | 解のロバスト性を考慮した組合せ最適化問題に関する研究が近年盛んになっており，経済，建築，都市計画，化学など多くの分野で応用されている．本研究では，max-min 評価基準の下で，入力データの摂動レベルを考慮したロバスト組合せ問題に対する汎用的な最悪シナリオ補題を提案する．また，この補題を用いた厳密解法と発見的解法をΓ ロバストmax-min ナップサック問題に対して提案し，その性能を計算実験により評価する．厳密解法に対する計算実験では，アイテム数2000 以下の全ての問題例に対して，2 時間以内に最適解が得られた．発見的解法に対する計算結果より，提案手法が高速であり，アイテム数10000 までの大規模な問題例に対しても3 分以内に解が得られること，および最適値が分かっている問題例の全てに対して厳密な最適解を得ており，解の精度が高いことが確認できた． |
| （英） | 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 speci es 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 three 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. |
|
| キーワード | （和） | ロバスト最適化 / Γロバスト / max-min 基準 / 最悪シナリオ / ナップサック問題 / 動的計画法 / / |
| （英） | robust optimization / Γ-robust / max-min criterion / worst-case scenario / knapsack problem / dynamic programming / / | |
| 文献情報 | 信学技報, vol. 118, no. 68, COMP2018-1, pp. 17-24, 2018年5月. | |
| 資料番号 | COMP2018-1 | |
| 発行日 | 2018-05-18 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2018-1 |
|
| 研究会情報 | |
| 研究会 | COMP IPSJ-AL |
| 開催期間 | 2018-05-25 - 2018-05-26 |
| 開催地（和） | 名古屋工業大学 |
| 開催地（英） | Nagoya Institute of Technology |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2018-05-COMP-AL |
| 本文の言語 | 日本語 |
| タイトル（和） | Γロバスト最適化における最悪シナリオ |
| サブタイトル（和） | |
| タイトル（英） | Worst-Case Scenario for Γ-Robust Optimization |
| サブタイトル（英） | |
| キーワード(1)（和/英） | ロバスト最適化 / robust optimization |
| キーワード(2)（和/英） | Γロバスト / Γ-robust |
| キーワード(3)（和/英） | max-min 基準 / max-min criterion |
| キーワード(4)（和/英） | 最悪シナリオ / worst-case scenario |
| キーワード(5)（和/英） | ナップサック問題 / knapsack problem |
| キーワード(6)（和/英） | 動的計画法 / dynamic programming |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 張 佳宝 / Jiabao Zhang / チョウ カホウ |
| 第1著者 所属（和/英） | 名古屋大学 (略称： 名大) Nagoya University (略称： Nagoya Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 呉 偉 / Wei Wu / ゴ イ |
| 第2著者 所属（和/英） | 成蹊大学 (略称： 成蹊大) Seikei University (略称： Seikei Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 柳浦 睦憲 / Mutsunori Yagiura / ヤギウラ ムツノリ |
| 第3著者 所属（和/英） | 名古屋大学 (略称： 名大) Nagoya University (略称： Nagoya Univ.) |
| 講演者 | 第2著者 |
| 発表日時 | 2018-05-26 14:30:00 |
| 発表時間 | 30分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2018-1 |
| 巻番号（vol） | vol.118 |
| 号番号（no） | no.68 |
| ページ範囲 | pp.17-24 |
| ページ数 | 6 |
| 発行日 | 2018-05-18 (COMP) |
[研究会発表申込システムのトップページに戻る]