チュートリアル ペア設定の最適解は、0であることが判明

 

行3の重みを100、行2の重みを10としてトライしてみたところ、10分ほどで最適解0を得ました。

 

こんな感じで、今までかなり時間をかけても最適解（OR用語でいうところの目的関数値が最小）を得ることが難しかったインスタンスについては、威力を発揮する場面があるでしょう。

 

 

 

ペア設定が数理計画では難しい

数理計画上(Integer Programming)で、ペア設定を記述しようとしているのですが、どうにも上手くいきません。これは、難しいです。学会でのベンチマーク問題には、出てきませんが、実使用上は、よく出てきる記述です。「新人が何人日勤だったら、ベテランは何人日勤」　みたいな、Implication＋Slack変数が絡む場合です。SAT上では、難なく書けますが..


参考にした記述を記します。

整数計画法による定式化入門
http://web.tuat.ac.jp/~miya/fujie_ORSJ.pdf

整数計画定式化MIT
 http://web.mit.edu/15.053/www/AMP-Chapter-09.pdf

piecewise linear modeling
https://www.math.cuhk.edu.hk/course_builder/1415/math3220/L2%20(without%20solution).pdf

cast to boolean
https://cs.stackexchange.com/questions/12102/express-boolean-logic-operations-in-zero-one-integer-linear-programming-ilp/12118

https://cs.stackexchange.com/questions/69531/greater-than-condition-in-integer-linear-program-with-a-binary-variable?noredirect=1&lq=1

http://yetanothermathprogrammingconsultant.blogspot.com/2016/10/mip-modeling-if-constraint.html

stack exchangeは、その道の専門家の回答が多く、困ったときは助けになる確率が高いです。

しかしながら、上記、BIG-Mによるテクニック等、SAT以上にKnowHow的な部分があるのですが、それらを駆使しても正確には記述できませんでした。（ScNurseのTutorialペア設定をIntegerProgramming出来る方がおられましたら素晴らしいです。）

一般ベンチでは思わしくない結果に

手持ちのテストプロジェクトがかろうじて動くようになり、やってみると惨憺たる結果となりました。
これらは、リアルベンチ（実使用のプロジェクト）ではあり、現在のScNurseの優秀さを改めて実感するという結果になりつつあります。ここまで、結果が分かれるとは、正直予想していませんでした。
　また、実問題で走らせてみると新たに別な問題も発生して、この対応にまた時間がかかりそうです。
　
　

要素技術開発がほぼ終了

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

１）手持ちベンチマークで検証　 10月
２）NS2ベンチマークで検証　　　11月
３）NS1ベンチマークで検証       
４）まとめ　　　　　　　　　　　　　　 12月
５）実装ベータ版公開　　　　　　　　1月
６）英語サイト公開　　　　　　　　　　2月
７）DSL作成～　　　　　　　　　　　　3月

特殊形では、ほぼWorlｄWideでトップ性能であることは、確認できたのですが、一般系でどのような性能になるのかが、未だ見えません。　こちらについては、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です。

数理計画テキスト

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

１）手持ちベンチマークで検証　 10月
２）NS2ベンチマークで検証　　　11月
３）NS1ベンチマークで検証       
４）まとめ　　　　　　　　　　　　　　 12月
５）実装ベータ版公開　　　　　　　　1月
６）英語サイト公開　　　　　　　　　　2月
７）DSL作成～　　　　　　　　　　　　3月

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

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

CALL for papers

Dear solver and benchmarks submitters to the MaxSAT Evaluation 2018,
The JSAT journal is being reactivated and has several renewals like a new
webpage (see http://jsatjournal.org/) and the submission management via
Easychair.
We are attaching a call for papers for a special issue on SAT-related
competitions. This special issue aims to cover all aspects related to
competitions (e.g., solving approaches, tools, benchmarks, result
interpretations, etc.) To make this special issue a success, we encourage
the MaxSAT submitters to contribute to the special issue.

シリアライゼーションライブラリ cereal

アルゴリズムの改善を行うのに、コンパイル→探索の　サイクルを出来るだけ早く回したいというのが背景です。大規模になると、コンパイルするだけで時間がかかってしまいます。そこで、コンパイル後の状態を保存・解凍できるようにすると、(一回コンパイルすれば）コンパイルの時間が省けます。この機能は、Save/Restoreという風に呼ばれていると思いますが、いわゆる「シリアル化」です。C++のクラスやvectorなどのテンプレートを、簡単にシリアル化するのに、cerealを今回、使ってみました。cerealは、serialと発音的にどうなんでしょうか？　ともあれ、とても簡単にシリアル化できました。BinaryやJson思いのままに可能です。日本語記事は、こちらか、こちらが詳しいです。