列生成算法在多重背包问题中的应用示例
题目描述
考虑一个多重背包问题：有 \(n\) 类物品，第 \(i\) 类物品的重量为 \(w_i\)，价值为 \(v_i\)，且最多可选择 \(b_i\) 个（即数量上限）。背包的总容量为 \(C\)。目标是在不超过背包容量的前提下，选择物品（每类物品可选多个，但不超过 \(b_i\)）使得总价值最大。
该问题可建模为整数规划，但直接求解计算复杂度高。列生成算法通过将问题分解为主问题（限制主问题）和子问题（定价问题），利用线性规划松弛逐步生成有价值的列（即物品的选择模式），逼近最优解。
解题过程
1. 问题建模
整数规划模型：
设 \(x_i\) 表示第 \(i\) 类物品的选择数量，模型为：
\[\max \sum_{i=1}^n v_i x_i \]
\[\text{s.t.} \quad \sum_{i=1}^n w_i x_i \leq C \]
\[0 \leq x_i \leq b_i, \quad x_i \in \mathbb{Z}^+ \]
直接求解该模型在物品类别多时计算困难，因此采用列生成算法。
2. 列生成框架设计
列生成将问题转化为线性规划松弛，并动态生成变量（列）：
- 主问题（Master Problem, MP）：初始仅包含部分列（如每类物品选0个或1个），通过线性规划松弛求解。
- 子问题（Pricing Problem）：检查是否存在未加入主问题的列（即物品组合）能改善当前目标函数，通过计算检验数（Reduced Cost）判断。
限制主问题（Restricted Master Problem, RMP）的构建：
假设初始列集合为每类物品单独选择的模式（即单位向量），RMP 的线性规划松弛形式为：
\[\max \sum_{p \in P} \left( \sum_{i=1}^n v_i a_{ip} \right) \lambda_p \]
\[\text{s.t.} \quad \sum_{p \in P} \left( \sum_{i=1}^n w_i a_{ip} \right) \lambda_p \leq C \]
\[\sum_{p \in P} a_{ip} \lambda_p \leq b_i \quad (\forall i=1,\dots,n) \]
\[\lambda_p \geq 0 \]
其中：
- \(p\) 是一个选择模式（列），\(a_{ip}\) 表示在该模式下第 \(i\) 类物品的数量。
- \(\lambda_p\) 表示选择模式 \(p\) 的比例（连续松弛）。
3. 列生成步骤
步骤 1：初始化 RMP
初始列集合包含 \(n\) 个列，每列对应只选一类物品（\(a_{ip} = 1\) 当 \(p=i\)，否则为 0）。例如，第 \(i\) 列的系数为 \((w_i, e_i)\)（\(e_i\) 是第 \(i\) 个单位向量）。
步骤 2：求解 RMP
求解当前 RMP 的线性规划，得到最优解 \(\lambda^*\) 和对偶变量：
- \(\pi\)：对应容量约束 \(\sum w_i x_i \leq C\) 的对偶变量。
- \(\mu_i\)：对应每类物品数量约束 \(\sum_p a_{ip} \lambda_p \leq b_i\) 的对偶变量。
步骤 3：定价子问题（检验新列）
子问题的目标是找到一个新列 \(p\)（即向量 \(a_p = (a_{1p}, \dots, a_{np})\)），使得其检验数（Reduced Cost）为正：
\[\text{Reduced Cost} = \sum_{i=1}^n v_i a_{ip} - \pi \left( \sum_{i=1}^n w_i a_{ip} \right) - \sum_{i=1}^n \mu_i a_{ip} \]
整理得：
\[\text{Reduced Cost} = \sum_{i=1}^n \left( v_i - \pi w_i - \mu_i \right) a_{ip} \]
子问题转化为一个整数规划：
\[\max \sum_{i=1}^n (v_i - \pi w_i - \mu_i) a_i \]
\[\text{s.t.} \quad 0 \leq a_i \leq b_i, \quad a_i \in \mathbb{Z}^+ \]
注意：此处 \(a_i\) 是选择第 \(i\) 类物品的数量，且子问题解需满足 \(\sum w_i a_i \leq C\)（但通常忽略，因 \(\pi\) 已隐含容量价值）。
步骤 4：判断收敛
- 若子问题的最优值 \(\leq 0\)：说明无改善列，当前 RMP 的解是原问题线性规划松弛的最优解。
- 若子问题的最优值 \(> 0\)：将对应列 \(a_p\) 加入 RMP，返回步骤 2。
4. 获取整数解
列生成结束后，得到线性规划松弛的最优解。若解为整数，则它是原问题的最优解；否则需结合分支定界法（分支价格法）得到整数解。
5. 实例演示
假设 \(n=2\)，\(w=(3,4)\)，\(v=(5,6)\)，\(b=(2,1)\)，\(C=8\)。
初始 RMP：列集为 \(\{(1,0), (0,1)\}\)（即每类物品单独选）。
RMP 形式：
\[\max 5\lambda_1 + 6\lambda_2 \]
\[\text{s.t.} \quad 3\lambda_1 + 4\lambda_2 \leq 8 \]
\[\lambda_1 \leq 2, \quad \lambda_2 \leq 1, \quad \lambda_1, \lambda_2 \geq 0 \]
求解得 \(\lambda_1=2, \lambda_2=0.5\)，目标值 \(=13\)。对偶变量：\(\pi=1.5\)（容量约束），\(\mu_1=0\)（第一类约束紧），\(\mu_2=0\)（第二类约束未紧）。
定价子问题：
系数为 \(v_i - \pi w_i - \mu_i\)：
- 物品1：\(5 - 1.5\times3 - 0 = 0.5\)
- 物品2：\(6 - 1.5\times4 - 0 = 0\)
子问题：\(\max 0.5a_1 + 0a_2\)，约束 \(a_1 \leq 2, a_2 \leq 1\)。最优解 \(a=(2,0)\)，检验数 \(=1>0\)。
加入新列 \(a=(2,0)\)：
新列重量 \(=3\times2=6\)，价值 \(=5\times2=10\)。更新 RMP，重新求解得更优解（例如 \(\lambda_{新}=1, \lambda_1=0, \lambda_2=0.5\)，目标值 \(=13\) 但可能改善）。迭代直至收敛。
最终得到松弛最优解，再通过分支定界求整数解（本例整数解为选两个物品1，价值10）。
关键点总结
- 列生成通过分解问题降低计算复杂度。
- 定价子问题利用对偶信息识别有效列。
- 多重背包的列生成中，子问题是简单的整数规划（可高效求解）。