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

0 件のコメント:

コメントを投稿

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