相補性

ORの教科書では、DUALの値ｘスラック変数＝０　という説明がされています。

スケジュールナース実装では、列制約(Cover Constraints)にUnder/Over用と二つのスラックを用いています。これは、SchedulingBenchmarksでは、Underの重みが100、Overの重みが1という異なる重みになっているからです。(GUIでもそのオプションがあることが分かると思います。) つまり、一つの制約で、二つの方向をコントロールしている訳です。このようにしている理由は少しでもLpSolverの負担を減らす目的です。

で、教科書にはない、1制約について二つのスラックがあるとき、理論的にどういう挙動になるのかを解析してみます。

相補性定理により、最適解においては、RowPrice化、スラック変数のどちらかが0になるのはわかるのですが、スラック変数が二つあり、Under重み100、Overが重み1で入っていた場合はどうなりますか？数式で説明して。

問題の定式化

例えば「目標値 $b$ からのずれ」を Under/Over で表す典型的な形を

$$a^{\mathrm{\top }}x+u-o=b,u\ge 0,o\ge 0$$

とします。 目的関数側で

$$\min 100u+1o+\text{(他の項)}$$

という「Underに重み100、Overに重み1」を入れているとします。

これを標準形 LP

$$\min c^{\mathrm{\top }}z\text{s.t. }Az=b,z\ge 0$$

とみなすと、変数ベクトル $z$ の中に $u,o$ が含まれ、 その係数は

$$c_u=100,c_o=1$$

です。また制約行列 $A$ において、この行（対象の1本の制約）に対する列は

• $u$ の列：その行で係数 $+1$

• $o$ の列：その行で係数 $-1$

となります。

双対問題と RowPrice（双対変数）

この制約に対応する双対変数を $\pi$（RowPrice）とします。 標準形 $\min$ の双対は

$$\max b^{\mathrm{\top }}\pi \text{s.t. }{A}^{\mathrm{\top }}\pi \le c$$

なので、列ごとに

• $u$ に対する双対制約：

$$\pi \le 100$$

• $o$ に対する双対制約：

$$-\pi \le 1⟺\pi \ge -1$$

したがって、RowPrice $\pi$ は

$$-1\le \pi \le 100$$

という区間に縛られます。

相補性条件（補完性条件）

相補性定理（補完的スラックネス）は

$$\text{(変数)}\times \text{(対応する双対制約のスラック)}=0$$

という形になります。 ここで双対制約のスラックは

• $u$ に対して：$100-\pi \ge 0$

• $o$ に対して：$1+\pi \ge 0$

なので、相補性条件は

$$u(100-\pi )=0,o(1+\pi )=0.$$

これが「スラック変数と RowPrice のどちらかが 0 になる」という話の、2スラック版の正確な数式です。

どちらのスラックが 0 になるか

上の 2 つの式から、最適解では次のいずれかのパターンになります。

1. 両方ゼロのケース

$$u=0,o=0$$

このときは

$$100-\pi >0,1+\pi >0$$

すなわち

$$-1<\pi <100$$

となります。 → 目標値からのずれがなく、Under/Overとも使われていない状態。

2. Underだけ正のケース

$$u>0\Rightarrow 100-\pi =0\Rightarrow \pi =100,o=0\Rightarrow 1+\pi >0$$

つまり

$$\pi =100,o=0,u\ge 0.$$

→ Under側のスラックだけが正になりうる状況。

3. Overだけ正のケース

$$o>0\Rightarrow 1+\pi =0\Rightarrow \pi =-1,u=0\Rightarrow 100-\pi >0$$

つまり

$$\pi =-1,u=0,o\ge 0.$$

→ Over側のスラックだけが正になりうる状況。

4. 両方正は不可能

$$u>0,o>0$$

だとすると

$$100-\pi =0,1+\pi =0\Rightarrow \pi =100,\pi =-1$$

となり矛盾。 → 相補性により「UnderとOverが同時に正」にはなりえない。

まとめ（直感）

• 双対変数（RowPrice）$\pi$ は $-1\le \pi \le 100$ の範囲にあり、

• 相補性条件

$$u(100-\pi )=0,o(1+\pi )=0$$

により、

• $-1<\pi <100$ なら $u=o=0$

• $\pi =100$ なら $u\ge 0,o=0$

• $\pi =-1$ なら $u=0,o\ge 0$

• したがって、最適解では Under と Over のどちらか一方だけが正になるか、両方ゼロであり、両方同時に正にはならない。

重み 100 と 1 の非対称性は、「RowPrice がどちら側の端点（100 か -1）に張り付くか」を通じて、「どちらのスラックが正になりうるか」を決めている、と見るとスッキリします。

Instance13での解析

下記は、instance13でのLB=1348時の様子です。rowpriceが0でない制約のみ列挙しています。上で予測されている通り、

