WEKO3
アイテム
低次元分数和計画問題に対する効率的なアルゴリズムに関する研究
https://doi.org/10.15118/00005122
https://doi.org/10.15118/000051223a13de5b-4f1a-45a9-84cd-07d0f1dfcbda
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
A366 (617.9 kB)
|
|
|
|
A366_summary (447.3 kB)
|
|
| アイテムタイプ | 学位論文 / Thesis or Dissertation(1) | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2014-12-04 | |||||||||||
| タイトル | ||||||||||||
| タイトル | Efficient Algorithms for Solving the Sum of Linear Ratios Problem with Lower Dimension | |||||||||||
| 言語 | en | |||||||||||
| タイトル | ||||||||||||
| タイトル | 低次元分数和計画問題に対する効率的なアルゴリズムに関する研究 | |||||||||||
| 言語 | ja | |||||||||||
| 言語 | ||||||||||||
| 言語 | eng | |||||||||||
| 資源タイプ | ||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_db06 | |||||||||||
| 資源タイプ | doctoral thesis | |||||||||||
| ID登録 | ||||||||||||
| ID登録 | 10.15118/00005122 | |||||||||||
| ID登録タイプ | JaLC | |||||||||||
| アクセス権 | ||||||||||||
| アクセス権 | open access | |||||||||||
| アクセス権URI | http://purl.org/coar/access_right/c_abf2 | |||||||||||
| 著者 |
胡, 勇文
× 胡, 勇文
|
|||||||||||
| 抄録 | ||||||||||||
| 内容記述タイプ | Abstract | |||||||||||
| 内容記述 | 分数和問題(Sum Of Liner Ratios Problem,SOLR)はNP困難な問題としてよく知られており，その応用領域の広さから数多くの応用および最適解探索のための研究がなされている。実問題における幅広い問題がSOLRとして定式化することが可能であり，その多くが少数変数かつ膨大な分数比を有しているという特徴を持つ。本論文は低次元におけるSOLR問題に焦点を当てた新たな効果的アルゴリズムの提案およびその検証を行った。主な成果を以下に示す。 | |||||||||||
| 言語 | ja | |||||||||||
| 抄録 | ||||||||||||
| 内容記述タイプ | Abstract | |||||||||||
| 内容記述 | ●低次元SOLR問題を統括的に解くための2分岐ルールに基づく分枝限定法を提案した。具体的には， SOLR問題を線形目的関数と2次および1次の制約を持つ2次計画問題へ変換し，補助変数を利用して全ての2次制約に対して線形緩和を行い2次の緩和問題を生成する。その問題に対して新たな2分岐ルールに基づく分枝限定法を適用する方法を考案し，先行研究手法（Carlsson and Shi）に対する優位性の検証を行った。数値結果より，最適解に対する解精度はもちろん，CPU時間，繰り返し回数，平均枝数などにおいても先行研究を大きく凌駕していることを明らかにした。 | |||||||||||
| 言語 | ja | |||||||||||
| 抄録 | ||||||||||||
| 内容記述タイプ | Abstract | |||||||||||
| 内容記述 | ●提案する分枝限定法では，低次元SOLR問題を包括的に解くために新たな分岐メカニズムを採用している。本メカニズムでは，もし現在のベストを含む長方形領域が2 つのサブ長方形領域に分割された場合，現在の最良解が両方のサブ領域に属するような分岐を行う。数値実験では，異なる分岐ルールを使用した場合との比較を行い変数p ³ 30の場合において良好な平均CPU時間において解導出可能であることを示した。また，pの増加に伴いCPU時間減少率はさらに増加することも明らかにした。 | |||||||||||
| 言語 | ja | |||||||||||
| 抄録 | ||||||||||||
| 内容記述タイプ | Abstract | |||||||||||
| 内容記述 | ●低次元SOLR問題に対してDIRECT法の適用についても検討を行った。数値結果から高い確率（99。99%）かつ少ない計算時間で解けることを確認することができた。 | |||||||||||
| 言語 | ja | |||||||||||
| 学位授与機関 | ||||||||||||
| 学位授与機関識別子Scheme | kakenhi | |||||||||||
| 学位授与機関識別子 | 10103 | |||||||||||
| 学位授与機関名 | 室蘭工業大学 | |||||||||||
| 言語 | ja | |||||||||||
| 学位授与機関名 | Muroran Institute of Technology | |||||||||||
| 言語 | en | |||||||||||
| 学位名 | ||||||||||||
| 学位名 | 博士（工学） | |||||||||||
| 言語 | ja | |||||||||||
| 学位の種別 | ||||||||||||
| 言語 | ja | |||||||||||
| 値 | 課程博士 | |||||||||||
| 学位授与番号 | ||||||||||||
| 学位授与番号 | 甲第366号 | |||||||||||
| 報告番号 | ||||||||||||
| 言語 | ja | |||||||||||
| 値 | 甲第366号 | |||||||||||
| 学位記番号 | ||||||||||||
| 言語 | ja | |||||||||||
| 値 | 博甲第366号 | |||||||||||
| 学位授与年月日 | ||||||||||||
| 学位授与年月日 | 2014-09-25 | |||||||||||
| 日本十進分類法 | ||||||||||||
| 主題Scheme | NDC | |||||||||||
| 主題 | 418 | |||||||||||
| 著者版フラグ | ||||||||||||
| 出版タイプ | VoR | |||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||||
| フォーマット | ||||||||||||
| 内容記述タイプ | Other | |||||||||||
| 内容記述 | application/pdf | |||||||||||
