基于线性规划的“装箱问题（Bin Packing）”的列生成算法求解示例
字数 4280 2025-12-16 07:21:19

好的，我随机选择线性规划领域一个尚未讲解过的经典算法题目：

基于线性规划的“装箱问题（Bin Packing）”的列生成算法求解示例

问题描述

想象你是一家物流公司的员工，有一批大小不一的货物需要装进标准尺寸的集装箱里运走。每个集装箱（箱子）的容量是固定的（例如容量为1单位）。每件货物有一个重量（大小）\(w_i\)，满足 \(0 < w_i \le 1\)。目标是用尽可能少的箱子，把所有货物装完，且每个箱子内货物的总重量不能超过其容量。

这就是经典的 一维装箱问题（Bin Packing Problem, BPP）。它是一个强NP难组合优化问题。当货物种类很多、数量很大时，直接建模求解非常困难。我们可以利用线性规划中的列生成算法，将其分解为主问题和定价子问题，从而高效地求解其线性规划松弛，并得到高质量的整数解。

循序渐进解题过程

我们的目标是将问题建模，并用列生成算法求解其线性规划松弛，最后通过舍入或启发式得到一个整数解。

第一步：建立集合覆盖模型

传统的装箱问题建模（每个箱子是否使用，每件货物放进哪个箱子）会导致变量和约束非常多，模型很“笨重”。

一个更巧妙的建模思路是 集合覆盖模型：

  • 我们不关注“箱子”，而是关注 “装箱模式（Packing Pattern）”。
  • 一个装箱模式，就是一个能放进一个箱子（容量为1）的货物组合，其总重量不超过1。
  • 例如，有3种货物，大小分别为0.5, 0.3, 0.2。那么一个有效的模式可以是 [0.5, 0.3, 0.2]，也可以是 [0.5, 0.5]，或者 [0.3, 0.3, 0.3] (如果货物数量足够多)。

设：

  • 所有可能的装箱模式集合为 \(P\)。
  • 对于模式 \(p \in P\)，定义参数 \(a_{ip} = 1\) 表示货物 \(i\) 在模式 \(p\) 中出现了一次，否则为0。
  • 设货物 \(i\) 的需求（数量）为 \(b_i\)。
  • 决策变量 \(x_p \ge 0\)：表示我们使用模式 \(p\) 的次数。

整数规划模型如下：

\[\begin{align*} \min \quad & \sum_{p \in P} x_p \\ \text{s.t.} \quad & \sum_{p \in P} a_{ip} x_p \ge b_i, \quad \forall \text{货物} i \\ & x_p \in \mathbb{Z}^+, \quad \forall p \in P \end{align*} \]

  • 目标：最小化使用的箱子总数（即所有模式的使用次数之和）。
  • 约束：对于每种货物 \(i\)，在所有被使用的模式中，它出现的总次数至少要满足它的需求 \(b_i\)。
  • 这是一个 集合覆盖问题 的整数规划形式。

第二步：线性规划松弛与列生成的挑战

将 \(x_p\) 松弛为连续变量 \(x_p \ge 0\)，得到线性规划（LP）松弛：

\[\begin{align*} \min \quad & \sum_{p \in P} x_p \\ \text{s.t.} \quad & \sum_{p \in P} a_{ip} x_p \ge b_i, \quad \forall i \\ & x_p \ge 0, \quad \forall p \in P \end{align*} \]

核心挑战：模式集合 \(P\) 的数量是天文数字（所有可能组合）。我们不可能在模型中显式地列出所有 \(x_p\) 变量。

列生成思想：我们从一个很小的、可行的模式子集 \(P‘ \subset P\) 开始，求解这个限制性主问题（Restricted Master Problem, RMP）。然后，我们设计一个定价子问题（Pricing Subproblem），来检查是否还有不在 \(P’\) 中的模式（列），能改善当前RMP的解（即检验简约成本（Reduced Cost）是否为负）。