■rowpriceがfractionalなら、minスラック(under)、maxスラック(over)ともに、0

■rowpriceが、-1ならば、overslack>=0

■rowpriceが、100ならば、underslack>=0

ここで、注意するのは、row_priceが0でないのは、全体の2割程度(119 out of 504)ということです。つまり、残り8割の制約については、row_priceが0なので、「効いていない」という特殊状況にあることが分かります。

        　　row[14]=-0.863305 day = 0 min val=2.55555e-12 max val=5.68424e-10 row[29]=-0.586112 day = 1 min val=2.71906e-12 max val=8.88973e-11 row[41]=-0.524564 day = 2 min val=2.85273e-12 max val=8.00538e-11 row[51]=-1 day = 2 min val=2.75741e-12 max val=0.0418587 row[59]=-1 day = 3 min val=2.76917e-12 max val=0.567414 row[65]=-1 day = 3 min val=2.76857e-12 max val=0.00902082 row[68]=-0.611479 day = 3 min val=2.70788e-12 max val=1.21897e-10 row[83]=-1 day = 4 min val=2.71771e-12 max val=0.00914605 row[86]=-0.816363 day = 4 min val=2.78994e-12 max val=3.59446e-10 row[90]=52.8873 day = 5 min val=4.51134e-12 max val=2.43741e-12 row[91]=52.8873 day = 5 min val=4.4417e-12 max val=2.53334e-12 row[92]=52.8873 day = 5 min val=4.50119e-12 max val=2.43681e-12 row[93]=52.8873 day = 5 min val=4.58953e-12 max val=2.38614e-12 row[94]=100 day = 5 min val=0.0826304 max val=1.60878e-12 row[95]=52.8873 day = 5 min val=4.45319e-12 max val=2.49542e-12 row[96]=52.8873 day = 5 min val=4.54492e-12 max val=2.36447e-12 row[97]=52.8873 day = 5 min val=4.60479e-12 max val=2.29994e-12 row[98]=52.8873 day = 5 min val=4.46162e-12 max val=2.50844e-12 row[99]=100 day = 5 min val=0.0244645 max val=1.68974e-12 row[100]=100 day = 5 min val=0.0276946 max val=1.48983e-12 row[101]=100 day = 5 min val=0.0197265 max val=1.63945e-12 row[102]=100 day = 5 min val=0.0241363 max val=1.60311e-12 row[103]=100 day = 5 min val=0.0352569 max val=1.68851e-12 row[104]=100 day = 5 min val=0.0548525 max val=1.65172e-12 row[105]=100 day = 5 min val=0.02621 max val=1.5467e-12 row[106]=100 day = 5 min val=0.385148 max val=1.29568e-12 row[107]=100 day = 5 min val=0.741131 max val=1.0914e-12 row[108]=47.1127 day = 6 min val=4.3592e-12 max val=2.38182e-12 row[109]=47.1127 day = 6 min val=4.18156e-12 max val=2.64174e-12 row[110]=47.1127 day = 6 min val=4.21321e-12 max val=2.59127e-12 row[111]=47.1127 day = 6 min val=4.22595e-12 max val=2.64134e-12 row[112]=47.1127 day = 6 min val=4.18462e-12 max val=2.74338e-12 row[113]=47.1127 day = 6 min val=4.2615e-12 max val=2.52519e-12 row[114]=47.1127 day = 6 min val=4.22859e-12 max val=2.59199e-12 row[115]=47.1127 day = 6 min val=4.18693e-12 max val=2.64157e-12 row[116]=46.2326 day = 6 min val=4.03356e-12 max val=2.87082e-12 row[117]=47.1127 day = 6 min val=3.96615e-12 max val=2.96322e-12 row[134]=-0.837218 day = 7 min val=2.58397e-12 max val=2.61113e-10 row[163]=-0.925784 day = 9 min val=2.59777e-12 max val=6.6424e-10 row[180]=-0.602286 day = 10 min val=2.70604e-12 max val=1.09113e-10 row[181]=-0.625962 day = 10 min val=2.91071e-12 max val=1.10779e-10 row[210]=-0.768445 day = 11 min val=2.79359e-12 max val=1.71992e-10 row[220]=100 day = 12 min val=0.025898 max val=1.74228e-12 row[225]=100 day = 12 min val=0.0205166 max val=1.80212e-12 row[226]=100 day = 12 min val=0.0184117 max val=1.74637e-12 row[227]=100 day = 12 min val=0.0179949 max val=1.70341e-12 row[228]=98.4456 day = 12 min val=6.02561e-11 max val=1.62807e-12 row[229]=100 day = 12 min val=0.0176241 max val=1.73514e-12 row[230]=100 day = 12 min val=0.0322697 max val=1.73808e-12 row[231]=100 day = 12 min val=0.0373443 max val=1.50067e-12 row[232]=100 day = 12 min val=1.18009 max val=1.41862e-12 row[233]=100 day = 12 min val=0.0403635 max val=1.57967e-12 row[234]=100 day = 13 min val=0.222295 max val=1.49075e-12 row[235]=100 day = 13 min val=0.124916 max val=1.45064e-12 row[236]=100 day = 13 min val=0.0436695 max val=1.47376e-12 row[237]=100 day = 13 min val=0.387442 max val=1.45202e-12 row[238]=100 day = 13 min val=0.152822 max val=1.66829e-12 row[239]=100 day = 13 min val=0.032794 max val=1.53126e-12 row[240]=100 day = 13 min val=0.0482729 max val=1.56177e-12 row[241]=100 day = 13 min val=0.0203498 max val=1.61615e-12 row[242]=100 day = 13 min val=0.0594985 max val=1.66069e-12 row[243]=100 day = 13 min val=0.914335 max val=1.24705e-12 row[260]=-0.685022 day = 14 min val=2.63634e-12 max val=1.35774e-10 row[265]=-1 day = 14 min val=2.60472e-12 max val=1.01838 row[283]=-1 day = 15 min val=2.87888e-12 max val=0.0561331 row[291]=-0.669252 day = 16 min val=2.72094e-12 max val=1.43556e-10 row[301]=-1 day = 16 min val=2.86499e-12 max val=0.0183823 row[309]=-0.70548 day = 17 min val=2.6219e-12 max val=1.69257e-10 row[313]=-0.883984 day = 17 min val=2.68177e-12 max val=4.08302e-10 row[319]=-1 day = 17 min val=2.5107e-12 max val=1 row[346]=98 day = 19 min val=4.59079e-11 max val=1.62041e-12 row[351]=100 day = 19 min val=0.646963 max val=1.37153e-12 row[352]=99.2295 day = 19 min val=1.0678e-10 max val=1.58572e-12 row[353]=100 day = 19 min val=0.0163243 max val=1.5739e-12 row[354]=100 day = 19 min val=0.0378528 max val=1.65346e-12 row[355]=100 day = 19 min val=0.10811 max val=1.51971e-12 row[356]=99.5536 day = 19 min val=2.40253e-10 max val=1.50882e-12 row[357]=100 day = 19 min val=0.0521357 max val=1.39095e-12 row[358]=100 day = 19 min val=0.651391 max val=1.25515e-12 row[359]=100 day = 19 min val=2.99785 max val=7.42342e-13 row[360]=100 day = 20 min val=0.025462 max val=1.56327e-12 row[361]=100 day = 20 min val=0.0124321 max val=1.75039e-12 row[362]=100 day = 20 min val=0.0323657 max val=1.63865e-12 row[363]=100 day = 20 min val=0.0133692 max val=1.73585e-12 row[364]=100 day = 20 min val=0.0191744 max val=1.79394e-12 row[365]=100 day = 20 min val=0.0307338 max val=1.73287e-12 row[366]=100 day = 20 min val=0.0295816 max val=1.66538e-12 row[367]=100 day = 20 min val=0.0157267 max val=1.74435e-12 row[368]=100 day = 20 min val=0.0348275 max val=1.64747e-12 row[369]=98.4726 day = 20 min val=5.25977e-11 max val=1.88827e-12 row[370]=-1 day = 20 min val=2.64508e-12 max val=0.145464 row[386]=-0.609231 day = 21 min val=2.73781e-12 max val=1.14469e-10 row[410]=-0.840048 day = 22 min val=2.74723e-12 max val=2.14573e-10 row[422]=-1 day = 23 min val=2.5522e-12 max val=0.314833 row[428]=-0.726678 day = 23 min val=2.35833e-12 max val=1.73831e-10 row[440]=-0.38895 day = 24 min val=2.83071e-12 max val=6.68554e-11 row[446]=-0.424308 day = 24 min val=2.38349e-12 max val=9.0038e-11 row[449]=-0.325618 day = 24 min val=2.88308e-12 max val=7.77122e-11 row[472]=100 day = 26 min val=0.0537183 max val=1.77114e-12 row[477]=100 day = 26 min val=0.0582241 max val=1.79152e-12 row[478]=100 day = 26 min val=0.0325335 max val=1.77199e-12 row[479]=100 day = 26 min val=0.0997524 max val=1.70957e-12 row[480]=100 day = 26 min val=0.0212184 max val=1.75241e-12 row[481]=100 day = 26 min val=0.0546691 max val=1.87567e-12 row[482]=100 day = 26 min val=0.0866728 max val=1.86261e-12 row[483]=100 day = 26 min val=0.0348345 max val=1.65861e-12 row[484]=100 day = 26 min val=0.0719359 max val=1.51472e-12 row[485]=100 day = 26 min val=0.323769 max val=1.52836e-12 row[486]=100 day = 27 min val=0.122186 max val=1.63422e-12 row[487]=100 day = 27 min val=0.0589922 max val=1.4626e-12 row[488]=100 day = 27 min val=0.0313694 max val=1.7076e-12 row[489]=100 day = 27 min val=0.0413175 max val=1.74454e-12 row[490]=100 day = 27 min val=0.0632407 max val=1.79693e-12 row[491]=100 day = 27 min val=0.0315268 max val=1.72677e-12 row[492]=100 day = 27 min val=0.0477631 max val=1.69113e-12 row[493]=100 day = 27 min val=0.0162712 max val=1.76216e-12 row[494]=100 day = 27 min val=0.0320612 max val=1.68608e-12 row[495]=100 day = 27 min val=0.175491 max val=1.60306e-12 row[496]=-0.883723 day = 27 min val=2.75924e-12 max val=5.71277e-10 effective rows=119 out of 504

