2018年10月31日水曜日

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

 
行3の重みを100、行2の重みを10としてトライしてみたところ、10分ほどで最適解0を得ました。
 
こんな感じで、今までかなり時間をかけても最適解(OR用語でいうところの目的関数値が最小)を得ることが難しかったインスタンスについては、威力を発揮する場面があるでしょう。
 
 
 

2018年10月30日火曜日

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

数理計画上(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出来る方がおられましたら素晴らしいです。)

2018年10月19日金曜日

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

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