数値実験の結果

以上に述べた提案解法をC言語により実装し、ランダムに発生させた大規模問題例を用い て数値実験を行った。数値実験では、グループ数と各グループの構成項目数に応じた下記 ３クラスの入力データを用いた。

(クラスS) グループ数小－構成項目数大：グループ数10~90,構成項目数500~700

(クラスM) グループ数中－構成項目数中：グループ数100~500,構成項目数150~250

(クラスL) グループ数大－構成項目数小：グループ数1000~10000,構成項目数50~100,90~120

このクラス分類に基づいて、指定したグループ数

m

と指定範囲のグループ構成項目数

n

k

(k^∈K)から構成される問題例をランダムに発生させ、他の属性については下記のように指定 範囲[a、b^]の一様分布U^[a、b^]による擬似乱数値を使用した。

c

k ∈ U^[500,2000] ： グループkの段取り費用

s

k ∈ U^[100,500^] ： グループkの段取り時間

p

kj ∈ U^[1000,2000^]： グループk,項目jの純利益

t

kj ∈ U^[300,600^] ： グループk,項目jの作業時間

但し

p

kjと

t

kjについては、現実的な状況下で顕在化するであろうと考えられる弱相関性を 考慮するため、項目の効率性(

p

kj

/ t

^{kj)にも一様分布U[2.0、4.0]}による制限を加えた。

また、計画期間については、グループごとの作業時間和と段取り時間により、下記のよう に決定した。

T =

Σ

k∈KU^k

Σ

j∈Nk

t

kj +

Σ

k∈KU^k

s

k

ここで、Ukはグループkのランダムな重みであり、一様分布による擬似乱数値で与える。

この一様分布の区間については、ナップサック容量の程度が計算困難度に与える影響を調 べるため、[0.15,0.20]と[0.05,0.10]の２区間のケースを考慮する。この区間は、設備更新計 画は一回のみではなく繰り返し定期的に策定されることを前提におき、大半の項目が選定 されないよう1.0より十分小さな範囲として設定されている。

以上の方針により作成された問題例を分類し、ナップサック容量比の区間[0.15,0.20]を用 いた問題例群１と区間[0.05,0.10]を用いた問題例群２を、それぞれ表 4-3、表 4-4 に示す。

各問題例群には、同一グループ数で構成される、クラス S、M、Lに属する 23 の問題例が含 まれている。

クラス 問題名 #group m s

#items

ns #ave.

ns/ m capacity T

S

S10 10 5852 585.2 490751

S30 30 17939 598.0 1493708 S50 50 30431 608.6 2592609 S70 70 42320 604.6 3552087 S90 90 53528 594.8 4569456

M

M100 100 15258 152.6 1307298

M120 120 20541 171.2 1754970

M150 150 30265 201.8 2586041

M180 180 36966 205.4 3108019

M200 200 39890 199.5 3366709

M300 300 59767 199.2 5117792

M400 400 79146 197.9 6760330

M500 500 100451 200.9 8540762

L

L1000 1000 74733 74.7 6413848

L2000 2000 150329 75.2 12876548

L3000 3000 226630 75.5 19370222

L4000 4000 299407 74.9 25619949

L5000 5000 375982 75.2 32261311

L6000 6000 629275 104.9 53846115 L7000 7000 734329 104.9 62654813 L8000 8000 839272 104.9 71639611 L9000 9000 944357 104.9 80637817 L10000 10000 1049092 104.9 89656308 表 4-3 数値実験用の問題例群１（U^k∈[0.15、0.20]）

クラス 問題名 #group

m s

#items

