2018年9月28日金曜日

要素技術開発がほぼ終了

ずっとSchedulingBenchmarkサイト問題に取り組んでいましたが、これは、NSPの特殊形であって一般系ではありません。現在、これを一般系でも動くように落とし込む作業を行っていますが、高いハードルで一筋縄では行きません。かなり複雑です。が、ほぼ形は見えたので、ようやく、今後の展開を考えることが出来ます。

1)手持ちベンチマークで検証  10月
2)NS2ベンチマークで検証   11月
3)NS1ベンチマークで検証       
4)まとめ               12月
5)実装ベータ版公開        1月
6)英語サイト公開          2月
7)DSL作成~            3月

特殊形では、ほぼWorldWideでトップ性能であることは、確認できたのですが、一般系でどのような性能になるのかが、未だ見えません。 こちらについては、10月以降検証を進めていきます。 上記ベンチマーク問題とプロジェクトファイルについては、英語サイトにして公開予定です。これで、One-StopのNSP問題集として、実問題を含めて網羅できると思います。新解の提示もいくつか出来ると思います。 

その後、Domain Specific Language 作成作業を行っていきたいと思います。 

開発中は、様々な文献を調査しました。門外漢である自分は、日本語での整数計画の本が少なくて困りました。連続系リニアでは、結構あるのですが、離散系である整数となると少ないのです。農工大の宮代先生が、近代科学社の最適化モデリングシリーズで書かれるようなので、そちらに期待というところです。

一般的な組み合わせ最適化問題と、NSPで何が違うかといういうとNSPは、組み合わせ最適化問題に包含される関係にあります。
前にも見たように、商用とフリーのMIPソルバーでは、いかんともしがたい性能差があります。ですから汎用である商用MIPソルバーに任せておけばよい、というのはある意味正しいです。実際、NSPのState Of Art Solverは、学術関係で発表されている全てのソルバーも含めても、Grobi/CPlexになると思います。残念ながら、学術関係ではない一般の方々が、StateOfArtソルバーを、手軽に使うことはできないですし、使い方もスキルを要します。
 NSPには、勤務シフトという他に例にないくらい複雑な制約郡と、多数の基数制約の組み合わせという特徴があります。この特殊な性質を上手に活用すると、State Of Artソルバー並みに、もしくはそれ以上に上手くいく場合もあります。State Of Artソルバー並みの性能と手軽に使うことができるGUI、そしてプログラマが使えるPython DSLを提供することがスケジュールナースの目標です。
さらにブラシュアップための知見は、現在の単純な線形目的関数値ではなく、機械学習や、AI的な手法によって得られると思います。現場に立脚した最適化は、個々の職場で違うと思うので、その目的のための道具としてPython DSLです。

0 件のコメント:

コメントを投稿

注: コメントを投稿できるのは、このブログのメンバーだけです。