列生成算法在广告投放优化问题中的应用示例
字数 2290 2025-11-02 13:20:39

列生成算法在广告投放优化问题中的应用示例

问题描述
假设一家广告公司要为多个客户在多个广告位上进行投放优化。每个广告位有固定的展示次数（库存），每个客户有不同的广告系列（campaign），每个系列有最低展示量要求、目标受众和出价。目标是最大化总广告收入，同时满足库存约束和客户要求。

具体数学模型：

  • 设广告位集合为 \(I\)，每个广告位 \(i \in I\) 的库存为 \(S_i\)
  • 客户广告系列集合为 \(J\)，每个系列 \(j \in J\) 需至少展示 \(D_j\) 次，出价为 \(p_j\)（每展示收入）
  • 决策变量 \(x_j\) 表示分配给系列 \(j\) 的展示总次数
  • 约束：每个广告位 \(i\) 分配给所有系列的总展示次数不超过 \(S_i\)，且 \(x_j \geq D_j\)

关键难点
直接建模需定义变量 \(x_{ij}\)（广告位 \(i\) 分给系列 \(j\) 的展示次数），但广告位和系列数量大时，变量规模爆炸。列生成通过动态生成“分配模式”来高效求解。

列生成建模过程

  1. 主问题（Master Problem, MP）
    • 定义“分配模式”：每个模式 \(k\) 对应一个广告位 \(i\) 的可行分配方案，即一个向量 \(a_{jk}\) 表示该模式下分给系列 \(j\) 的展示次数。
    • 设模式 \(k\) 的使用次数为 \(\lambda_k\)，其收入为 \(\sum_j p_j a_{jk}\)
    • MP 模型：

\[ \max \sum_k \left( \sum_j p_j a_{jk} \right) \lambda_k \]

\[ \text{s.t.} \quad \sum_k \lambda_k \leq S_i \quad (\forall i \in I) \quad \text{（每个广告位库存约束）} \]

\[ \sum_k a_{jk} \lambda_k \geq D_j \quad (\forall j \in J) \quad \text{（系列最低展示量）} \]

\[ \lambda_k \geq 0 \]

  1. 限制主问题（RMP）

    • 初始仅包含少数模式（如每个广告位单独分配一个系列），求解 RMP 得到对偶变量 \(\mu_i\)（对应库存约束）和 \(\pi_j\)（对应展示量约束）。

  2. 子问题（Pricing Problem）

    • 对每个广告位 \(i\)，生成新模式 \(k\) 的检验数为：

\[ \text{Reduced Cost} = \sum_j p_j a_j - \mu_i - \sum_j \pi_j a_j \]

 其中 $ a_j $ 为新模式中分给系列 $ j $ 的展示次数。
  • 子问题目标：最大化 \(\sum_j (p_j - \pi_j) a_j\)，约束为 \(\sum_j a_j \leq S_i\) 和 \(a_j \geq 0\)。
  • 此问题实质是单广告位上的背包问题：选择系列分配展示次数以最大化净收益。

迭代求解步骤

  1. 初始化

    • 为每个广告位创建一个简单模式（如全部分配给出价最高的系列），加入 RMP。

  2. 循环迭代

    • 步骤1：求解当前 RMP，得到对偶变量 \(\mu_i, \pi_j\)。
    • 步骤2：对每个广告位 \(i\)，求解子问题：

\[ \max \sum_j (p_j - \pi_j) a_j, \quad \text{s.t.} \quad \sum_j a_j \leq S_i, \quad a_j \geq 0 \]

 若最优值 $ > \mu_i $，则新模式可加入 RMP。
  • 步骤3：若无新模式可改善目标值，当前解即最优；否则将新模式加入 RMP，重复步骤1。
  1. 终止条件
    • 所有广告位的子问题 reduced cost 均非正，说明无改进空间。

实例演示
假设：

  • 广告位1库存 \(S_1 = 1000\)，广告位2库存 \(S_2 = 1500\)
  • 系列A：出价 \(p_A=5\)，要求 \(D_A=800\)；系列B：出价 \(p_B=3\)，要求 \(D_B=1000\)

迭代1：

  • 初始模式：广告位1全分给A（收入5000），广告位2全分给B（收入4500）
  • 求解 RMP 得 \(\pi_A=5, \pi_B=3\)（对偶变量）
  • 子问题：对广告位1，计算 \((p_A-\pi_A)=0, (p_B-\pi_B)=0\)，无改善；同理广告位2无改善。
  • 但当前解不满足系列B展示量要求（仅1500<1000? 需检查约束）。

迭代修正：

  • 调整初始模式，加入满足下限的可行解后重新计算对偶变量，再通过子问题生成更优模式（如混合分配A和B）。
  • 最终生成模式可能如：广告位1分600次给A、400次给B，广告位2分200次给A、1300次给B，以满足需求并最大化收入。

关键点总结

  • 列生成将大规模问题分解为“主问题+子问题”，通过动态生成列（模式）避免枚举所有变量。
  • 子问题的效率至关重要：本例中为背包问题，可用贪心或动态规划快速求解。
  • 广告投放场景中，列生成可轻松扩展至多广告位、多受众定向等复杂约束。