n^{s #}ave.

n^s/ m capacity T S

S10 10 6046 604.6 236334

S30 30 17818 593.9 632671

S50 50 30134 602.7 1103824

S70 70 42355 605.1 1523089

S90 90 53874 598.6 1961246

M

M100 100 15037 150.4 562339

M120 120 20870 173.9 781033

M150 150 29941 199.6 1099836

M180 180 36038 200.2 1311407

M200 200 41122 205.6 1501642

M300 300 59891 199.6 2196709

M400 400 80707 201.8 2977541

M500 500 100045 200.1 3621612

L

L1000 1000 74761 74.8 2749782

L2000 2000 150070 75.0 5489715

L3000 3000 223513 74.5 8229021

L4000 4000 300284 75.1 10991682

L5000 5000 375452 75.1 13772825

L6000 6000 630748 105.1 23035194 L7000 7000 736234 105.2 26963164 L8000 8000 839902 105.0 30709006 L9000 9000 943212 104.8 34452801 L10000 10000 1051092 105.1 38412615 表 4-4 数値実験用の問題例群２（U^k∈[0.05、0.10]）

次に、問題例群１、２に対する数値実験の実行結果を、それぞれ表 4-5、表 4-6 に示 す。なお数値実験に使用したPCは、Dell Precision T1500(Intel Core i7、 64bit OS、

2.80GHz、物理メモリ16GB)である。表 4-5、表 4-6では、下記の内容について提案解法

による実行結果が示されている。

Prob. ： 問題例の名称

Int.gap(%) ： ルート問題における整数ギャップ ＝100（上界値–下界値）/^下界値

pure items ： 釘付けテストにより固定された純項目数（#peg0:０固定、#peg1:１固定）

virtual items ： 釘付けテストにより固定された仮想項目数（#peg0:０固定、#peg1:１固定）

#groups unfix ： 釘付けテストにより固定されなかったグループ数（B&Bによる列挙対象）

#groups sel. ： 最終的に選定されたグループ数（最適解）

B&B nodes ： 分枝限定法で探索された木ノード数

„*‟は、釘付けテストの前に最適解が得られたことを示す。

„~‟は、釘付けテストにより全グループが固定されたことを示す。

knp sol ： 全グループ固定の0－1ナップサック問題が解かれた回数

Opt.value ： 最適解の値（目的関数値）

cpu(sec) prep ：分枝限定法を除く準備処理の計算時間（秒）（4.3.3.6(１)~(４)、入力時間除く）

cpu(sec) total ： 準備処理と分枝限定法の計算時間（秒）（4.3.3.6(１)~(５)、出力時間除く）

表 4-5、表 4-6に示した計算時間の結果から、数値実験で用いたようなデータ特性を有す る大規模セットアップ付きナップサック問題の殆どは提案解法により高速に解けるものと 判断される。46の問題例のうち38例が1秒未満で解けており、残りは5秒未満が5例、

10秒以上を要したのは3例である。このうち、分枝限定法を実行することなく最適解が得 られたのは、クラスSを中心に46例中12例であった。また、分枝限定法を実行した問題例 からは、様々なサイズの未固定グループ数を取り扱っているので、分枝限定法の全体的性 能を捉えることができる。以上の高性能の理由として、提案解法の高速性は当然のことと して、数値実験で用いた大規模セットアップ付きナップサック問題の整数ギャップが元々 小さいことが主因として挙げられる。

したがって、微尐な整数ギャップを与える上下界値を求める連続緩和法とヒューリスティ ックを採用したことが、分枝限定法の高効率化を引き出したと言える。ちなみに、数値実 験による整数ギャップは、問題例群１で23例中22例が0.05%以下、問題例群２で23例中

16例が0.05%以下、残りの6例が1.0%以下であった。全体的な整数ギャップの出現度合い

から判断すると、「計画期間を大きくすると、解きやすくなる問題例の割合が多くなる傾向 がみられる」という結果が得られている。

しかしながら、数値実験の結果は、大規模セットアップ付きナップサック問題の中には提 案解法により実時間内で解けないものが存在するであろうことも示唆している。例えば、

問題例群１のL6000、L7000では実行時間が 50 秒を超えており、この結果が最悪ケース であるとは判定できないからである。この低速化の原因は、「分枝限定法の過程で生じた数 十万項目の0－1ナップサック問題の求解に多くの計算時間が費やされているためであった」

と判明している。

Prob. Int.gap pure items

pure Virtual items

pure #groups B&B kn

p Opt. cpu(sec)

(%) #peg0 #peg1 #peg0 #peg1 unfix sel. nodes sol value #peg

0 #peg1 S10 0.0086

5 3496 0 0 10 0 10 ~ 1 1838288 0.01

5 0.031 S30 0.0000

7 14514 1575 0 30 0 30 ~ 1 5625983 0.04

7 0.047 S50 0.0000

6 24348 2720 0 50 0 50 ~ 1 9751594 0.01

6 0.031 S70 0.0000

5 33921 3508 0 70 0 70 ~ 1 13368568 0.01

5 0.031

S90 0.0 - - - - - ⁹⁰ * 0 17190233 0.01

5 0.015 M100 0.0001

0 11618 486 23 77 0 77 ~ 1 4769885 0.01

5 0.015

M120 0.0 - - - - - ⁹⁷ * ^{0 6429756 0.01}

6 0.016 M150 0.0035

1 10502 0 8 120 22 130 45 2 9488651 0.01

5 0.109 M180 0.0057

4 3725 0 3 112 65 161 115 1 11444749 0.04

7 0.078 M200 0.0000

3 31291 1605 28 172 0 172 ~ 1 12375483 0.01

6 0.031 M300 0.0121

5 0 0 0 15 285 259 530 1 18800913 0.04

7 0.125 M400 0.0101

5 0 0 0 7 393 349 887 4 24841892 0.06

3 0.640 M500 0.0004

3 60638 0 41 431 28 443 57 2 31376444 0.04

6 0.546 L1000 0.0002

6 45887 246 412 527 61 555 90 1 22710261 0.04

7 0.110 L2000 0.0266

4 0 0 0 0 2000 1116 2233 0 45576257 0.04

7 0.375 L3000 0.0004

7 66482 0 927 1283 790 1675 785 0 68653946 0.14

0 0.328 L4000 0.0003

3 94560 0 1337 1717 946 2213 1443 1 90726882 0.18

8 0.858 L5000 0.0000

0 25640

6 9999 2205 2783 12 2789 19 1 11426363 8

0.21

9 0.250 L6000 0.0007

0 0 0 150 469 5381 4081 8994 1 19316507 8

0.51 5

55.55 L7000 0.3120 2

0 46006

9 284 2002 4514 484 4752 723 1 22478932 6

0.43 7

68.90

L8000 0.0 - - - - - ⁵⁴⁴¹ * 0 25713777 5

0 0.37

5 0.390 L9000 0.0000

4 56079

3 26 2481 5753 766 6146 786 0 28946597 5

0.60

8 2.262 L1000

0

0.0000 3

61594

4 29 2751 6361 888 6836 950 0 32159374 2

0.68

6 3.011

表 4-5 問題例群１の計算結果（U^k∈[0.15、0.20]）

Prob. Int.gap pure items

pure Virtual items

pure #groups B&B kn

p Opt. cpu(sec)

(%) #peg0 #peg1 #peg0 #peg1 unfix sel. nodes sol value #peg

0 #peg1 S10 0.0027

6 5260 0 1 9 0 9 ~ 1 904436 0.01

6 0.016 S30 0.0631

0 0 0 1 1 28 22 50 1 2416744 0.01

5 0.031 S50 1.9197

1 0 0 0 0 50 38 89 1 4210181 0.03

1 0.031 S70 0.0000

2 37685 505 18 52 0 52 ~ 1 5813176 0.01

6 0.016 S90 0.9856

0 0 0 0 0 90 67 134 0 7474433 0.01

6 0.032 M100 0.6783

4 0 0 0 0 100 39 261 3 2074575 0.01

5 0.031 M120 0.8014

3 0 0 0 0 120 52 174 1 2897381 0.03

2 0.047 M150 0.5250

5 0 0 0 0 150 68 219 1 4087088 0.03

2 0.047 M180 0.0167

7 1416 0 39 22 119 80 178 1 4873834 0.01

6 0.032 M200 0.0169

9 156 0 35 15 150 90 377 3 5593837 0.04

7 0.093 M300 0.0718

0 0 0 0 0 300 132 601 2 8167484 0.01

6 0.094 M400 0.0128

0 0 0 30 2 368 181 548 1 11055106 0.06

3 0.125 M500 0.0066

6 1298 0 102 46 352 221 881 3 13480240 0.06

2 0.468 L1000 0.0064

6 6698 0 472 65 463 266 927 2 9873795 0.03

1 0.219 L2000 0.0010

5 69426 0 1307 378 315 532 632 2 19708747 0.07

8 0.188 L3000 0.0009

9 80078 0 1828 487 685 793 2501 5 29516232 0.10

9 1.357 L4000 0.0007

6 10567

1 0 2463 644 893 1063 841 0 39484882 0.15

6 0.328 L5000 0.0001

8 23273

6 2 3513 1155 332 1332 665 2 49429678 0.18

8 2.777 L6000 0.0001

7 36438

6 0 3617 1608 775 1963 1131 1 83674798 0.34

3 0.967 L7000 0.0001

4 42743

9 0 4255 1897 848 2320 1273 1 97977603 0.42

1 1.248 L8000 0.0007

6 10769 0 2370 370 5260 2631 1 0 11152644 3

0.60

8 0.717 L9000 0.0021

3 0 0 84 0 8916 2962 11879 1 12515824

2 0.811 12.77 L1000 6

0 0.0 - - - - - ³³⁰⁵ * 0 13958180

9 0.48

4 0.499

表 4-6 問題例群２の計算結果（U^k∈[0.05、0.10]）

一般に、0－1ナップサック問題の標準的問題例は、項目の利益と重量の相関性に応じて無 相関、弱相関、強相関の３種に分類されており、このうち強相関の問題例が求解困難とさ れている[28]。強相関性とは、項目の利益を重量の線形固定費関数とすることを意味する。

セットアップ付きナップサック問題（KPS１）では固定費を陽に考慮しているので、提案解法 では強相関の問題例を解くための専用解法[25、27]を採用していない。したがって、L6000、

L7000で実行時間が増大したのは、その 0－1ナップサック問題の仮想項目群の中に強相関

に近い部分集合が出現したためであると判断される。

最後に、本稿と同じ定式化を使用しているセットアップ付きナップサック問題の最新結果

[34]について、比較のため引用しておく。この論文には、最大100グループ、約10000項目

までの問題例について数値実験結果が掲載されている。このうち、ナップサック容量比[0.15、

0.25]の相関性を考慮した最大サイズの10問題例において、計算時間が最小59秒、平均478

秒、最大878 秒であった。この結果は、問題例の発生方法と使用した計算機（1.7GHz）が本 稿のものと異なるので、我々の数値実験結果と直接比較することはできないが、同規模問 題例M100と比較すると計算時間のオーダーが３桁以上違うので、「本稿の提案解法により 大幅な高速化が達成された」と主張できるものと判断する。

参考文献

[1] G.B. Dantzig: “Discrete-Variable Extremum Problems”, Operations Research, vol.5, pp.266-277, 1957

[2] P.C. Gilmore and R.E. Gomory: “The Theory and Computation of Knapsack Functions”, Operations Research, 14(1), pp.1045-1074, 1966

[3] P.J. Kolesar: “A Branch and Bound Algorithm for the Knapsack Problems”, Management Science, vol.13, no.9, pp.723–735, May 1967

[4] H. Greenberg, R.L. Hegerich: “A Branch Search Algorithm for the Knapsack Problems”, Management Science, vol.16, pp.327-332, 1970

[5] E. Horowitz and S. Sahni: “Computing partitions with applications to the knapsack problem”, Journal of the ACM, vol.21, no.2, pp.277−292, April 1974

[6] G.P. Ingargiola and J.F. Korsh: “A Reduction Algorithm for Zero-One Single Knapsack Problems”, Management Science, vol.20, pp.460–463, 1975

[7] O.H. Ibarra and C.E. Kim: “Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems”, Journal of the ACM, vol.22, no.4, pp.463-468, Oct.1975

[8] R.M. Nauss: “An Efficient Algorithm for the 0-1 Knapsack Problem”, Management Science, vol.23, no.1, pp.27-31, 1976

[9] A.A. Zoltners: “A Direct Descent Binary Knapsack Algorithm”, Journal of the ACM, vol.25, no.2, pp.304-311, April 1978

[10] P. Toth: “Dynamic Programming Algorithms for the Zero-One Knapsack Problem”, Computing, vol.25, pp.29-45, 1980

[11] E. Balas and E. Zemel: “An Algorithm for Large Zero-One Knapsack Problems”, Operations Research, vol.28, no.5, pp.119–148, 1980

[12] R.S. Dembo and P.L. Hammer: “A Reduction Algorithm for Knapsack Problems”, Methods of Operations Research, vol.36, pp.49-60, 1980

[13] V. Chvátal: “Hard Knapsack Problems”, Operations Research, vol.28, no.6, pp.402–411, 1980

[14] D. Fayard and G. Plateau: “An Algorithm for the Solution of the 0-1 Knapsack Problem”, Computing, vol.28, pp.269-287, 1982

[15] K. Dudziński and S. Walukiewicz: “Exact Methods for the Knapsack Problem and its Generalizations”, European Journal of Operational Research, vol.28, no.1, pp.3–21, 1987

[16] R.L. Bulfin: “An algorithm for the continuous variable upper bound knapsack problem”, OPSEARCH, 25(2), pp.119-125, 1988

[17] S. Martello and P. Toth: “A New Algorithm for the 0-1 Knapsack Problem”, Management Science, vol.34, pp.633–644, 1988

[18] S. Martello and P. Toth: “Knapsack Problems: Algorithms and Computer Implementations”, John Wiley & Sons, 1990

[19] E.D. Chajakis and M. Guignard: “Exact Algorithms for the Setup Knapsack Problem”, INFOR, vol.32, no.3, pp.124-142, 1994

[20] D. Pisinger: “An expanding-core algorithm for the exact 0-1 knapsack problem”, European Journal of Operational Research, vol.87, pp.175–187, 1995

[21] D. Pisinger: “Algorithms for Knapsack Problems”, Ph.D. thesis, University of Copenhagen, Feb.1995

[22] D. Pisinger: “A Minimal Algorithm for the 0-1 Knapsack Problem”, Operations Research, vol.45, pp.758–767, 1997

[23] S. Martello and P. Toth: “Upper Bounds and Algorithms for Hard 0-1 Knapsack Problems”, Operations Research,vol. 45, no.5, pp.768–778, 1997

[24] E. Y-H. Lin: “A bibliographical survey on some well known non-standard knapsack problems”, INFOR, vol.36, pp.274-317, 1998

[25] S. Martello, D. Pisinger and P. Toth: “Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem”, Management Science, vol.45, no.3, March 1999

[26] U. Pferschy: “Dynamic Programming Revisited: Improving knapsack Algorithm”, Computing, vol.63, no.4, pp.419-430, 1999

[27] A. Kulanoot: “Algorithms for Some Hard Knapsack Problem”, Ph.D. thesis, Curtin University of Technology, Jan.2000

[28] D. Pisinger: “Where are the hard knapsack problems ?”, Computers & Operations Research, vol.32, pp.2271–2282, 2005

[29] U. Akinc: “Approximate and exact algorithms for the fixed-charge knapsack problem”, European Journal of Operational Research, vol.170, pp.363–375, 2006

[30] Y. Yang: “KNAPSACK PROBLEMS WITH SETUP”, Ph.D. thesis, Auburn University, Aug.2006

[31] L.A. McLay and S.H. Jacobson: “Integer knapsack problems with set-up weights”, Computational Optimization and Applications, vol.37, pp.35–47, 2007

[32] M. Caserta, E.Q. Rico and A.M. Uribe: “A cross entropy algorithm for the Knapsack problem with setups”, Computers & Operations Research, vol.35, pp.241–252, 2008 [33] S. Michel, N. Perrot and F. Vanderbeck: “Knapsack Problems with Setups”, European

Journal of Operational Research, vol.196, no.3, pp.909–918, 2009

[34] Y. Yang and R.L. Bulfin: “An exact algorithm for the Knapsack Problem with Setup”, Int.

J. Operational Research, vol.5, no.3, pp.280-291, 2009

[35] 永田 真幸、竹原 有紗、“供給信頼度制約を考慮した電力流通設備更新の平準化支援ツ

ール －プロトタイプの開発－”、電力中央研究所研究報告書R08001、2009

[36] T. Ichimura, K. Kuroda, K. Yamagishi, W. Kawai and K. Sasaki, “Utilization of an asset information base for advanced power transmission asset management”, IEEJ-EIT Joint Symposium on Advanced Technology in Power Systems, 2009

[37] T. Ichimura, R.Yokoyama, H. Magori, “A faster exact method for large-scale knapsack problems with setup costs and times”, International Journal of Operational Research, 2012 Vol.14 No.4, 485-504, 2012

[38] 市村 富保, 黒田 健, 馬郡 英樹, 横山 隆一, “電力設備更新コスト平準化に向けた優先

順位決定方式”, 電力技術・電力系統技術合同研究会, PE-10-136, PSE-10-135, 2010

ドキュメント内 保全コスト平準化に向けた (ページ 96-103)