数理解析研究所講究録
第 1548 巻 2007 年 99-10699

固定費つき複数ナップサック問題の近似解法と厳密解法
Heuristic and Exact Algorithms for the Fixed-Charge Multiple Knapsack Problem
防衛大学校情報工学科
竹岡貴裕 , 山田武夫

TAKEOKA Takahiro, YAMADA Takeo{g44041, yamada}@nda.ac.jp
Department of Computer Science, The National Defense Academy
Yokosuka, Kanagawa 239-8686, Japan1

はじめに個の商品 1, 2, $\cdots,n$ があり, 商品 の重量と利得がそれぞれ ” であるとする. これらを容量がそれぞれ瑞 $(i=1,2, \cdots, m)$ の複数のナップサックに詰め込み, 総利得を最大化する問題は檀数ナップサック問題 (multiple knapsack problem: MKP) と呼ばれ, 多数の研究が発表されて来ている[5, 6, 11]. 本稿ではこれに対してナップサックにそれぞれ費用が付随していて, 各ナップサックの使用には対応する費用を支払わなければならない状況を考える. これを固定畳付き複数ナップサック問題(fixed-charge multiple knapsack problem: FCMKP) と呼ぶが, これは数式では以下のように定式化され$n$る $[13, 14]$

$j$

$w$

$p_{j}$.

FCMKP:maxs.t.

$z(x,y):= \sum_{*=1}^{m}\sum_{j=1}^{n}p_{j}x_{1j}-\sum_{:=1}^{m}f_{1}y$$\sum_{j=1}^{n}w_{j}x_{1j}\leq c_{i}y_{i},$$\sum_{i=1}^{m}X:j\leq 1,$$x_{1j},$$\forall i\in M$$\forall j\in N$$y:\in\{0,1\},$:(1),(2),$\forall i\in M,\forall j\in N$

(3)

.

(4)

ここで $M=\{1,2, \ldots,m\},$ $N=\{1,2, \ldots, n\}$ はそれぞれナップサックと商品の集合を表し, $X:j$ は商晶 $i$の採否を,はナップサック の使用・不使用を表す 0-1 型の決定変数である.
ナップサックのコストがすべて , すなわち $f_{i}\equiv 0(i\in M)$ のときは明らかに :\equiv 1(すべてのナップサックを使用) が最適で, 問題は通常の MKP に帰す. 標準的な 0-1 ナップサック問題 (knapsack problem: KP)
がすでに NP-困難 [3] なので, その拡張である MKP, FCMKP はいずれも-困難であるが, KP, MKPについては過去の研究によりかなり大規模な問題が比較的短時間に解けるようになっている $[5, 6]$
本稿ではラグランジュ緩和, 釘付けテスト, 分枝限定法などの手法 [8] を用いて FCMKP を厳密に解くことを試みるが, 一般性を失うことなく, 以下では商品とナップサックは以下の仮定を満たすものとす$y_{i}$

$i$

$0$

$y$

$N\mathcal{P}$.

る.

100

$A_{1}$$A_{2}$: 問題データ$p_{j},$$w_{j}(j\in N),$$c_{i},$$f_{i}(i\in M)$

はすべて正の整数.

: 商品は相対利得の大きい順に $p_{1}/w_{1}\geq p_{2}/w_{2}\geq\ldots\geq p_{n}/w_{n}$ と整列済み.

A3 : ナップサックは相対容量の大きい順に

2上下界値

2.1

ラグランジュ緩和$\lambda=(\lambda_{1}, \lambda_{2}, \cdots, \lambda_{m})\geq 0$に対して,$c_{1}/f_{1}\geq c_{2}/f_{2}\geq\cdots$\geq Cm/漏と整列済み.

FCMKP のラグランジュ関数を(5)$\iota(x,y;\lambda):=\sum_{:=1j}^{m}\sum_{=1}^{n}(p_{j}-\lambda_{i}w_{j})x_{1j}+\sum_{:=1}^{m}:f_{i})y_{i}$で定義すると, ラグランジュ緩和問題は

LFCMKP$(\lambda)$:
max $L(x,y;\lambda)$st.となる. この問題の最適関数値$\overline{z}_{L}(\lambda)$(3), (4)を最小とする問題 $\min\{z_{L}(\lambda)|\lambda\geq 0\}$ をラグランジュ双対問題という. このとき, 次が成り立っ.
定理 1(i) 任意の$(\ddot{u})\overline{z}_{L}(\lambda)$$\lambda\geq 0$