列生成算法在广告投放优化问题中的应用示例 问题描述 假设一家广告公司要为多个客户在多个广告位上进行投放优化。每个广告位有固定的展示次数（库存），每个客户有不同的广告系列（campaign），每个系列有最低展示量要求、目标受众和出价。目标是最大化总广告收入，同时满足库存约束和客户要求。 具体数学模型： 设广告位集合为 \( I \)，每个广告位 \( i \in I \) 的库存为 \( S_ i \) 客户广告系列集合为 \( J \)，每个系列 \( j \in J \) 需至少展示 \( D_ j \) 次，出价为 \( p_ j \)（每展示收入） 决策变量 \( x_ j \) 表示分配给系列 \( j \) 的展示总次数 约束：每个广告位 \( i \) 分配给所有系列的总展示次数不超过 \( S_ i \)，且 \( x_ j \geq D_ j \) 关键难点 直接建模需定义变量 \( x_ {ij} \)（广告位 \( i \) 分给系列 \( j \) 的展示次数），但广告位和系列数量大时，变量规模爆炸。列生成通过动态生成“分配模式”来高效求解。 列生成建模过程 主问题（Master Problem, MP） 定义“分配模式”：每个模式 \( k \) 对应一个广告位 \( i \) 的可行分配方案，即一个向量 \( a_ {jk} \) 表示该模式下分给系列 \( j \) 的展示次数。 设模式 \( k \) 的使用次数为 \( \lambda_ k \)，其收入为 \( \sum_ j p_ j a_ {jk} \) MP 模型： \[ \max \sum_ k \left( \sum_ j p_ j a_ {jk} \right) \lambda_ k \] \[ \text{s.t.} \quad \sum_ k \lambda_ k \leq S_ i \quad (\forall i \in I) \quad \text{（每个广告位库存约束）} \] \[ \sum_ k a_ {jk} \lambda_ k \geq D_ j \quad (\forall j \in J) \quad \text{（系列最低展示量）} \] \[ \lambda_ k \geq 0 \] 限制主问题（RMP） 初始仅包含少数模式（如每个广告位单独分配一个系列），求解 RMP 得到对偶变量 \( \mu_ i \)（对应库存约束）和 \( \pi_ j \)（对应展示量约束）。 子问题（Pricing Problem） 对每个广告位 \( i \)，生成新模式 \( k \) 的检验数为： \[ \text{Reduced Cost} = \sum_ j p_ j a_ j - \mu_ i - \sum_ j \pi_ j a_ j \] 其中 \( a_ j \) 为新模式中分给系列 \( j \) 的展示次数。 子问题目标：最大化 \( \sum_ j (p_ j - \pi_ j) a_ j \)，约束为 \( \sum_ j a_ j \leq S_ i \) 和 \( a_ j \geq 0 \)。 此问题实质是单广告位上的背包问题：选择系列分配展示次数以最大化净收益。 迭代求解步骤 初始化 为每个广告位创建一个简单模式（如全部分配给出价最高的系列），加入 RMP。 循环迭代 步骤1 ：求解当前 RMP，得到对偶变量 \( \mu_ i, \pi_ j \)。 步骤2 ：对每个广告位 \( i \)，求解子问题： \[ \max \sum_ j (p_ j - \pi_ j) a_ j, \quad \text{s.t.} \quad \sum_ j a_ j \leq S_ i, \quad a_ j \geq 0 \] 若最优值 \( > \mu_ i \)，则新模式可加入 RMP。 步骤3 ：若无新模式可改善目标值，当前解即最优；否则将新模式加入 RMP，重复步骤1。 终止条件 所有广告位的子问题 reduced cost 均非正，说明无改进空间。 实例演示 假设： 广告位1库存 \( S_ 1 = 1000 \)，广告位2库存 \( S_ 2 = 1500 \) 系列A：出价 \( p_ A=5 \)，要求 \( D_ A=800 \)；系列B：出价 \( p_ B=3 \)，要求 \( D_ B=1000 \) 迭代1 ： 初始模式：广告位1全分给A（收入5000），广告位2全分给B（收入4500） 求解 RMP 得 \( \pi_ A=5, \pi_ B=3 \)（对偶变量） 子问题：对广告位1，计算 \( (p_ A-\pi_ A)=0, (p_ B-\pi_ B)=0 \)，无改善；同理广告位2无改善。 但当前解不满足系列B展示量要求（仅1500 <1000? 需检查约束）。 迭代修正 ： 调整初始模式，加入满足下限的可行解后重新计算对偶变量，再通过子问题生成更优模式（如混合分配A和B）。 最终生成模式可能如：广告位1分600次给A、400次给B，广告位2分200次给A、1300次给B，以满足需求并最大化收入。 关键点总结 列生成将大规模问题分解为“主问题+子问题”，通过动态生成列（模式）避免枚举所有变量。 子问题的效率至关重要：本例中为背包问题，可用贪心或动态规划快速求解。 广告投放场景中，列生成可轻松扩展至多广告位、多受众定向等复杂约束。