１．担当ＰＭ

　伊知地　宏　（ラムダ数学教育研究所　代表）

２．採択者氏名

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

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

４．委託金支払額

　4,924,586円

５．テーマ名

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

６．関連Webサイト

　なし

７．テーマ概要

　本プロジェクトは，局所探索が使える制約プログラミングシステムを開発することを目標にしている．局所探索についてはいろいろな方法がすでに開発されているが，それらの手法は探索する問題に対する十分な知識がないと使えず，プログラミングも煩雑で，特に近傍関数のプログラミングが難しく，柔軟性に乏しいという問題がある．また制約プログラムは柔軟性があるものの，探索は大域探索アルゴリズムによるものがほとんどで探索時間が非常にかかるという問題がある．それに対して，局所探索問題に対する十分な知識がなくても，近傍関数を自動生成して局所探索を実施する制約プログラミングシステムを開発しようというものである．

８．採択理由

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

９．開発目標

　局所探索が使える制約プログラミングシステムを実現するためには2つの課題があり，それを実現することが開発目標となる．
　(1) 近傍関数の自動生成システム
　(2) 局所探索プログラムの開発支援システム

１０．進捗概要

　開発は予定よりも早く順調に進んでいたが，開発者が4月中旬に体調を崩し，以後完全に開発が止まってしまった．8月になって徐々に回復してきたものの，すでに開発を継続する残り時間があまりなく，4月時点での成果をまとめるだけで終わってしまった．素晴らしい成果が出る予感があっただけに残念である．

１１．成果

(1) 制約解消解消系本体の開発

　　当初の予定では既存の制約解消解消系Creamを用いる予定であったが，
　　(a)柔軟性に乏しく提案手法を適用しづらい，
　　(b)遅い
　という二つの理由から，制約解消系を新しく書き直した．新しい制約解消系を，便宜上 "veecon" と仮称する．
　　Creamに対するveeconの改良は主に3つある．
　　(a) メタ制約(AND, OR, NOT等)の導入
　　(b) ranch-and-boundループの高速化
　　(c) 変数ドメイン表現の動的最適化
　このうち (a) が柔軟性，(b) と (c) が速度に寄与する．(b)はいわゆる「ループ最適化」である．またそれができるようにデータ構造も変えた．(c) はドメインの大きさによって適切な (≒最も高速な) ドメイン表現に切り替えるものである．Cream (ver.2) にも同様の機能はあったが，表現が2種類から3種類に増え，より細かな制御が可能になっている．
　ILOG Solverは商用制約解消系の中でも最も速いもののひとつであるが，基礎的なベンチマークで比較すると，ILOG solverに対して
　　Cream: 十数倍から数十倍
　　veecon: 2.0-3.0倍
　程度の時間がかかった．このように，基本的な制約解消速度が，商用製品と比較しうる程度にまで大きく改善された．ただし，メモリ効率の点ではILOGに大きく遅れを取っているのでこちらの改善も必要である．

(2) 近傍生成アルゴリズムの開発・改良

(2-1)　2次元カッティング問題への適用
　2次元カッティング問題では
　　(a) 1枚の大きな矩形の板(の寸法)
　　(b) (a)よりは小さい複数の異なる矩形の板(の寸法)
　　(c) (b)の板それぞれの価値(目的関数)
　　(d) (b)の板それぞれの最低/最大切り出し枚数．(制約条件)
　が与えられる．目的は，(a)の板から(d)を満たすように(b)の板を切り出して，切り出された板の価値の合計値を最大化することである．
　単純化していうと，それぞれの板pについて「切り出す」「切りださない」を決定することが重要である．板pを切り出す場合，「板pは大きな板(a)からはみ出さない」という制約が加わり，さらに「板pは他の切り出される板と重ならない」という制約も加えられる．
　以前のアルゴリズム (Cream ver.2) では上のすべての制約を一度全部加えてから最適化を行っていた．つまり，全ての板について切り出すか切り出さないかを決めてから最適化を行っていた．しかし，加えられる制約間にコンフリクトがあった場合 (つまり解が存在しない場合) その間の時間は無駄になってしまう．
　新しいアルゴリズムでは「制約プール」という制約のコンフリクトを監視するようなオブジェクトを用意し，そこにひとつずつ制約を入れていくことにした．これにより，途中でコンフリクトが発見されればそこで中止して次のステップに進むことができる．これで無駄な時間を減らすことができ，近傍生成ループ全体の速度を向上させることができる．それを実装した結果，従来の近傍生成法より良い解を(平均的に)より早く発見することができるようになった．
　ただし，「全体として(平均的に)速くなった」ことを確かめただけで，内部動作の詳しい解析はまだ行っていない．すなわち，そのアルゴリズムによって実際に
　　(a) 近傍生成時の矛盾の発生は減少したか,
　　(b) 近傍生成の時間が短くなったか,
　という二点について，はっきりと確認がとれてはいない．これを調べることは
　　(a) プログラムが確率的動作をする
　　(b) 新手法と旧手法がveeconとcreamという別の制約エンジ上で動いている
　点からすこし難しい．しかし，今後のためにこの解析は必要である．

(2-2) 0-1最適化問題への適用
　0-1最適化問題は，整数最適化問題の一種で(ほぼ)全ての変数が値として0か1をとるものを言う．変数の数が非常に多いのが特徴である．問題が線形であれば商用/非商用の一般型整数計画法ソフトを使うと良い．しかし問題が非線形になると，対象となっている問題に特化したソルバーがなければ実用的解を得るのは難しいというのが現状である．
　さて，提案手法 (近傍自動生成による局所探索) でこの問題にアタックするのは，二次元カッティングの場合よりも難しい．それは(0-1)整数計画問題では制約条件が全て変数の(非)線形(不)等式であらわされ，「p OR q」といった明示的な選言的制約は現れないからである．
　単純に思いつく方法のひとつとして，それぞれの0-1変数xについて「x=0 OR x=1」という制約条件があるものとして無理やり選言的制約に変換する方法があるが，この方法は各変数に0/1を割り当てるのを遠回りにしているだけで意味がない．それに，変数の数が多いから制約の数も比例して多くなり，提案手法では処理しきれないと考えられる．
　現時点ではまだこちらの問題には手をつけていない．しかし提案手法の適用範囲を広げるために避けて通ることはできない．

１２．プロジェクト評価

　9ヶ月の開発期間のうちおよそ半分の5ヶ月間くらいしか開発を行えなかったにもかかわらず，「0-1最適化問題への適用」以外の課題をほとんど解決した．ざっと見て当初目標の70%を達成したと考えられる．

　・未踏性: A
　　大域探索アルゴリズムを近傍関数の自動生成で局所探索アルゴリズムにしようというもので，その未踏性は高い．
　・先進性: A
　　制約プログラミングシステムを商用製品に近いレベルに持っていくなど，プログラミング技術能力はきわめて高い．
　・実用性: B+
　　現在のシステムは「0-1最適化問題への適用」が出来ていないため，実用性という面ではそんなに評価は高くない．
　・社会への影響: A-
　　局所探索問題は日常生活においてもいろいろ存在し，システムの存在価値，社会への影響は比較的高いと思われる．
　　(A: 高い，B: 並，C: 低い)

　開発期間をフルに活躍できれば，物凄い成果をあげ，スーパークリエータは間違いなかっただけに残念である．

１３．今後の課題

　まずは是非ともシステムを完成させてもらいたい．そして，システムがいろいろな局所探索問題に対して有効かどうかを検証してもらいたい．