分枝限定法

分枝限定法の基本的な考え方は、与えられた問題を直接解くことが難しい場合に、その 問題をいくつかの部分問題（Partial problem）に分解し、それらを解くことによって元の 問題を解こうとするものである。ある問題から、その部分問題を生成する手続きは分枝操

作（branching operation）と呼ばれる。この分枝操作により生成された部分問題がまだ

難しくて解けない場合には、問題をさらに分解する操作を繰り返し適用する。この操作に より、問題の規模は次第に小さくなり、いつかは解くことができるようになる。

しかし、分枝操作をしただけでは、結局全ての解を数え上げる列挙法（enumeration

method）と同じことになるので、大規模問題を解くことはできない。そこで、最適解を与

える見込みのない問題を終端（terminate）して、考察の対象から除外するという限定操

作（bounding operation）を導入する必要がある。限定操作を行うために現時点までに求

まった部分問題の最適解のうちで最良のものを暫定解として記憶しておく。このとき、部 分問題の目的関数が暫定解よりも良い値を与えないことが判定できれば、その部分問題は それ以上分解することは無意味なので部分問題は終端される。

この判定を行うためには、通常、部分問題の制約条件を緩めた緩和問題（relaxation

problem）が解かれる。このような分枝操作および限定操作を繰り返しながら探索を行う

のが分枝限定法であり、その探索過程は、図4-1のような探索木（search tree）を用いて 表現できる。

図4-1 分枝限定法の探索木

第4章 経年機器の最適更新順位づけ

46

探索木の根ノードが原問題に対応し、各ノードがその部分問題となる。また、分解され たノードはその子ノードの部分問題を解くことにより、間接的に解かれることになる。葉 ノードに対応する部分問題の状態は3種類に分けられ、1)その部分問題は終端されている か、2)部分問題の最適解が求まっているか、3)あるいはそのどちらかでもない場合である。

部分問題が終端されるか、部分問題の最適解が求まった場合には、その部分問題はそれ 以上分解する必要はない。そうでない場合は部分問題をさらに分解する必要があり、その ような部分問題は活性（active）であるという。探査木において活性な部分問題が無くな った時点で全ての部分問題が解かれたことになり、そのときの暫定解は最適解になる。

＜分枝限定法の原理＞：0-1ナップサック問題（0-1 knapsack problem） １）一般化した問題

n個のアイテムからなる有限集合N、各々のアイテムの重量Siと価値Vi、およびナッ ﾌﾟサックの重量制限bが与えられたとき、アイテムの重量の合計がbを超えないという 条件の下で、価値の合計を最大にするようにNからアイテムを選択せよ。

２）例題

自分が、ぬいぐるみ専門の泥棒だと仮定する。ある晩、高級ぬいぐるみ店に忍び込み、

マニアの間で高額で取引されているクマの人形を盗もうとした。人形は4種類あり、そ れらの値段と重さは、図4-2のようになっている。転売価格の合計が最大になるように クマの人形を選んで逃げなければならないが、いつも盗品を入れて逃げるのに愛用して いるナッﾌﾟサックはとても古く、7kgよりも重い荷物を入れると底が抜けてしまう。さ て、どの人形を持って逃げればよいだろうか？

図4-2 ４種のクマ人形とナップサック

第4章 経年機器の最適更新順位づけ

47

この問題はアイテムをナップサックに入れるとき1、入れないときを0とすると、下記 のような、整数計画問題（integer programming problem）、すなわち、ある制約を満たす 整数の組合せで、ある関数を最大化（もしくは最小化）するものを見つける問題として定 式化される。

最大化 ΣVi・Si

条 件 ΣSi・Xi ≦b

Xi ∈{0,1}

分枝限定法は、整数計画法に対する標準的な厳密解法であり、多くの汎用的なソフトウ エアは線形計画法を解くアルゴリズムと分枝限定法から構成されている。また、その概念 は、列挙法（力づく法）により理解することができる。

上記ナップサック問題に対する列挙木は、まず極小人形をナップサックに入れる場合と 入れない場合の2通りを考える。次に、極小人形をナップサックに入れた場合に対して、

小人形をナップサックに入れた場合と入れない場合に分ける。さらに中人形を入れた場合 と入れない場合・・・と順次2つに分けていくことによって、n個のアイテムからどのア イテムをナップサックに入れるかを表す木ができる。この木の先端まで行けば、持って逃 げられる価値の合計と重量の合計が求まる。したがって、ナップサックの重量上限を超え ないものの中で価値の合計が最大のものを選択することによって最適解が求まる。