Branchを繰り返した結果、UB=1348の整数解時では、全RowPriceが整数となりました。

　　　　row[450]=100 day = 25 min val=0 max val=0 row[451]=100 day = 25 min val=0 max val=0 row[452]=-1 day = 25 min val=0 max val=0 row[453]=100 day = 25 min val=0 max val=0 row[454]=100 day = 25 min val=0 max val=0 row[455]=100 day = 25 min val=0 max val=0 row[456]=100 day = 25 min val=0 max val=0 row[457]=100 day = 25 min val=0 max val=0 row[458]=100 day = 25 min val=0 max val=0 row[459]=-1 day = 25 min val=0 max val=0 row[460]=100 day = 25 min val=0 max val=0 row[461]=100 day = 25 min val=0 max val=0 row[462]=100 day = 25 min val=0 max val=0 row[463]=100 day = 25 min val=4.44089e-16 max val=0 row[464]=-1 day = 25 min val=0 max val=0 row[465]=100 day = 25 min val=0 max val=0 row[466]=100 day = 25 min val=0 max val=0 row[467]=100 day = 25 min val=0 max val=0 row[468]=100 day = 26 min val=0 max val=0 row[469]=-1 day = 26 min val=0 max val=0 row[470]=-1 day = 26 min val=0 max val=0 row[471]=100 day = 26 min val=-4.44089e-16 max val=0 row[472]=-1 day = 26 min val=0 max val=0 row[473]=-1 day = 26 min val=0 max val=0 row[474]=100 day = 26 min val=0 max val=0 row[475]=-1 day = 26 min val=0 max val=0 row[476]=100 day = 26 min val=0 max val=0 row[477]=100 day = 26 min val=0 max val=0 row[478]=100 day = 26 min val=0 max val=0 row[479]=100 day = 26 min val=-4.44089e-16 max val=0 row[480]=-1 day = 26 min val=0 max val=0 row[481]=-1 day = 26 min val=0 max val=0 row[482]=-1 day = 26 min val=0 max val=0 row[483]=100 day = 26 min val=1 max val=0 row[484]=-1 day = 26 min val=0 max val=0 row[485]=100 day = 26 min val=0 max val=0 row[486]=100 day = 27 min val=0 max val=0 row[487]=-1 day = 27 min val=0 max val=0 row[488]=-1 day = 27 min val=0 max val=0 row[489]=-1 day = 27 min val=0 max val=0 row[490]=-1 day = 27 min val=0 max val=0 row[491]=-1 day = 27 min val=0 max val=0 row[492]=-1 day = 27 min val=0 max val=0 row[493]=-1 day = 27 min val=0 max val=0 row[494]=100 day = 27 min val=1 max val=0 row[495]=100 day = 27 min val=2 max val=0 row[496]=-1 day = 27 min val=0 max val=0 row[497]=100 day = 27 min val=0 max val=0 row[498]=-1 day = 27 min val=0 max val=0 row[499]=100 day = 27 min val=-8.88178e-16 max val=0 row[500]=-1 day = 27 min val=0 max val=0 row[501]=-1 day = 27 min val=0 max val=0 row[502]=-1 day = 27 min val=0 max val=0 row[503]=100 day = 27 min val=0 max val=0 effective rows=504 out of 504

一瞬、「こんなに効いていないのが支配的であるのなら、とりあえず制約を外して..」という高速化を思いついたのですが、むしろ上のような状況の方が特殊であることが分かりました。instance13の方が特殊、ということです。残念。

ちなみに、整数解時、row[494][495]のスラックが整数になっています。これは、LB時にもその萌芽が見られます。Lpsolverは、ベクトル的に最適解に近い解を出力する、ということを基にして（前提にして）解くのがMIPSolve的な解法となります。