連続変数によるLPを解いた解は、連続変数解であって整数ではありません。LPを解くと、3.1人とか、4.6人とか、連続変数解が出てきます。人をぶった切る訳にも行かないので、整数化を行うことが必須になります。
LPは、下界を見積もるには重宝します。離散解は、連続変数解より良くなる筈がない、という原理に基づいて、離散解を得る前に、目的関数値の下界を得ることができます。「これ以上良くなることはありません」という値を知って、それなら、離散解を求めることなく制約に変更をかける、といったことも可能になります。
最も困難なのは、整数化です。MIPソルバでは、平面削除(CuttingPlane)、ヒューリスティクスによるReducedCostFixing、そして最後に分岐限定操作により整数化を行っています。CuttingPlaneだけで、整数化が完了するのは、小さいインスタンスのみで、大抵は、分岐限定で問題を分割して整数化を行うことになります。
NSPの分岐限定法は、まさに看護師長さんが、勤務表を作る様子そのものです。分岐限定は、Tree構造になりますが、どのRoster、Day、Shiftから始めればよいか？は、Tree構造の大きさに関係して求解速度に直結しています。
キーとなる重要なノードから選択して分岐限定を始めることがTreeSizeを小さくする上で鍵となります。LPで、Fractionalな数値ちょうど0.5あたりを選べば直感的には、良いようですが、Randomに選んだものと大差ないという結論のようです。ノード選択には、strong branching,pseude-cost 等の方法が知られています。
参考：
0 件のコメント:
コメントを投稿