Day毎の累積最小・最大の計算法

 SATソルバが鍵となります。

長大のインスタンスにおいて、いきなり年間[1840,1872]時間では、探索範囲が膨大過ぎます。探索範囲をなるべく限定することを考えます。

Power On時、Target Rangeに至る経路は膨大です。そのままでSAT SOLVEすると爆発して求めることができません。

そこで、まずは、LpSolverで、システム全体のLowerBoundまで求めます。LB≒UBの性質を利用してグラフをReductionします。Reductionしたグラフ上で、Day毎に[最小：最大]を算出して、上図のように探索範囲を限定してやろう、という算段です。最適化という作業は、選択と評価探索の言い換えです。OR世界では、Branch＆Boundという最強の手法が存在しますが、残念ながら、今回の規模は大きすぎてそれでも時間がかかりすぎるために、この手法に至っています。

具体的には、次のアルゴリズムで、Day毎の[最小：最大]を確定させます。

グラフ上では、レベルと呼ばれる変数があります。大まかにいえば、各レベルは各シフトに対応します。各シフトは、同一Dayでは連続します。各レベルでの最小、最大を求めてやれば、各Dayでの最小・最大に換算することは出来ます。なので、まずは、各レベルでの最小と最大を求めてやることが必要となります。それには、各レベル上の各ノードで、最小と最大値を得ることになります。それを各レベルにまとめ、さらに各Dayにまとめる、という作業になります。

動的計画法を単に用いただけでは、終端での最小・最大値しか担保されません。全ての中間ノードをScanすることで、はじめて厳密なDay毎の累計最小・最大状態を得ることが出来ます。

このように、ORにおける最適化とは、ほとんど枝刈りのための前処理と枝刈りそのものです。