2018年5月20日日曜日

MIPソルバーの評価

例のベンチでの評価結果です。厳密解を得るまでの時間を
まとめてみました。(NEOSサーバによる)Instance8だけは、5分内に厳密界を得ることができず、最良値を書いています。
なお、自分のエンジンについては、Pieter Smetさんの解を元に解析を進めてバグをFIXすることが出来、無事、厳密解1300を得ることが出来ました。


 CBCSCIPCplexGurobi
Instance11.81.670.150.27
Instance24.624.680.660.98
Instance3 30.33.11.62
Instance4 51.513.184.53
Instance5 235.0456.9134.39
Instance6  30.1514.7
Instance7  84.95113.54
Instance8(厳密解1300(300sec)  16651794 

2018年5月16日水曜日

Benchmark 評価

http://www.schedulingbenchmarks.org/

のうち最初の8題をやってみました。
最後の1題を除いてOptimum値が一致しました。

最後の1題、Instance8は、ベルギー、ルーヴェン・カトリック大学 Pieter Smetさんによる新しい解がOptimumとされています。 (CPLEXでも最適値は求まっていません。)

それまでは、長らくノッティンガムの1308という解がBestでした。私の解(開発中エンジン)は1301で、下記値と一致していません。サイトには、解のファイルも置いていますが、残念ながら、最新の結果を反映したものではありません。

そこで、Pieter Smetさんにお願いして、解を頂いて解析することにしました。
→頂きました。なおPieter Smetさんの論文は、レビュー中であり未だオープンになっていないそうです。

下記インスタンスは、去年のRAMP講演でも発表しましたが、SATにとって苦手なインスタンス郡です。厳密解が得られたのは、Instance1のみで、その他は、近似解で、規模が大きくなるに従い乖離
が大きくなる傾向にありました。
InstanceWeeksEmployeesShift typesBest known lower boundBest known solution
Instance1 281607607
Instance2 2142828828
Instance3 220310011001
Instance4 410217161716
Instance5 416211431143
Instance6 418319501950
Instance7 420310561056
Instance8 430413001300

2018年5月6日日曜日

海外ベンチマーク動向

最近の学術研究動向について述べます。

ナーススケジューリングコンペティションは、過去2回あり、最初のコンペ2010では、法政大の野々部先生が、2位になられています。

https://www.kuleuven-kulak.be/nrpcompetition

2回目(2015)は、RAMP講演でも述べましたが、私も参加しました。
http://mobiz.vives.be/inrc2/

こちらは、動的に勤務表問題を解くものであり、異色のベンチでした。ちょっとこれでは、性能比較しにくいということで、最近は、STATICにしたベンチマークでの論文が出ています。

1回目のベンチについては、ほぼ全部の最適解が分かっています。2回目のSTATIC Versionでは、ほぼ最適解は、解けていません。(やっている人が少ないかもしれません。)

簡単なものから、未解決の超難問がそろっているのは、ノッティンガムの24の前奏曲です。

http://www.schedulingbenchmarks.org/

こちらは、2017に衝撃がありました。整数計画ソルバで大半の未解決問題が解かれてしまいました。 おそらくは、Gurobiだと思うのですが、こちらをキャッチアップするのは、容易でないでしょうが、目指しているは皆さん、そこだと思います。 ちなみにオープンソースで定評のあるCBCを使っても、解けるのは、もっともやさしい1-2問程度です。商用ソルバとの実力差は、いかんともしがたいです。

2014年度の結果は、こちらで、
http://www.schedulingbenchmarks.org/papers/computational_results_on_new_staff_scheduling_benchmark_instances.pdf

ここ数年で見ても急速に向上していることが分かると思います。整数計画ソルバ恐るべしです。

とはいえ、そのGurobiをもってしても、手ごわいのが池上先生のベンチです。(詳細は池上先生の著作をごらんください。) ただ、池上先生のベンチは、SATソルバを持ってすると簡単に解けてしまうという不思議な世界がNSPです。 この原因は、大体分かりましたが、述べるには余白が足りません。別の機会に。

日本からも、学術用のコンピュータで作成したベンチではなく、あくまで人間が作成したベンチを公開していきたいと思います。ただ、その際に、自分だけが解ける問題だけを載せてもあまり説得力がないので、上記ベンチマーク結果についても、検証ができるようにしていきたいと思います。






2018年5月2日水曜日

池上先生の本が出ました

https://www.amazon.co.jp/%E3%83%8A%E3%83%BC%E3%82%B9%E3%83%BB%E3%82%B9%E3%82%B1%E3%82%B8%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%EF%BC%9A%E5%95%8F%E9%A1%8C%E6%8A%8A%E6%8F%A1%E3%81%A8%E3%83%A2%E3%83%87%E3%83%AA%E3%83%B3%E3%82%B0-%E3%82%B7%E3%83%AA%E3%83%BC%E3%82%BA%EF%BC%9A%E6%9C%80%E9%81%A9%E5%8C%96%E3%83%A2%E3%83%87%E3%83%AA%E3%83%B3%E3%82%B0-%E6%B1%A0%E4%B8%8A-%E6%95%A6%E5%AD%90-ebook/dp/B07B4S2GMG

です。世界的に見ても、ナーススケジューリングに関するこれほどの本は、ないのではないでしょうか? 私は、取り組み始めて未だ数年ですが、研究の変遷等、「そうだったんだ」と腑に落ちる部分も多々あります。OR学会関係の書物は、数式が多いのに閉口しますが、数式は少ないので読み物としても面白く読めます。普通の学術・技術書にはない、その問題に至る過程や、苦闘の様子などが語られていて、一線を画するユニークな学術書になっています。

組み合わせ最適化に関心のある研究者、技術者、大学院生、学部生には必携の書でしょう。


2018年4月21日土曜日

MaxSat Evaluation 2019 Call for Participation

去年参加したので、主催者様から、ご案内を頂きました。(なぜかタイトルが2019になっていますが。)

現在、私は、新しい発想のソルバを検証中なのですが、MaxSATの形で入れ込むには、時間が足りないので今年は、参加を見送ります。

最近、MAXSAT Communityの性能向上は、停滞ぎみなので、新規参入には良いチャンスです。

*MaxSAT Evaluation 2018 (MSE-2018)*
*Call for Participation*
Submissions Deadline: *May 31st, 2018*
Results disclosed in July 2018 at Sat-2018, Oxford, UK
The MaxSat Evaluation is designed to provide a snapshot of current
progress in solving MaxSat by running submitted MaxSat solvers on a
heterogenous collection of benchmark instances.
MSE 2018 will be the 13th annual MaxSat Evaluation. We
welcome contributions of two types from the community at large:
a) New MaxSAT benchmarks encoding instances of interesting
     NP-hard optimization problems, and
