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 の範囲で収まる唯一のクラス。

Q.重み個数n(デルタではなく）の限定式を重みWとGAPからまとめてください。

結論から先にまとめると：

重み $W$ を持つ変数の「整数解で許される最大個数 $n_w$」は、 LP 解の値 $x_w^{LP}$ と GAP を使って

$$>n_w\le \lfloor x_w^{LP}+\frac{\mathrm{G}\mathrm{A}\mathrm{P/}}{W}\rfloor >$$

で与えられる。

これが “重み W と GAP から導く、絶対個数の上限式” の完成形です。

🎯 1. なぜこの式になるのか（最重要）

整数化で変数 $x_w$ を LP 値から整数値へ動かすとき、 目的値の悪化は最低でも

$$W\cdot (n_w-x_w^{LP})$$

です。

整数解が TargetUB を超えないためには：

$$W\cdot (n_w-x_w^{LP})\le \mathrm{G}\mathrm{A}\mathrm{P}$$

これを $n_w$ について解くと：

$$n_w\le x_w^{LP}+\frac{\mathrm{G}\mathrm{A}\mathrm{P/}}{W}$$

整数変数なので：

$$\boxed{{\displaystyle n_w\le \lfloor x_w^{LP}+\frac{\mathrm{G}\mathrm{A}\mathrm{P/}}{W}\rfloor }}$$

これが 重み W の変数の絶対個数上限。

🎯 2. Δではなく「絶対個数 n_w」で書く理由

あなたが求めているのは：

• Δ（増分）ではなく

• 整数解でその変数を最大いくつまで許せるか（絶対個数）

なので、LP 値 $x_w^{LP}$ を含めた式が必要になる。

🎯 3. 例：重み 100、LP 値 0.3、GAP=1.5

$$n_{100}\le \lfloor 0.3+\frac{\mathrm{1.5/}}{100}\rfloor =\lfloor 0.315\rfloor =0$$

→ 整数解では 0 に固定（増やせない）

🎯 4. 例：重み 1、LP 値 2.4、GAP=1.5

$$n_1\le \lfloor 2.4+\frac{\mathrm{1.5/}}{1}\rfloor =\lfloor 3.9\rfloor =3$$

→ 整数解では最大 3 本まで許される

🎯 5. まとめ（あなたが欲しかった式）

重み $W$ の変数の整数解での最大個数は：

$$\boxed{{\displaystyle n_w^{\max }=\lfloor x_w^{LP}+\frac{\mathrm{G}\mathrm{A}\mathrm{P/}}{W}\rfloor }}$$

• $x_w^{LP}$：RMP の LP 解の値

• $W$：その変数の重み

• $\mathrm{G}\mathrm{A}\mathrm{P}=\mathrm{T}\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{e}\mathrm{t}\mathrm{U}\mathrm{B}-LB$