Research Activities in Discrete Mathematics Group

茨木の研究内容紹介

研究分野： 離散数学、オペレーションズ・リサーチ、組合せ最適化、グラフ・ネットワーク、ブール関数、アルゴリズム、メタヒューリスティクス（遺伝アルゴリズム、タブー探索、アニーリング法など）、計算の複雑さ、それらの応用（スケジューリング、データの論理的解析、データベース、分散システム、ゲーム理論、ゲームアルゴリズム）など。

茨木は離散最適化問題(あるいは組合せ最適化問題) と呼ばれる問題を扱っています。このタイプの問題は、カーナビで使われている最短路問題、このホームページのトップにもある巡回セールスマン問題（n 点を巡回する最短閉路を見つける問題）、いろいろな制約の下での時間割表・勤務表の作成問題、与えられた図形の集合をできるだけ小さな領域に詰め込む問題、生産工場における作業の順序をきめるスケジューリング問題など、身近にいくらでもころがっています。これらの問題は、その意味を理解するのは簡単なのに、解を求めることが大変難しいという性質を共有しています。もちろん、コンピュータを用いなければ解くことはできませんが、解くためのアルゴリズム(計算手順)をよく考えないと、やみくもにコンピュータをぶん回すだけでは駄目です。我々のグループは、離散数学の立場からこれらの数学的性質を研究し、問題が持つ計算の複雑さを理論的に明らかにするともに、その成果を具体的な問題の解決に利用するため、アルゴリズムの開発に従事しています。この研究は、オペレーションズリサーチ、コンピュータ科学、システム工学、さらには経営学、経済学、社会科学にいたる広い領域に、さまざまな形で関連しています。

（１）問題解決エンジンの構築に関する研究

組合せ最適化問題がどれをとっても結構困難な問題であることを考えると、すべての問題を個別に考えるというアプローチでは破綻してしまいます。できるだけ幅広い問題を扱えるような標準問題をいくつか設定して、それらに対し、高性能のアルゴリズムを開発しておくというアプローチが現実的です。それらを問題解決エンジンと呼んでいます。下の図はこのアプローチを示したもので、どのような標準問題を考えているかも見て取れるでしょう。

（2）近似アルゴリズムの枠組み、メタヒューリスティクスの研究

汎用性の高い標準問題を、実用的な意味で解くには、厳密解をあきらめて近似解で満足せざるを得ません。実用的には近似解で十分な場合がほとんどです。しかし、近似解といっても、精度の高い近似解を高速に求めるには、アルゴリズムの工夫と理論的な裏づけが必要です。メタヒューリスティクスは最近とくに注目されている枠組みで、遺伝アルゴリズム、タブー探索、アニーリング法、反復局所探索法、などを含んでいます。この中のいくつかの名前は聞いたことがあるという人もいるでしょう。我々は、上の問題解決エンジンをメタヒューリスティクスに基づいて開発しています。下の図は、配送計画問題と2次元長方形詰込み問題について、ランダムな初期解から出発して、良質な解を得ている様子を示しています。

（3）組合せ最適化問題の複雑さとアルゴリズムに関する研究。

さまざまな組合せ（最適化）問題を対象とし、それらの計算の複雑さ、とくに多項式時間で解ける問題とＮＰ困難問題の理論的分類を行い、前者に対してはより効率の良いアルゴリズムの開発、後者に対しては、動的計画法や分枝限定法などの厳密解法とともに、メタヒューリスティクスによる近似アルゴリズムの研究に取り組んでいます。

（4）グラフ・ネットワーク問題の研究。

グラフやネットワークは、離散数学の代表的な話題であり、応用という観点からも重要です。これまで、グラフの最小カット、連結度、単品種および多品種フローなどを計算する効率よい多項式時間アルゴリズムを開発するとともに、ＮＰ困難である彩色問題、最大クリーク問題、k-分割問題などについても、厳密および近似アルゴリズムを手がけてきました。

（5）データの論理的解析とブール関数(論理関数)の研究。

貯えられたデータを処理して、データが語る内容を論理的な知識（すなわちブール関数による表現）として取り出す研究を行っています。これは最近よく話題になっているデータマイニングに関連しています。我々のアプローチは、データを不完全定義ブール関数とみなして、その拡大を求める問題と解釈することで、関連する問題の計算の複雑さを明らかにし、実際のデータに適用するためのアルゴリズムを開発するというものです。この新しい視点から、ブール関数を見直す作業も行っており、正関数、ホーン関数、分解可能関数、自己双対関数などについて新しい知見を得ています。

今後の展望

以上のようなテーマは、離散数学の観点から奥深い内容を持つものが多く、数学としての興味は尽きることがありません。また最近のアルゴリズムや計算の複雑さの理論の発展をうけて、新しい展開を遂げつつある分野でもあります。一方、応用の立場からも、これらの成果の利用が強く求められており、数理計画、人工知能、ニューラルネットワーク、ファジイ理論などとともに、問題解決手法の重要な一翼を担っています。この目的に用いることのできる実用的なソフトウェアへの期待も大きいと感じています。理論と応用のバランスを保つことを忘れず、かつ研究を楽しみながら、その成果を現実の問題解決に少しでも役立てることができるよう、努力したいと思っています。

茨木研究室のホームページへ