研究室紹介OPAL-RING
村松 研究室
最適化アルゴリズムの開発およびその応用
| 所属 | 大学院情報理工学研究科 情報・通信工学専攻 |
|---|---|
| メンバー | 村松 正和 教授 |
| 所属学会 | 日本オペレーションズ・リサーチ学会、応用数理学会、Society for Industrial and Applied Mathematics （SIAM）、Institute for Operations Research and Management Science （INFORMS） |
| 研究室HP | http://jsb.cs.uec.ac.jp/ |
| 印刷用PDF |
掲載情報は2015年8月現在
- 村松 正和
Masakazu MURAMATSU
- キーワード
-
最適化問題、連続最適化、非線形計画、凸計画、錐線形計画、半正定値計画、2次錐計画、対称錐計画、内点法、オペレーションズ・リサーチ、アルゴリズム、スケジューリング
研究概要
いくつかの手段の中から最も適切なものを選び出す「最適化問題」を数学的手法で研究
当研究室では、広く「最適化問題」についてアルゴリズムの開発を行っている。
何らかの定量的な仕事を最も効率よく遂行するにはどうしたらよいか。こうした問題を大きく「最適化問題」と呼ぶことができる。機械制御、ファイナンスなど、多方面で「最適化問題」は現れる。
例えば、最近の当研究室のトピックとしては、海運会社の配船スケジューリングに関する研究が挙げられる。最適化アルゴリズムの適用により、従来人間のエキスパートが作成していたスケジュールに比べ、5%のコスト削減が可能なスケジュールを作成することができたのである。
人員配備計画にも最適化問題
また、一見最適化とは関係ないと思われる問題に、「最適化問題」が潜んでいることもよくある。
例えば、病院管理者が、何人かいる看護師の誰をどの時間帯に何時間働かせるか、各人にとって公平で不満が出ないような形で翌月のシフトを決めたいとする。こういうときが「最適化問題」の出番である。すなわち、各人の「満足度」をうまく数値化し、その「満足度」の総和を最大にするような数理的な問題（最適化問題）を考えて解くことにより、「最適な」人員配備計画を立てることができるのである。
非線形計画、凸計画、最先端の研究
当研究室では、多種多様な最適化問題に興味をもって研究しているが、特に「非線形計画」や「凸計画」といわれる最適化問題を中心テーマとしている。
最適化問題を解くアルゴリズムとしては、主に「内点法」という計算アルゴリズムの拡張を研究している。ちなみに「内点法」は世界で初めてそのアルゴリズムに特許が与えられたものである。
得意の錐線形計画
当研究室が非線形計画の中でも得意とするのは、2000年頃から話題になってきている「錐線形計画」という最適化問題である。この「錐線形計画」とその派生形の「半正定値計画」「2次錐計画」「対称錐計画」に関する研究では、当研究室は最先端を行くと自負している。
アドバンテージ
最新の最適化アルゴリズムの手法に広く通暁
- 与えられた点をすべて含む最小楕円
- 凸関数の最適化
最適化の技術は、①最適化問題という観点から自分の問題を眺める→②その問題を最適化問題にモデル化する→③最適化問題を解く→④得られた解を用いて自分の問題を解決する、というステップを踏んで利用されるのが一般的だ。
この中で最も重要なのはステップ①、すなわち日常的な問題に隠れている「最適化問題」に気づくことである。利用者が最適化問題に気づき興味をもてば、ステップ②の「モデル化」に進む。この段階で重要なのは、解決可能性の見極めである。
最適化問題にも簡単に解けるものと解けないものがあり、当然ながら解ける問題にモデル化する必要がある。解けない最適化問題にモデル化しても、ステップ③の「解く」に進めないのでは意味がない。この解決できる「モデル化」を見出すステップ②が、最適化問題の最大の難関とも言える。
当研究室は最適化の諸問題とアルゴリズムの各手法について通暁している。よって、企業の方が自分の問題は最適化問題と関係があるのではないかと気づいた場合、ステップ②とステップ③（モデル化とその解決）について、大いに協力できると思う。もちろん、既にしっかりとモデル化された解くべき最適化問題がある場合は、作業効率を上げるために最も望ましいアルゴリズムの提案（最適化の提案）などの点で、ご相談にのることも可能である。
特にここ数年の最適化技術の発達は目覚ましく、従来解けないとされていた問題が、次々と解けるようになってきている。こうした発展の成果を受けて、最新の技術を開発していることも、当研究室の強みである。
今後の展開
最適化=理論と応用のコラボレーション
最適化技術も机上で考えただけでは面白くない。現実のさまざまな問題を解くことができて初めて面白いのだ、と常々感じている。当研究室は、基礎研究と現実の問題を解くことの両方に、常に興味をもっている。
現在、基礎研究の対象としているのは「多項式最適化」という最適化問題である。これは簡単に言えば、多項式を用いて表現されるような最適化問題なのだが、その最適解を前述の「半正定値計画」を使ってエレガントに導けることが最近わかってきた。
この「多項式最適化」を解くためのソフトウェアを他大学と共同で開発したばかりであり、現在、その応用の場を探している。
企業の方から新たな問題を提示され、新たな最適化問題に出会うことは常に大きな楽しみである。こんな問題は解けるだろうかといったことがあれば、是非紹介していただきたい。
- バリア付き施設配置問題の最適解