ナップサック問題

ナップサック問題#

ナップサック問題（knapsack problem）は価値 $p_{i}$ やサイズ $v_{i}$ が様々な $n$ 個の品物が与えられた時、合計重量がナップサックの許容重量を超えない範囲で合計の価値が最大化するように品物を詰める問題。整数計画問題（Integer programming）のひとつで0-1整数計画問題という。

\begin{array}{r} {Maximize}_{x_{i}} \sum_{i = 1}^{n} p_{i} x_{i} \\ subject to \sum_{i = 1}^{n} v_{i} x_{i} \leq V \end{array}

$x_{i} \in {0, 1}$ ：ナップサックに入れるかどうか
$v_{i}$ ：サイズ
$p_{i}$ ：価値
$V$ ：ナップサックの容量

貪欲法#

ナップサックの有名な近似解は

サイズあたりの価値 $p_{i} / v_{i}$ が高い順に品物の添字を並べかえる
品物を1から順にナップザックに詰め込んでいき詰め込めなければストップする

というもの。

貪欲法の例

Amazon.comにおいて空輸してでも「翌日配送」の表示を出すかどうかのレコメンド問題（Mondal et al, 2022）で使われていたもの。

問題

\begin{array}{r} {argmax}_{λ_{i}} \sum E ({Revenue}_{i}) \\ s. t. \sum_{i} E ({Cost}_{i}) \leq Budget \end{array}

$λ_{i} \in {0, 1}$ ：商品 $i$ を表示するときに「翌日配送」の表示をするかどうか
- 翌日配送は売上を高める可能性があるが空輸するのでコストも掛かる
$E (R_{i})$ ：商品 $i$ の推定売上
- $E (R_{i}) = λ_{i} \cdot {price}_{i} \cdot Δ_{i}$
- $Δ_{i}$ ：speed sensitivity。翌日配送でupliftする売上

アルゴリズム

利益スコア（benefit score）を計算して、商品をbenefit scoreの降順に並べる

{benefit score}_{i} = {\frac{{price}_{i} \cdot Δ_{i}}{{weight}_{i} \cdot {cost}_{i}^{f l y}}}_{i}

予算内なら順にレコメンド対象にしていく

$F L Y := \emptyset, k := 1, {Budget}^{r e s} := B$
while $({Budget}^{r e s} - d_{k} \cdot {weight}_{k} \cdot {cost}_{k}^{f l y}) \geq 0$ do
- $F L Y := F L Y \cup {{product}_{k}}$
- ${Budget}^{r e s} := {Budget}^{r e s} - d_{k} \cdot {weight}_{k} \cdot {cost}_{k}^{f l y}$
- $k := k + 1$
end

参考：Mondal, A., Majumder, A., & Chaoji, V. (2022, August). ASPIRE: Air Shipping Recommendation for E-commerce Products via Causal Inference Framework. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (pp. 3584-3592).

線形計画問題への近似と貪欲法#

貪欲法のとき、最初に詰め込めなくなる品物の番号を $i^{*}$ として、

\begin{array}{r} x_{i}^{*} = {\begin{cases} 1 & if i = 1, \dots, i^{*} - 1 \\ \frac{1}{v_{i^{*}}} (V - \sum_{i = 1}^{i^{*} - 1} v_{i}) & if i = i^{*} \\ 0 & if i = i^{*} + 1, \dots, n \end{cases} \end{array}

とおくと、これは $x_{i} \in {0, 1}$ という制約を $0 \leq x_{i} \leq 1$ に置き換えた線形計画問題の最適解になる（寒野, 2019）

これは整数計画問題であるナップサック問題の実行可能解ではないため、

\begin{array}{r} x_{i}^{*} = {\begin{cases} 1 & if i = 1, \dots, i^{*} - 1 \\ 0 & if i = i^{*}, \dots, n \end{cases} \end{array}

とすると、これは貪欲法になる

（※貪欲法は最適解とは限らない）

分岐限定法#

離散最適化問題の厳密解法。

$x_{i} \in {0, 1}, i = 1, \dots, n$ なら、解は $2^{n}$ 個の組み合わせのうちにある。それを列挙木で列挙して解いていく

動的計画法#

典型的な DP (動的計画法) のパターンを整理 Part 1 ～ナップサック DP 編～ - Qiita

参考文献#

寒野善博（2019）『最適化手法入門』、講談社サイエンティフィック

（reading list）