すなわち、最適解は、「極小人形＋大人形」の2体をナップサックに入れて出すことで ある。この場合の、転売価格は44（16+26）万円で、合計重量はナップサックの限界重量 である7kgとなる。

図4-3 ナップサック問題に対する列挙木。

＊黒丸は、ナップサックが破れてしまうこと（実行不可能解）を表す

第4章 経年機器の最適更新順位づけ

48

しかし、木の先端の数は2^ｎ個あり、これらをすべて探索するのは計算の無駄であるばか りか、一般には、膨大な数となり、実行不可能である。

分枝限定法は、木の中の探しても無駄な部分の探索を下界と上界の概念を用いて最適性 を失うことなしに省略することができる。ここで、下界（lower bound）とは、最適値よ りも小さいか（運がよければ）等しいことが保証されている値のことである。通常は何ら かの方法で見つけた実行可能解（制約を満たす解）の目的関数を用いる。ナップサック問 題の下界は、単位重量当たりの価値Vi/Siの大きいものから順に限界を超えない限り詰めて いく、いわゆる貪欲アルゴリズム（greedy algorithm）を用いることによって得られる。

一方、上界（upper bound）は、常に最適値よりも大きいか、運が良ければ等しい値を 指し、ナップサック問題では人形を切ってしまうことを許すことによって得られる。言い 換えると、変数Xiの整数条件を実数条件に緩めた以下の問題を解くことによって上界を得 ることができる。

最大化 ΣVi・Si

条 件 ΣSi・Xi ≦b

0 ≦Xi≦ 1

この問題は、線形計画問題そのものであり、このように制約条件を緩めた問題を一般に緩

和問題（relaxation problem）とよぶ。整数条件を実数条件に緩めることによって得られ

る緩和問題を特に、線形計画緩和問題（linear programming relaxation problem）とよぶ。

ナップサック問題の線形計画緩和問題は、前述の貪欲アルゴリズムによって簡単に解く ことができる。すなわち、単位重量当たりの価値Vi/Siの大きいものから順にbを超えな い限り詰めていくだけである。緩和問題の場合には、実数を許すので、ナップサックに入 れられる人形は切られてしまう可能性がある。

列挙法では各人形を持っていくか行かないかで2つに分けることにより、枝分れをさせ ていった。ここで上界はさらに枝分れをさせていったときに得られる解の値に等しいかそ れよりも大きい。よって、上界が今までに得られている下界に等しいかそれよりも小さく なったら、もう枝分れして調べる必要はなくなる。これが分枝限定法における「限定」操 作であり、適切な木の探索順と上界を用いることによって、大規模なナップサック問題で も比較的短時間で解くことが可能となる。

第4章 経年機器の最適更新順位づけ

49

上界（緩和）

下界（実行可能）

最適解

上界（実行可能）

下界（緩和）

最適解

最大化問題の場合 最小化問題の場合

図4-4 上界・下界の説明と分枝限定法による最適解の探索

図4-4の原問題における上界値を貪欲法により求めると下の式により、46.5万円となる。

これは極小人形1体、小人形1体、そして中人形を1/2体とした組み合わせである。

＊原問題における上界値 46.5万円 ①各人形の単位重量あたり価値

極小人形 ：16万円/2ｋｇ ＝8 万円/ｋｇ 小人人形 ：19万円/3ｋｇ ＝6.33 万円/ｋｇ 中人形 ：23万円/4ｋｇ ＝5.75 万円/ｋｇ 大人形 ：28万円/5ｋｇ ＝5.6 万円/ｋｇ ②貪欲法による、上界値

重量 価値 極小人形 2ｋｇ 16万円×1 ＝16 万円 小人形 3ｋｇ 19万円×1 ＝19 万円 中人形 2ｋｇ（7-2-3） 23万円×2/4 ＝12.5 万円 合 計 7ｋｇ 46.5 万円

その後、極小人形を持ち出した分枝（左半分）のツリーの探索により、最終端において 44万円（極小人形1体、大人形1体）という下界値が求まる。

一方、極小人形を持ち出さない分枝（右半分）では、上界は42（19+23）万円（小人形 1体と中人形1体）となり左半分のツリーの最終端で得られた下界（44万円）よりも小さ いので、これ以上調べる必要はない。すなわち、終端とすることができる。