b) implementations of MaxSAT solvers that will be evaluated
    within MSE 2018 on a heterogenous collection of benchmarks.
Please visit
https://maxsat-evaluations.github.io/2018/
For more information, and details about participating.
  We look forward to your participation
  MSE-2018 organizing committee


2018年4月8日日曜日

特許は技術者の履歴書

特許検索で自分の名前を打つと、20数件の自分が関連した特許出願がヒットします。その多くは、会社員時代、アルプス電気で出願したものです。ソニーとのジョイントプロジェクトもありましたので、厚木や大崎で、出願したことがあります。特許は、論文に似て、技術的には、携わらなくても忖度して上司や、同僚の名前を載せることがあります。ステッピングモータ・スピンドルモータ関連でも自分の名前が出てくるのはそういった特許で、サインだけして実は中身はよく知りません。昔の出願を見ていると、記憶の片隅にあった同僚の名前が懐かしく想いださたりします。あのとき、こういう仕事をしていたんだな、という感慨が沸いてくるのです。

で、その特許出願がどうなったかといういうと、権利化されたのは、そのうちのごく少数で、かつ現在でも有効なものはひとつもありません。技術というのは日進月歩で、新しい技術に駆逐される運命にあります。儚いものにも思えますが、それでも、間違いなく自分が携わった仕事の証であります。 

2018年4月2日月曜日

特許登録・年金の支払い

出願ソフトの補助タブで、納付番号を取得します。
その際、金額を計算しないといけないのですが、以下のサイトで計算します。
https://www.jpo.go.jp/tetuzuki/ryoukin/shutugan.htm

パラメータは、何年度分の特許料を納めるかと、請求項の数です。今回の場合、請求項が9項、
10年分の特許料を納めるので、入力すると、236900円となります。 

小規模業者の減免は、自分で計算し10円未満は切り捨てします。
これを入力すると、納付番号が取得できます。そのままオンラインで収めることも可能です。

減免申請は同時とされていますが、オンラインではなく、申請書類は、郵送で送ります。

これで全ての処理は、おしまいです。後は、特許登録通知を待ちます。