第 4 章 設備更新コスト平準化問題の定式化と解法
4.2 設備更新コスト平準化問題の解法（セットアップ付きナップサック問題）
4.2.1 セットアップ付きナップサック問題の厳密解法
セットアップ付きナップサック問題の厳密解法を説明するにあたって、基本となるナップ サック問題の厳密解法を4.2.1.1で示す。その上で、4.2.1.2にてセットアップ付きナップサ ック問題の厳密解法を示す。
4.2.1.1 ナップサック問題の解法
変数が0,1範囲である0-1ナップサック問題(KP)は、以下のように定式化される。
（KP）(目的関数) max
∑
= M 1 i
i i
x c
(制約条件) a x b
M i
i
i
∑
1
{ } 0,1
x
i∈ (
i=1,,M)
0-1ナップサック問題の厳密解法の解法手順は以下の通りである。
（STEP1）目的関数の上限値を取得する。上限値の取得にあたり、ナップサック問題の緩和 問題を考え、その解を得る。
（STEP2）目的関数の下限値を取得する。これは、上記ナップサック問題を満たす 𝑥𝑖 を見 つけることで、得ることができる。問題の解になりうる範囲の解を実行可能解と 呼ぶ。
（STEP3）分枝限定法(branch and bound method)の活用により厳密解を求める。このとき、
（STEP1）(STEP2)の手法で見つけた上下限値を活用して、ナップサック問題の最 適解の範囲を限定しながら厳密解として求める。
これらの手順を、次に概観する。（STEP1）では、上記 0-1 ナップサック問題の変数𝑥𝑖は、
0-1条件、すなわち、0、または、1の離散値しか取らないが、これを、0 ≤ 𝑥𝑖 ≤ 1の連続値 で置き換え、その最適解を求めることで上限値を算定する。すなわち、（KP）に対する緩和 問題（relaxed problem）（RKP）を解くこととなる。
（RKP） (目的関数) max
∑
= M 1 i
i i
x c
(制約条件) a x b
M i
i
i
∑
1
0 ≤ 𝑥𝑖≤ 1
(
i=1,,M)
ただし、
a r c
i i
i
=
としたとき、 𝑎𝑖 、 𝑐𝑖 、 𝑥𝑖 の添え字、𝑟𝑖が降順に並べられている順にソ ートされているものとする。これに対しては文献[1]における下記定理を活用する。（RKP）の最適解は以下のように得ることができる。
( )
(
>)
=
∑
=
<
=
=
k j x 0
a b a x
k j 1 x
j
k 1 k
1 i
i k
j
（ = ∑ >
=
b a i min k
i 1 j
''
j ）
上記が解となる理由は、図 4.5からわかるように、係数比の大きい順に並べたて、順に𝑥𝑖＝1 と設定すると、制約条件側の和が増えた場合に、目的関数値の和が最大になることによる.
そして、制約境界値に対し、上記𝑥𝑘の値を取ることで、目的関数値が最大となる。このよ うにして得られる緩和されたナップサック問題に対する解法は貪欲法（Greedy Method）と 呼ばれる。
図 4.5 目的関数値と制約値との関係 a
c
1 1
a c
2 2
a c
3 3
a c
p -p
1 1 ｰ
a c
p
p a
c
n n
M
∑ck
∑ak
したがって、この時得られる（RKP）の目的関数値が（KP）の目的関数の上限値になると いえる。また、(STEP2)の下限値に関しては、上記最適解でxk1ならば、xk 0として与 えることができる。
図 4.6 分枝限定法のイメージ
（STEP3）の解法として、分枝限定法(Branch-and-Bound method)を活用する。
この手法は、別名、間接列挙法(Implicit Enumeration)と呼ばれるように、完全列挙法
(Complete Enumeration)を基盤として探索の効率化を図った手法である。分枝限定法は、
与えられた問題を直接解くことが難しい場合に、その問題をいくつかの子問題に分解し、
それらを解くことによって与えられた問題を解くことで実現される。子問題に分割するこ とによって、その問題規模を小さくし、また、子問題の最適解のうち最良のものが、親問 題の最適解となる必要がある。ただし、分解した子問題を解くことが難しい場合には、そ の子問題をさらに、分解していく。この手順を繰返し適用することによって、最終的に直 接解くことができる問題に到達し、それらの解を総合することによって、与えられた問題 を解くことができる。この分解する操作を分枝操作と呼ぶ。
また、分解された子問題を解くにあたり、そのいかなる実行可能解も、現状得られている 解、もしくは、他の子問題の最適解の方が優良な解が得られることが分かっている場合は、
その子問題に対し分枝操作を継続する必要はない。このように、分枝操作を停止すること で、考察の対象から除外することを限定操作と呼ぶ。これによって、効率的に解く対象の 子問題を限定することができる。この探索の効率化の手段として、得られた解の良し悪し を判定するための道具が必要であり、その道具として緩和法が採用されることが多い。緩 和法が有効に作用すれば、分枝限定法の性能は大幅に向上するが、緩和法の力が弱ければ、
分枝限定法は列挙法の性能に近づき、組合せ爆発の現象を招く。したがって、分枝限定法 による成功の鍵は、良い緩和法の採用にかかっている。一般的な緩和法は、上記の
（STEP1）,(STEP2)のようにして、上限値や下限値を求め、問題の最適解の範囲判断を行う 手段として使われる。このような限定操作を行うことが一般的である。限定操作の効率化 は、子問題を解く順番などによって、その性能が大きく変わる。
Root
xj =1 xj =0
4.2.1.2 セットアップ付きナップサック問題の厳密解法
0-1 ナップサック問題を分枝限定法で解くにあたっては、変数𝑥𝑖を 0 または 1 に固定する ことによって子問題とし、各子問題に対し、（STEP1）、(STEP2)での上限値、下限値を利用 して、解くべき問題対象を限定することによって、最適解を求めることができる。
これを活用して、以下で示すセットアップ付きナップサック問題（KPS）の解法が、同様 の手順で実現できることを示す。
（KPS）(目的関数) max
M i
ni j
ij ij
x c
1 1
(制約条件)
y b d x
a
M
i i i
M i
ni j
ij
ij
∑
∑∑
1 1 1
x
ij y
i
i1,,M;j1,,ni
0 , 1
, y
x
ij i
i1,,M;j1,,ni
解法手順は以下の通りである。
セットアップ付きナップサック問題（KPS）の緩和問題は、以下となるが、この緩和問題 がナップサック問題に帰着できることを示す。
（RKPS）(目的関数) max
M i
ni j
c
ijx
ij 1 1(制約条件)
y b d x
a
M
i i i
M i
ni j
ij
ij
∑
∑∑
1 1 1
x
ij y
i
i1,,M;j1,,ni 1
0
0 x
ij 1 , y
i
(
i=1,,M;j=1,,ni)
なお、各
i
に対し、a r c
ij ij
ij
=
を置き、r
i1 r
i2 r
iniとなるように、添え字が入れ替え られていることを前提とする。このとき、各i
について、(KPS)解法手順
(STEP1)KPS 問題の上限境界を求めるために、KPS問題の緩和問題として、セットアッ
プ項の無い緩和問題RKSへ変形し、その上限境界を求める。
(STEP2)KPS問題の実行可能解を求める。これが下限境界となる。
(STEP3)分枝限定法により、(STEP1)(STEP2)で求めた上下限を範囲として、セットアッ プ付きナップサック問題KPSの厳密解を求める。
k n
d a
c d
a c
i i
k j
ij k j
ij
i mi
j ij mi j
ij
, , 1 max
1 1
1
1
を満たす
m
i(
i=1,,M)
をとり、= ∑
= mi 1 j ij '
1
i
c
c
、c c
i,j' mi 1 -j ,
i +
= ( j = m
i+ 1 , , n
i)
d a
a
imi 1
j ij
' 1
i
= ∑ +
=
、
a a
i,j 'mi 1 -j ,
i +
= ( j = m
i+ 1 , , n
i)
'
n m 1 n
i i iとおくと、上記、RKPSは、セットアップ項の無い以下の緩和問題RKSと同一であること が示されている。
（RKS） (目的関数) max ∑∑
= = M
1 i
n'i 1 j
ij ' ijx c (制約条件)
b x a
M i
n'i j
' ij
ij
∑∑
1 1
0 x
ij 1 (
i=1,,M;j=1,,n'i)
これにより、（KPS）問題は、ナップサック問題と同様に厳密解を得ることができる。