第三步：求解限制性主问题（RMP）

  1. 初始化：构建一个最简单的初始可行列集合 \(P'\)。一个简单的方法是，为每一种货物 \(i\) 创建一个模式，该模式只包含一件这种货物，重复 \(b_i\) 次直到填满箱子容量（但BPP中通常一件货物就是一个独立物品，所以更常见的初始化是“一种货物一个模式”，但数量是分数）。更实用的初始化是使用单纯形分解或启发式方法生成一批质量较好的模式。
    例如，假设我们有三种货物，大小分别为0.6, 0.4, 0.3，需求分别为 \(b_1=2, b_2=3, b_3=1\)。
    初始模式可以设为：

    • 模式1: [0.6] (对应货物1)
    • 模式2: [0.4] (对应货物2)
    • 模式3: [0.3] (对应货物3)
      这显然不是好模式，但能保证RMP有可行解（\(x_1=2, x_2=3, x_3=1\)，目标值=6）。

  2. 求解RMP：使用单纯形法求解这个只有少数列的RMP。得到最优解 \(x_p^*\) 和对应的对偶变量 \(\pi_i^* \ge 0\)（每个货物覆盖约束对应一个对偶变量）。

第四步：定价子问题——寻找可进基的列

在线性规划单纯形法中，一个变量（列）能否进基改善目标函数，看它的 简约成本（Reduced Cost） \(c_p - \pi^T A_p\)。

  • 在我们的模型中，原始成本 \(c_p = 1\)（每个模式使用一次的成本是1个箱子）。
  • \(A_p\) 是列向量，其第 \(i\) 个元素 \(a_{ip}\) 表示模式 \(p\) 包含货物 \(i\) 的个数。
  • 因此，模式 \(p\) 的简约成本为：\(\bar{c}_p = 1 - \sum_{i} \pi_i^* a_{ip}\)。

定价子问题的目标：寻找一个可行的装箱模式 \(p\)（即 \(\sum_i w_i a_{ip} \le 1, a_{ip} \in \mathbb{Z}^+\)），使得其简约成本 \(\bar{c}_p < 0\)。如果找不到，则当前RMP的解就是整个LP松弛的最优解。

由于 \(1\) 是常数，寻找 \(\bar{c}_p < 0\) 等价于寻找一个模式满足：

\[\sum_{i} \pi_i^* a_{ip} > 1 \]

并且该模式是可行的（总重量 \(\le 1\)）。

这本身就是一个背包问题（Knapsack Problem）：

\[\max \quad & \sum_{i} \pi_i^* y_i \\ \text{s.t.} \quad & \sum_{i} w_i y_i \le 1 \\ & y_i \in \mathbb{Z}^+, \quad \forall i \]

  • 变量 \(y_i\)：在要生成的新模式中，包含货物 \(i\) 的件数。
  • 目标：最大化“利润” \(\sum \pi_i^* y_i\)，利润来自对偶变量的值。
  • 约束：总重量不超过箱子容量1。

我们需要求解这个背包问题。虽然背包也是NP难的，但其规模通常只与货物种类数有关，而与货物总数量无关，因此对于实际中种类不太多的情况，可以用动态规划高效求解。

第五步：迭代与终止

  1. 求解定价子问题（背包问题），得到最优解 \(y^*\) 和最大利润 \(V^*\)。
  2. 判断：
    • 如果 \(V^* > 1\)，则意味着找到了一个模式 \(p_{new}\)，其简约成本 \(\bar{c}_{p_{new}} = 1 - V^* < 0\)。这是一个可以改善目标函数的列。
    • 将 \(p_{new}\)（由 \(y^*\) 定义）作为新列加入RMP的系数矩阵 \(A\) 中（即 \(a_{i, p_{new}} = y_i^*\)）。
    • 回到第三步，重新求解新的RMP。
    • 如果 \(V^* \le 1\)，则说明没有简约成本为负的列了。列生成过程结束，当前RMP的解就是原大规模LP松弛的最优解。

第六步：获得整数解

通过列生成，我们得到了原装箱问题LP松弛的最优解 \(x_{LP}^*\) 和最优值 \(OPT_{LP}\)。因为 \(OPT_{LP}\) 是整数解最优值 \(OPT_{IP}\) 的下界，即 \(OPT_{LP} \le OPT_{IP}\)。

但 \(x_{LP}^*\) 可能是分数解（例如，某个模式使用0.5次）。我们需要得到一个可行的整数装箱方案。常用方法有：

  1. 启发式舍入：将 \(x_{LP}^*\) 中值较大的变量（例如 \(x_p \ge 0.9\)）直接取整为1，将其对应的模式直接使用。然后处理剩余的未被这些模式覆盖的货物。
  2. 分支定价（Branch and Price）：这是最精确的方法。在列生成框架上加入分支定界。当LP松弛解为分数时，通过分支规则（例如，强制某两件货物必须/不能在同一箱）创建新的子问题，在每个子节点上继续运行列生成。这是求解大规模整数规划的先进技术。
  3. 简单启发式：直接对列生成最后得到的那个RMP（它包含了算法找到的所有“好”模式）进行整数规划求解（调用MIP求解器）。虽然这个RMP的变量数远小于原问题，但整数求解仍然可能较慢，可作为近似。
  4. 首次适应递减（FFD）等经典启发式：有时直接使用 \(OPT_{LP}\) 作为参考，对剩余货物运行FFD算法，效果也很好。

小结与意义

通过这个例子，我们看到了列生成算法如何将一个变量极多的组合优化问题（装箱问题）分解：

  • 主问题（RMP）：负责协调各种“模式”的使用比例，以最小化总使用次数。
  • 子问题（定价问题）：负责根据当前解的市场价格（对偶变量 \(\pi_i\)），生成最有利可图的“新产品”（装箱模式）。

这种“主问题-子问题”的分解，允许我们隐式地处理指数级数量的变量，只需在需要时动态生成有价值的列。这不仅是求解大规模线性规划的有力工具，更是解决许多实际中大规模整数规划问题（如车辆路径、机组排班、切割库存）的核心框架。装箱问题的列生成求解，完美展示了这一框架的威力与美感。

好的，我随机选择线性规划领域一个尚未讲解过的经典算法题目： 基于线性规划的“装箱问题（Bin Packing）”的列生成算法求解示例 问题描述 想象你是一家物流公司的员工，有一批大小不一的货物需要装进标准尺寸的集装箱里运走。每个集装箱（箱子）的容量是固定的（例如容量为1单位）。每件货物有一个重量（大小）\(w_ i\)，满足 \(0 < w_ i \le 1\)。目标是用尽可能少的箱子，把所有货物装完，且每个箱子内货物的总重量不能超过其容量。 这就是经典的 一维装箱问题（Bin Packing Problem, BPP） 。它是一个强NP难组合优化问题。当货物种类很多、数量很大时，直接建模求解非常困难。我们可以利用线性规划中的 列生成算法 ，将其分解为主问题和定价子问题，从而高效地求解其线性规划松弛，并得到高质量的整数解。 循序渐进解题过程 我们的目标是将问题建模，并用列生成算法求解其线性规划松弛，最后通过舍入或启发式得到一个整数解。 第一步：建立集合覆盖模型 传统的装箱问题建模（每个箱子是否使用，每件货物放进哪个箱子）会导致变量和约束非常多，模型很“笨重”。 一个更巧妙的建模思路是 集合覆盖模型 ： 我们不关注“箱子”，而是关注 “装箱模式（Packing Pattern）” 。 一个装箱模式，就是一个能放进一个箱子（容量为1）的货物组合，其总重量不超过1。 例如，有3种货物，大小分别为0.5, 0.3, 0.2。那么一个有效的模式可以是 [0.5, 0.3, 0.2] ，也可以是 [0.5, 0.5] ，或者 [0.3, 0.3, 0.3] (如果货物数量足够多)。 设： 所有可能的装箱模式集合为 \(P\)。 对于模式 \(p \in P\)，定义参数 \(a_ {ip} = 1\) 表示货物 \(i\) 在模式 \(p\) 中出现了一次，否则为0。 设货物 \(i\) 的需求（数量）为 \(b_ i\)。 决策变量 \(x_ p \ge 0\)：表示我们使用模式 \(p\) 的次数。 整数规划模型如下： \[ \begin{align* } \min \quad & \sum_ {p \in P} x_ p \\ \text{s.t.} \quad & \sum_ {p \in P} a_ {ip} x_ p \ge b_ i, \quad \forall \text{货物} i \\ & x_ p \in \mathbb{Z}^+, \quad \forall p \in P \end{align* } \] 目标：最小化使用的箱子总数（即所有模式的使用次数之和）。 约束：对于每种货物 \(i\)，在所有被使用的模式中，它出现的总次数至少要满足它的需求 \(b_ i\)。 这是一个 集合覆盖问题 的整数规划形式。 第二步：线性规划松弛与列生成的挑战 将 \(x_ p\) 松弛为连续变量 \(x_ p \ge 0\)，得到线性规划（LP）松弛： \[ \begin{align* } \min \quad & \sum_ {p \in P} x_ p \\ \text{s.t.} \quad & \sum_ {p \in P} a_ {ip} x_ p \ge b_ i, \quad \forall i \\ & x_ p \ge 0, \quad \forall p \in P \end{align* } \] 核心挑战 ：模式集合 \(P\) 的数量是 天文数字 （所有可能组合）。我们不可能在模型中显式地列出所有 \(x_ p\) 变量。 列生成思想 ：我们从一个很小的、可行的模式子集 \(P‘ \subset P\) 开始，求解这个 限制性主问题（Restricted Master Problem, RMP） 。然后，我们设计一个 定价子问题（Pricing Subproblem） ，来检查是否还有不在 \(P’\) 中的模式（列），能改善当前RMP的解（即检验 简约成本（Reduced Cost） 是否为负）。 第三步：求解限制性主问题（RMP） 初始化 ：构建一个最简单的初始可行列集合 \(P'\)。一个简单的方法是，为 每一种货物 \(i\) 创建一个模式，该模式只包含一件这种货物，重复 \(b_ i\) 次直到填满箱子容量（但BPP中通常一件货物就是一个独立物品，所以更常见的初始化是“一种货物一个模式”，但数量是分数）。更实用的初始化是使用 单纯形分解 或启发式方法生成一批质量较好的模式。 例如，假设我们有三种货物，大小分别为0.6, 0.4, 0.3，需求分别为 \(b_ 1=2, b_ 2=3, b_ 3=1\)。 初始模式可以设为： 模式1: [ 0.6 ] (对应货物1) 模式2: [ 0.4 ] (对应货物2) 模式3: [ 0.3 ] (对应货物3) 这显然不是好模式，但能保证RMP有可行解（\(x_ 1=2, x_ 2=3, x_ 3=1\)，目标值=6）。 求解RMP ：使用单纯形法求解这个只有少数列的RMP。得到最优解 \(x_ p^ \) 和对应的 对偶变量 \(\pi_ i^ \ge 0\)（每个货物覆盖约束对应一个对偶变量）。 第四步：定价子问题——寻找可进基的列 在线性规划单纯形法中，一个变量（列）能否进基改善目标函数，看它的 简约成本（Reduced Cost） \(c_ p - \pi^T A_ p\)。 在我们的模型中， 原始成本 \(c_ p = 1\)（每个模式使用一次的成本是1个箱子）。 \(A_ p\) 是列向量，其第 \(i\) 个元素 \(a_ {ip}\) 表示模式 \(p\) 包含货物 \(i\) 的个数。 因此，模式 \(p\) 的简约成本为：\(\bar{c} p = 1 - \sum {i} \pi_ i^* a_ {ip}\)。 定价子问题的目标 ：寻找一个 可行的装箱模式 \(p\)（即 \(\sum_ i w_ i a_ {ip} \le 1, a_ {ip} \in \mathbb{Z}^+\)），使得其简约成本 \(\bar{c}_ p < 0\)。如果找不到，则当前RMP的解就是整个LP松弛的最优解。 由于 \(1\) 是常数，寻找 \(\bar{c} p < 0\) 等价于寻找一个模式满足： \[ \sum {i} \pi_ i^* a_ {ip} > 1 \] 并且该模式是可行的（总重量 \(\le 1\)）。 这本身就是一个 背包问题（Knapsack Problem） ： \[ \max \quad & \sum_ {i} \pi_ i^* y_ i \\ \text{s.t.} \quad & \sum_ {i} w_ i y_ i \le 1 \\ & y_ i \in \mathbb{Z}^+, \quad \forall i \] 变量 \(y_ i\)：在要生成的新模式中，包含货物 \(i\) 的件数。 目标：最大化“利润” \(\sum \pi_ i^* y_ i\)，利润来自对偶变量的值。 约束：总重量不超过箱子容量1。 我们需要求解这个 背包问题 。虽然背包也是NP难的，但其规模通常只与 货物种类数 有关，而与货物总数量无关，因此对于实际中种类不太多的情况，可以用动态规划高效求解。 第五步：迭代与终止 求解定价子问题（背包问题），得到最优解 \(y^ \) 和最大利润 \(V^ \)。 判断 ： 如果 \(V^* > 1\)，则意味着找到了一个模式 \(p_ {new}\)，其简约成本 \(\bar{c} {p {new}} = 1 - V^* < 0\)。这是一个可以改善目标函数的列。 将 \(p_ {new}\)（由 \(y^ \) 定义）作为新列加入RMP的系数矩阵 \(A\) 中（即 \(a_ {i, p_ {new}} = y_ i^ \)）。 回到 第三步 ，重新求解新的RMP。 如果 \(V^* \le 1\)，则说明没有简约成本为负的列了。 列生成过程结束 ，当前RMP的解就是原大规模LP松弛的最优解。 第六步：获得整数解 通过列生成，我们得到了原装箱问题LP松弛的最优解 \(x_ {LP}^* \) 和最优值 \(OPT_ {LP}\)。因为 \(OPT_ {LP}\) 是整数解最优值 \(OPT_ {IP}\) 的下界，即 \(OPT_ {LP} \le OPT_ {IP}\)。 但 \(x_ {LP}^* \) 可能是分数解（例如，某个模式使用0.5次）。我们需要得到一个可行的整数装箱方案。常用方法有： 启发式舍入 ：将 \(x_ {LP}^* \) 中值较大的变量（例如 \(x_ p \ge 0.9\)）直接取整为1，将其对应的模式直接使用。然后处理剩余的未被这些模式覆盖的货物。 分支定价（Branch and Price） ：这是最精确的方法。在列生成框架上加入分支定界。当LP松弛解为分数时，通过分支规则（例如，强制某两件货物必须/不能在同一箱）创建新的子问题，在每个子节点上继续运行列生成。这是求解大规模整数规划的先进技术。 简单启发式 ：直接对列生成最后得到的那个RMP（它包含了算法找到的所有“好”模式）进行整数规划求解（调用MIP求解器）。虽然这个RMP的变量数远小于原问题，但整数求解仍然可能较慢，可作为近似。 首次适应递减（FFD）等经典启发式 ：有时直接使用 \(OPT_ {LP}\) 作为参考，对剩余货物运行FFD算法，效果也很好。 小结与意义 通过这个例子，我们看到了列生成算法如何将一个变量极多的组合优化问题（装箱问题）分解： 主问题（RMP） ：负责协调各种“模式”的使用比例，以最小化总使用次数。 子问题（定价问题） ：负责根据当前解的市场价格（对偶变量 \(\pi_ i\)），生成最有利可图的“新产品”（装箱模式）。 这种“主问题-子问题”的分解，允许我们 隐式地处理指数级数量的变量 ，只需在需要时动态生成有价值的列。这不仅是求解大规模线性规划的有力工具，更是解决许多实际中 大规模整数规划问题（如车辆路径、机组排班、切割库存）的核心框架 。装箱问题的列生成求解，完美展示了这一框架的威力与美感。