は$\lambda$

に対して$\overline{z}\iota(\lambda)$

は FCMKP の上界値を与える.

について区分的に線形な凸関数である.

(iii) ラグランジュ双対問題は$\lambda_{1}^{\dagger}=\lambda_{2}^{1}=\cdots=\lambda_{m}\dagger(=\lambda\dagger)$であるような最適解$\lambda^{\dagger}=(\lambda\dagger, \lambda\dagger, \ldots, \lambda\dagger)$を持つ.

証明 :(i), (ii) ラグランジ$\Rightarrow$

緩和の一般論 $[2, 8]$ より容易に導かれる.

(iii) $k:= \arg\min\{\lambda_{i}\}$ とする. すなわち$\lambda_{k}^{\dagger}\leq\lambda^{\dagger},$$\phi(\cdot)$

を. の真偽により 1 または$0$$\forall i\in M$.

(6)をとる真理値関数とすると, LFCMKP$x:j(\lambda^{t})=\phi(i=k, p_{j}-\lambda_{k}^{\dagger}w_{j}>0)$$(\lambda^{\dagger})$の解は,$y:(\lambda^{\dagger})=\phi((\lambda\ddagger c_{1}-f:>0)$

で与えられ, 最適関数値は$\overline{z}_{L}(\lambda^{t})=\sum_{j=1}^{\mathfrak{n}}(p_{j}-\lambda_{k}^{\dagger}w_{j})^{+}+\sum_{1=1}^{m}(\lambda^{\dagger}c;-f:)^{+}$(7)

101となる.

ここで,$(\alpha)^{+}$$:= \max\{\alpha, 0\}$件下で (7) を最小とする$\lambda^{\dagger}$

で,$(\lambda_{i}^{\dagger}c_{i}-f_{i})^{+}$

は$\lambda^{\dot{\dagger}}$について単調非減少関数なので,(6) の条

は$\lambda_{i}^{\dagger}\equiv\lambda_{k}^{\dagger},$$\forall i\in M$を満たすと考えてよい.
定理 1 より, ラグランジ $=$ 緩和問題 LFCMKP
いので,において$(\lambda)$$\lambda_{*}\cdot\equiv\lambda(i\in M)$の場合のみを考えれば良問題は

LFCMKP$(\lambda)$:$m$ 下口 c

$s.t$

.

:

$\sum_{j=1}^{n}(p_{j}-\lambda w_{j})x_{j}+\sum_{:=1}^{m}(\lambda c_{i}-f_{l})y$$x_{j},y:\in\{0,1\},$.

$\forall i\in M,\forall j\in N$(8)(9)と書きかえられる. ここに$x_{j}:= \sum_{*=1}^{m}x_{ij}$である.

$\lambda\geq 0$

に対して,

LFCMKP$(\lambda)$の最適値は$\overline{z}_{L}(\lambda)=\sum_{j=1}^{\mathfrak{n}}(p_{j}-\lambda w_{j})^{+}+\sum_{*=1}^{m}(\lambda \mathfrak{g}-f_{*}\cdot)^{+}$となる. (10) の勾配は ($\lambda$(10)で微分可能ならば)
C-わ\epsilon -L $( \lambda)/d\lambda=\sum_{\lambda c;-f:>0}c_{i}-\sum_{jp-\lambda w_{j}>0}w_{j}$なので,の上界値を2.2を最小とする$\overline{z}_{L}(\lambda)$$\lambda\dagger$

は 2 分探索法で容易に求められる. このようにして得られる FCMKPと記す.

$\overline{z}_{L}$下界値

Pisinger[10] は, 通常の $k1$ ナップサック問題 KP について以下の高速近似解法を提示している. $p_{j},w_{j}(j\in$$N)$ を商品の利得および重量,をナップサック容量とし, 商晶は仮定 A2 に従って番号づけられているとする.
で商品 までの累積利得 (重量) を表すものとし, 臨界商晶を $b= \min\{j|\overline{w}_{j})>c\}$前で定義して,(後) 向きグリーディ解をそれぞれ下のように定める.
$j$$p_{j}$$c$$j$$(\overline{w}_{j})$$\underline{z}_{f}z==\max_{=Jb,\ldots\prime \mathfrak{n}}\{\Phi_{b-1}+p_{j} :下$axc\{\overline{p}_{b}-p_{j} :$J=1,\ldots,-1m$

Pisinger は\overline{w}_{b-1}+w_{j}\leq c\}\lrcorner$\overline{w}_{b}-w_{j}\leq c\}$.と島の大きいほうを KP の下界値とすることを提唱している.
本稿ではこれを FCMKP に拡張する. すなわちナップサックの番号順に逐次上の近似解法を適用し,$\underline{z}_{f}$商品をナップサックに話めていく. この際, ナップサックに収容された商品の総利得がそのナップサックのコスト以下であれば当該ナップサックの使用を取り消し, そこに詰められた商品はすべて解放して次のナップサックに移る. これを最後のナップサックまで繰り返して得られる解を拡張 Pisinger 解と呼び, 対応する下界値を と記す.
$\underline{z}$

