ORのレクチャー

目的関数値とか、スケジュールナースのマニュアルには、時々OR用語が出てきますが、
良い、解説がありました。

http://www.robot.t.u-tokyo.ac.jp/dcm/lec_opt/lec01.pdf

http://www.robot.t.u-tokyo.ac.jp/dcm/lec_opt/lec02.pdf

http://www.dais.is.tohoku.ac.jp/~shioura/teaching/mp11/mp11-06.pdf




見て分かるように、ナップザック問題や最短経路問題は、ナーススケジューリングにおいても重要な部分問題であり、この性能の良し悪しが全体のボトルネックになります。数理最適化において最も重要な解法は、分岐限定法です。分岐限定法は、ポイントが二つあり、ノードの選択とと切除平面です。前者については、Reserchgateの回答がエッセンスです。
https://www.researchgate.net/post/Branch_and_Bound_Algorithm_How_to_choose_variables_in_case_of_more_than_one_fractional_values

切除平面については、色々な方法がありますが、最も基本的なものは、小数カットと呼ばれる方法です。

http://www.orsj.or.jp/~archive/pdf/bul/Vol.48_12_936.pdf
http://infoshako.sk.tsukuba.ac.jp/~maiko/mathpro/n_note2-2.pdf
http://dopal.cs.uec.ac.jp/okamotoy/lect/2013/opt/handout06.pdf
http://www.msi.co.jp/nuopt/glossary/term_167e2968d79e57b147ffb376f70159d277feacb7.html