MDD TREEの枝刈り

Scheduling Benchmarksでは、すべて、

RMPの重みは、Understaffing=100、Overstaffing＝１

スタッフ側(Pricer)は、希望休み・シフトに対する違反重み種類が3種類(1,2,3)

と非常にシンプルです。

前提の整理

• 最小化問題とします。

• 目的関数は、重み付き個数の和：

$$z=100x_{100}+1x_1+1y_1+2y_2+3y_3$$

のような形（RMP に 100,1、Pricer に 1,2,3 の重み）。

• 線形緩和の最適値を $LB$、現在の整数実行可能解の値を $UB$ とし、

$$GAP=UB-LB$$

とする。

基本アイデア

ある重み $w$ を持つ変数（列）を、LP 解から整数解に向かうときに「どれだけ増やせるか」は、

$$w\cdot \mathrm{\Delta }{n}_w\le GAP$$

を満たさないと $UB$ を超えてしまう、という制約から来ます。 したがって、

$$\mathrm{\Delta }{n}_w\le \lfloor \frac{GAP}{w}\rfloor$$

が、その重みクラスについて許される“増分の最大数”になります。

各重みごとの限定

• 重み 100 の列:

$$\mathrm{\Delta }{n}_{100}\le \lfloor \frac{GAP}{100}\rfloor$$

• 重み 3 の列:

$$\mathrm{\Delta }{n}_3\le \lfloor \frac{GAP}{3}\rfloor$$

• 重み 2 の列:

$$\mathrm{\Delta }{n}_2\le \lfloor \frac{GAP}{2}\rfloor$$

• 重み 1 の列（RMP, Pricer 両方含めて）:

$$\mathrm{\Delta }{n}_1\le GAP$$

ここでの $\mathrm{\Delta }{n}_w$ は「LP 解から整数化の過程で、その重みクラスについて増やせる“余分な個数”」という意味です。 他の重みクラスの変数をすでにある程度固定しているなら、その分のコストを差し引いた残りの余裕に対して同じ式を適用できます。

直感的なまとめ

• GAP が小さいほど、重い列（重み 100 や 3）の「取りすぎ」はすぐに UB を超えるので、 それぞれ $\lfloor GAP\mathrm{/}w\rfloor$ 個までしか“余分には”許されない。

• これを使うと、整数化フェーズで「重み 100 の列は LP 解から多くても $\lfloor GAP\mathrm{/}100\rfloor$ 本まで」「重み 3 は $\lfloor GAP\mathrm{/}3\rfloor$ 本まで」などと、探索空間をかなり素直にカットできます。

もし「RMP 側の 100 と 1」「Pricer 側の 1,2,3」を別々に扱いたい（例えば RMP の 1 と Pricer の 1 を区別したい）なら、そのクラスごとに同じ形で上限を入れていく形になります。

この方向性で、実際に使っている目的関数の形（係数と変数の対応）をもう少し具体的に書いてくれたら、 「絶対個数の上限」まで踏み込んだ式に落とし込むこともできますが、まずはこの $\lfloor GAP\mathrm{/}w\rfloor$ ルールがコアになります。

Q.GAPが1.5のときどうなりますか？

結論だけ先に言うと、GAP = 1.5 のとき、重み 2・3・100 の列は “追加ゼロ” しか許されません。 追加できるのは重み 1 の列だけで、最大 1 本まで です。

◆ なぜそうなるか（核心）

整数化で LP 解から増やせる本数 Δn は

$$w\cdot \mathrm{\Delta }n\le GAP$$

なので

$$\mathrm{\Delta }n\le \lfloor \frac{GAP}{w}\rfloor$$

を満たす必要があります。

GAP = 1.5 を代入すると：

◆ 重みごとの上限（GAP = 1.5）

• 重み 100

$$\mathrm{\Delta }{n}_{100}\le \lfloor \frac{\mathrm{1.5/}}{100}\rfloor =0$$

• 重み 3

$$\mathrm{\Delta }{n}_3\le \lfloor \frac{\mathrm{1.5/}}{3}\rfloor =0$$

• 重み 2

$$\mathrm{\Delta }{n}_2\le \lfloor \frac{\mathrm{1.5/}}{2}\rfloor =0$$

• 重み 1（RMP・Pricer 共通）

$$\mathrm{\Delta }{n}_1\le \lfloor 1.5\rfloor =1$$

◆ つまりどうなるか

• 重い列（100, 3, 2）は一切増やせない → 追加した瞬間に UB を超えるため。

• 重み 1 の列だけが最大 1 本まで許される → GAP 1.5 の範囲で収まる唯一のクラス。