分岐限定法

このような問題について,解法は種々考案されていますが,ネットワークの最適化 で述べた「分岐限定法」を適用することもできます。

「分岐限定法」を、この問題に適用するように書き直すと

最小化問題$P$が与えられたとして：

(1)

　$P$から,部分問題の集合 $L=\{P_0,P_1,P_2,\cdots,P_n\}$を作り,
　　　初期解を適当に選択してその値$C_0$を求める。
以下の手続きを$L$の元$P_i$の全てについて行う

(2)

　最小問題$P_i$の解の上限値$sup P_i$を求め,　
　　　　　　 $sup P_i <　C_0$なら　 $L \leftarrow L \setminus \{P_i\}$ $(LからP_iを削除)$

(3)

　最小問題$P_i$の解$max P_i$を求め　
　　　　　　　 $max P_i　>　C_0$なら　 $C_0 \leftarrow max P_i$ 　とする

となります。部分問題の造り方は,詰める品物のいくつかを固定して,他の品物を詰めるかどうかの問題にするというものです。
制約条件

$$\begin{eqnarray*} && g_1 x_1 + g_2 x_2 + \cdots +g_m x_m \le G \\ && x_k \in \{0,1 \} ,k=1,2,\cdots,m \\ \end{eqnarray*}$$

のもとで,

$$p_1 x_1 + p_2 x_2 + \cdots +p_m x_m$$

を最大にするのですから,例えば,品物1,2は必ず詰めるとして, すなわち,$x_1=x_2=1$とおき,部分問題として

$$\begin{eqnarray*} && g_3 x_3 \cdots +g_m x_m \le G- (g_1 + g_2) \\ && x_k \in \{0,1 \} ,k=3,4,\cdots,m \\ \end{eqnarray*}$$

のもとで,

$$(p_1+p_2)+p_3 x_3 + p_4 x_4 + \cdots +p_m x_m$$

を最大化するというものです。