102

3

釘付けテスト(10) 式を最小とする ‘最適’ ラグランジュ乗数, および前節の方法による下界値三が計算済みであるとする. また, 商品とナップサックのしきい値を以下によりそれぞれ定義する.
$\theta_{j}$$\lambda\dagger$と対応する上界値$:=p_{j}-\lambda\dagger w_{j},$$\eta;$$\overline{z}:=\overline{z}_{L}(\lambda\dagger)$(11)$:=\lambda^{\uparrow}c_{i}-f_{i}$または 1 として, FCMKP に制約式 $y_{k}=\delta$ を付加した問題を $P(y_{k}=\delta)$ とする. さらに,によるそのラグランジュ緩和を次のように導入する.

次に$\delta$を$0$$\overline{P}(y_{k}=\delta)$$\lambda\dagger$:$m$ 下口 ($s.t$

.

(12)

$\sum_{j=1}^{\mathfrak{n}}\theta_{j}x_{j}+\sum_{i=1}^{m}\eta:y_{i}$(9),$y_{k}=\delta$

この問題の最適値は明らかに(13)$\overline{z}(y_{k}=\delta):=\sum_{j\in N}\theta_{j}^{+}+\sum_{i\neq k}\eta^{+}+\eta_{k}\delta$

で, これより直ちに次が従う.

定理 2(ナップサックの釘付け) すべての $k\in M$ に対して

(i)
(ii)

$\overline{z}-\underline{z}<\eta_{k}\Rightarrow y_{k}^{*}=1$,$\overline{z}-\underline{z}<-\eta_{k}\Rightarrow y_{\dot{k}}=0$

証明 :(i)(10), (13) より$\overline{z}(y_{k}=0)=\overline{z}-\eta_{k}$.

よりであることに注意すると,-三$y_{k}=0$
これは最適解ではく三を得る.
ではありえないことを意味しているので, (i)$\eta_{k}\geq 0\Rightarrow\overline{z}(y_{k}=0)=\overline{z}-\eta_{k}$$0\leq\overline{z}$$<\eta_{k}$が証明された. (ii) も同様に証明される$\blacksquare$

同様に, 商品についても次の釘付け定理が成立する.

定理 3(商品の釘付け) すべての $j\in N$ について,(i) $\overline{z}-g<-\theta_{j}\Rightarrow x_{j}^{*}=0$ ,(ii)$\overline{z}-\underline{z}<\theta_{j}\Rightarrow x_{j}^{\star}=1$.

注 1 ナップサック問題に対する釘付けテストは [1, 4, 7] などにみられる. 本節は最初にラグランジ ュ 緩和を介在させることによって, 同様の手法を FCMKP にも適用可能としたものである.

4厳密解法

FCMKP を解く分枝限定法アルゴリズムの基本的な考え方は, 釘付け後に使用不使用が未確定のナップサックについて, つまり変数 について, 逐次跳 $=1$ または $y:=0$ という条件を付加した ‘子問題’ こ$y_{i}$$t$103
分割していくことである. これを記述するために以下の問題を定義する.

$F_{0}$と凡は $M$ の互いに排反な部分集合 $(F_{0}, F_{1}\subseteq M, F_{0}\cap F_{1}=\emptyset)$ で$K_{1}\subseteq F_{1}$を満たすものとする. これらはそれぞれ$0$.

および 1 に固定されたナップサックの集合を表す. 固定されていないナップサックの集合を $U:=M\backslash (F_{0}\cup F_{1})$ とし, 次の部分間題を考える.

:$P(F_{0},F_{1})$max (1)st.

第 2 節の$\overline{P}(F_{0},F_{1})$$\lambda\dagger$(2), (3), (4),$y_{i}=0,$$\forall i\in F_{0}$$y:=1,$$\forall i\in F_{1}$

,(14)

.

(15)

を用いて上の問題をラグランジ ュ 緩湘すると:max (12)st.

(9), (14), (15)となる.

これらの問題の最適関数値をそれぞれ $z^{*}(F_{0}, F_{1}),$の上界値となる. すなわち,$z^{\star}(F_{0}, F_{1})$$\overline{z}(F_{0}, F_{1})$$z^{\star}(F_{0}, F_{1})\leq\overline{z}(F_{0}, F_{1})$と表記すると, 明らかに $Z(F_{0},F_{1})$ はで, 後者は明らかに$\overline{z}(F_{0}, F_{1})=\sum_{j=1}^{n}\theta_{j}^{+}+\sum_{:\in F_{1}}\eta_{i}+\sum_{\in U}\eta_{i}^{+}$である. すると,もし現時点での下界値-z が$Z(F_{0}, F_{1})<\underline{z}$

.

(16)

を満たしているならば, この部分間題 $P(F_{0}, F_{1})$を終端することが出来る.

枝払いのための条件としては, 上の他に実行可能性と優越性が挙げられる. 最初に, 子問題 $P(F0, F_{1})$でのナップサック総容量を果とし, ナップサックに収容することが確定している商品の総重量を $Wflx$とすると, $Wflx>\overline{c}(F_{0}, F_{1})$ の場合には子問題 $P(F_{0}, F_{1})$ は実行不可能であり, よってこの子問題は終端されることになる.
$\overline{c}(F_{0}, F_{1}):=\sum_{:\in M\backslash F_{O}}$$:= \sum_{j\in I_{1}}w_{j}$

次に,$c_{i}\geq\alpha$’,$f_{1}\leq f_{1’}$

題 $P(F_{0}, F_{1})$ において,かつ $(c:, f_{i})\neq(c_{1’}, f_{1’})$ のとき,ナップサックが $i’$ に優越している場合, ナップサック$i$は $i’$ に優越するという. 子問を使用せずにを使用することは不合理である. よって, ここで $i\in F_{0},$ $i’\in F_{1}$ の場合, 子問題を終端する. $P(F_{0}, F_{1})$ がこのようなナップ
$i$

$i$

$i’$

サックの対を含む場合, この子問題は不合理であるという.
もし $P(F_{0},F_{1})$ がこれらによって終端されず, $U$ が空集合でない場合には $U$ に含まれるナップサック を選び, $P(F_{0}, F_{1})$ の子問題 $P(F_{0}\cup\{i\},F_{1})$ と $P(F_{0}, F_{1}\cup\{i\})$ を新たに生成する.の楊合は $P(F_{0}, F_{1})$は末端子問題で, この場合には $P(F_{0}, F_{1})$ は MKP なので Pisinger のプログラム mulknap[ll] を用いて最適値を得ることが出来る. これが現時点での最良値 より大であればにより下界値を更新する.
$i$$U=\emptyset$$z^{*}(F_{0}, F_{1})$$\underline{z}arrow z^{*}(F_{0}, F_{1})$$\underline{z}$以上をまとめ,FCMKP を解くには第 2 節で求めた下界値ゴリズムを呼べばよい. ただし, 集合は最初ある.

$F_{0}$$:=\emptyset$

で,$F_{1}$$\underline{z}$と釘付けテストの結果を持って次のアルは 1 と釘付けされたナップサックの集合で

104
アルゴリズム B&B $(F_{0}, F_{1})$St $ep1:U:=M\backslash (F_{0}\cup F_{1})$ とする.
Step 2:$Wflx>\overline{c}(F_{0}, F_{1})$Step 3:$\overline{z}(F_{0}, F_{1})$$U=\emptyset$

ならば, Step 5 へ.

または $P(F_{0}, F_{1})$ が不合理である場合, $P(F, R)$ を終端して Step 6 へ.

を計算し F$\overline{z}(F_{0}, F_{1})<\underline{z}$ならば $P(F, R)$ を終端して Step 6 へ.

Step 4: ナップサック $i\in U$ を選び子問題 $P(F_{0}\cup\{i\}, F_{1})$ とを生成する. これらの問
題を再帰的に呼び出して実行し, Step 6 へ.
Step 5: (mulknap[ll] を用いて) この MKP を解いて最適値により下界値を更新する.
ならば$z^{*}(F_{0}, F_{1})$を求める. もし$z^{*}(F_{0}, F_{1})>\underline{z}$$\underline{z}arrow z^{\star}(F_{0}, F_{1})$Step 6: 親問題へ戻る.
このアルゴリズムを実装する際には, Step 4 で分枝に用いるナップサック の選び方, すなわち分枝戦略と, 子問題からなる 2 分木の走査方法を指定する必要がある. 後者については, 幅優先探索なども$i$考えられるが, 本研究ではメモリーの必要量が少なくてすむ深さ優先探索を採用した. 一方, 分枝戦略については次の 2 つを考察した.の大きいものから順) に取り出す. 子問題の分枝戦略 1: ナップサック $i\in U$ を番号順 (すなわち,$P(F_{0}\cup\{i\},F_{1})arrow
P(F_{0},F_{1}\cup\{i\})$の順とする.
走査は$c_{i}/f_{i}$分枝戦略 2: ナップサック $i\in U$ をしきい値$|\eta_{i}|$の小さいものから順に取り出す. 子問題の走査は $\eta:>0$ のときは $P(F_{0}\cup\{i\}, F_{1})arrow P(F_{0}, F_{1}\cup\{i\})$ の順, そうでないときは $P(F_{0}, F_{1}\cup\{i\})arrow P(F_{0}\cup\{i\}, F_{1})$の順とする.

5数値実験

前節の B&B アルゴリズムを数値実験によって評価する. アルゴリズムは $C$ 言語で実装し, IBM $IiS/6000$
Model 270 ワークステーション (CPU: POWER3-II SMP $2way,$ $375MHz$ ) 上で実験を行なった.

5.1実験計回

例題のサイズは $n=20\sim 16000$ および $m=5\sim 50$ で, 下の様式に従ってランダムに生成する.

(a) 商品..

重量 $wj\ddagger[1,10m]$ 上の整数一様分布

利得-$p_{j}$

無相関 (UNCOR): $[1, 1000]$ 上の整数一様分布,$(w_{j})$-弱相関 (WEAK): $[w_{j},w_{j}+200]$ 上の整数一様分布.

-

強相間 (STRONG):$p_{j}$とは独立.

$:=w_{j}+20$(b) ナップサック$\bullet$

容量果$=\lfloor 5CX$

布に従い,$\delta$.

$\delta\cdot\xi_{*}\cdot\rfloor$. ここで$\xi_{i}(i\in M)$

は $\{(\xi_{1}, \ldots,\xi_{m})|\sum_{:=1}^{m}\xi_{i}=1, \xi_{i}\geq 0\}$ 上の一様分

は 025, 050, 075 のいずれかとする.

105.
ここでなので,5.2$\delta$

コスト $f_{i}=\rho_{i}c_{i}$ , ただし

は [0.5, 1.5] 上で (連続) 一様分布.

$\rho_{i}$はナップサックに収容可能な商品の割合を制御するパラメテータで, 商品の平均重量が約 500$\delta=0.50$の場合は全商品のおよそ半分がナップサックに収容可能ということを意味している.

IP ソルバーとの比較

表 1 は $n=20\sim 60$ および $m=5$ の小規模な例題について, 商用ソフト NUOPT Ver. 3.3.0 [9] および XPRESS-IVE Ver.

1-16-20 [12] を用いた場合と, B&B アルゴリズムによる計算結果を比較したもの
CPU 時間 600 秒以内に厳密に解けである. 各相関タイブと $n$ の値ごとに 30 例題をランダムに生成し,た回数 (#solved) と, (解けた場合についての) 平均計算時間が秒で示されている.
この表より, 商用ソフトではかなり小さい問題でも求解が困難なケースが出現するが, B&B アルゴリ
ズムではこの程度の問題はほとんど瞬時に解いていることが分かる.
表 1: IP ソルバーとの比較 $(m=5)$ .

$\overline{NUOPT}$
XPRESS-IVE

B&B$\frac{TyPo\mathfrak{n}lOV\ovalbox{\tt\small REJECT}\epsilon ov\ovalbox{\tt\small REJECT} lOY\ovalbox{\tt\small REJECT}}{UNCOR2030.66300.10300.01}$WEAK

30405060
203040STRONG

50
60
2030
40
50

60

5.3

29
17

14
5

29
15
83

39.85
81.50
77.02
115.1214.23
132.96169.23243.19

.

$0$

30
16
16
92

28.38
98.58
26.27
5.07
28.91

30
23
22
12

30
20
13
54
30
19
20
17
14

7.76
36.68
49.67

30
30
30
30

117.67

go

69.29
9.19
85.38

151.89
70.79
2.84
66.21
23.26
39.17
17.45

0.00
0.01
0.00
0.00

0.06
0.08

$lO$

30

0.00

0.01
0.00
0.02
0.03
0.01
0.00

30
30
30
30
30
30
30

0.01

厳密解

商品数 $n=$ 1000\sim 32000, ナップサック数 $m=$ 10\sim 50 で, 様々な相関タイブの例題について, 上下界値と釘付けを行い, 分枝限定法による厳密解の計算を試みた. 上下界値と釘付けの計算時間はどのが比
この結果, STRONG で $m$ が大きく,較的小さいいくつかの場合を除いて, ナップサックは 90% もしくはそれ以上が または 1 に固定され,ケースも 01 秒以下で, ほとんど無視できる程度である.

$n$

$0$

UNCOR と WEAK では商品も 1/3 程度が に固定されることが多かった.
B&B は, 少数の例外を除いて数秒以内に FCMKP の厳密解を得ており, この間 MULKNAP を呼び出す回数も通常は数回のみである. 戦略の比較では通常戦略 2 が戦略 1 を上回り, STRONG で $m$ が大$0$きい場合には特にこの傾向が顕著である.

6

むすび

固定費つき複数ナップサック問題を定式化し, これを厳密に解くアルゴリズムを与えた. これは. ラグランジュ緩和と釘付けテスト, および分枝限定法を組み合わせたもので, 末端子問題は複数ナップサッ
ク問題 (MKP) であることを利用して既存の MULKNAP プログラムを呼び出して解いている. これに106
よって, $n=32000$ 商品, $m=50$ ナップサック程度の問題でも通常の計算機を用いて 10 秒程度で解くことに成功した.

参考文献[1] R.S. Dembo, P.L. Hammer: “A reduction algorithm for knapsack problems”, Methods of Opemtions Research, 30:49-60, 1980.

[2] M. Fisher: “The Lagrangian relaxation method for solving integer programming problems,” Man-agement Scienoe 50:1861-1871, 2004.
[3] M.R. Garey, D.S. Johnson: Computers and Intractability: A Guide to the Theory of NPCompleteness, Freeman and Company, San Francisco, 1979.

[4] G.P. Ingargiola, F.F. Korsh: “Reduction algorithms for zero-one single knapsack problems,”
Management Science, 20:460-463, 1973.
[5] H. Kellerer, U. Pferschy, D. Pisinger: Knapsack Problems, Springer, Berlin, 2004.
[6] S. Martello, P. Toth: Knapsack Problems: Algorithms and Computer Implementatiotes, John
Wiley&Sons, Chichester, 1990.

[7] R.M. Nauss: Parametric Integer Programming, Univ. Missouri Press, Columbia, MI, 1979.

[8] G.L. Nemhauser, L.A. Wolsey, Integer and Combinato rial Optimization, John Wiley&Sons, NewYork, 1988.
[9] NUOPT Ver. 3.3.0, Mathematical Systems Incorporated, 2002. (http://www.msi.co.jp/nuopt)[10] D. Pisinger: “An expanding-core algorithm for the exact kl knapsack problem,” European Journal of Operational Research, 87:175-187, 1995.
[11] D. Pisinger: “An exact algorithm for large multiple knapsack problems,” Burvpean Journal of Operational Research, 114:528-541, 1999. (Source code ‘mulknap’ available at
http: $//www$ . diku. dk/-pisinger/codes. html)[12] XPRESS-IVE Ver. 1.16.20, Dash Associates, 2006. (http://www.dashoptimization.com)[13] 保田亮, 片岡靖詞: 固定費付き複数ナップサック問題の上界値, OR 学会秋季研究発表会 (東北大学, 2004), 214-215.
[14] 保田亮: 固定費付き複数ナップサック問題一分枝費用法によるアプローチー, 修士論文, 防衛大学校
理工学研究科情報数理専攻, 平成 17 年 3 月.