組合せ最適化、アルゴリズム、オペレーションズ・リサーチ

「 A 地点から B 地点までなるべく速く移動したい」と思ったとき、Google Map などのナビゲーションシステムを使えば、どんな経路を選べば良いかが瞬時に分かります。この背後には、地図データの正確さやコンピュータの計算能力の高さに加え、「具体的な計算の手順を定める」アルゴリズムの力が潜んでいます。同じ入力に対して同じ結果を出力するのにも、アルゴリズムによってその手間は数万倍にも数億倍にもなり、0.1 秒で終わるか 1 年かけても終わらないかという大きな違いが生まれることもあります。したがって、効率的なアルゴリズムを設計・選択することは、問題解決において重要な役割を果たします。

私は、前述の経路探索のような「与えられた条件を満たす中で、決められた指標に関して最も良い組合せを見つけたい」という問題を扱う組合せ最適化を中心に研究しています。個別の問題を解く効率的なアルゴリズムやその難しさを考えるのはもちろん、「どのような組合せ構造や性質を持つ問題が、どのようなアルゴリズムによって効率的に解けるのか」ということを抽象的・統一的に整理することに興味があり、離散数学（グラフ・ネットワーク、マトロイド、劣モジュラ性、離散凸性など）の理論とも関連した研究を行っています。

経路探索の他にも、「学生を研究室にできるだけ公平に（双方が不満を抱かないように）割り当てたい」、「低いリスクで高いリターンを得られるように分散的に投資したい」、「電力網や交通網，通信ネットワークなどを、低コストで頑健に設計したい」など、世の中には様々なタイプの要望が溢れています。そのような状況を数理の力で分析し、意思決定をサポートする学問を、オペレーションズ・リサーチといいます。私を含め、本研究室では、組合せ最適化や離散アルゴリズムに限らず、広くオペレーションズ・リサーチに関する研究を行っています。