１．担当ＰＭ

　伊知地　宏

２．採択者氏名

３．プロジェクト管理組織

　日本エンジェルズインベストメント株式会社

４．採択金額

　6,000,000円

５．テーマ名

　 局所探索が使える制約プログラミングシステムの開発

６．関連Webサイト

　なし

７．テーマ概要（採択者）

　困難な組合せ最適化問題を効率良く解くことの重要性がますます高まっている。
伝統的なアプローチのひとつに、山登り法やタブーサーチ、遺伝的アルゴリズムをはじめとする局所探索がある。局所探索は非常に探索効率が良く、現在でも組合せ最適化問題に対する最も効果的な手法のひとつである。しかし、局所探索プログラムを設計するには対象とする問題についての詳しい知識が必要で、コーディングも煩雑である。特に「近傍関数」のコーディングが難しい。また作られたプログラムが問題に特化したものになり、柔軟性に乏しいという問題もある。

　他方、新しいアプローチとして制約プログラミングが注目を集めている。制約プログラミングでは、プログラマは問題の制約条件と目的関数を記述して制約システムに渡すだけで良い。解の探索は制約システムが自動で行う。このように汎用性・簡便性・柔軟性が制約プログラミングの大きな利点であるが、反面、探索アルゴリズムが多くの場合バックトラックと分枝限定法による大域探索のみであり、探索効率が悪い。

　本プロジェクトの目標は、「局所探索が使える制約プログラミングシステム」を作ることである。開発項目は大きくふたつの項目に分かれる：

１．近傍関数の自動生成システム
これにより、問題の制約条件と目的関数を記述するだけで局所探索が適用可能になり、従来の大域探索より効率良く解が求まるようになる。
２．局所探索プログラムの開発支援システム。
制約プログラミングの特性を利用して、局所探索プログラムの開発・改良を支援する。

　最後にこれらをひとつの制約プログラミングシステムとして統合する。本提案により、大域探索か局所探索かの二者択一ではない両方の利点を生かしたような最適化手法を確立できれば良いと考えている。

８．採択理由（担当ＰＭ）

　局所探索プログラムは，近傍関数などを人がプログラミングして特化させるのが普通である．提案者はその近傍関数を自動生成して，大域探索プログラムのままで局所探索を行える理論を大学院修士課程で研究した．しかし，その研究成果では効率の良い局所探索プログラムを生成することは難しい．そこで，もっと効率的な局所探索プログラムを生成できるメカニズムを開発しようというのが提案の主な内容である．開発内容は画期的であり，理論的にもしっかりしていて，大きな成果を得られる可能性が十分にある．その一方で失敗する可能性も高く，まさに未踏性の極めて高い，ある種危険なプロジェクトである．うまく完成すると実用性もかなり高いと予想される．提案者は大学院博士課程の学生であるが，研究室の方針で博士論文のテーマは本テーマと異なるものであり，是非とも未踏ソフトウェア創造事業でこの開発をしたいという意気込みが特に気に入った．