列生成算法在电信网络资源分配问题中的应用示例 题目描述 考虑一个电信网络资源分配问题：某电信公司需要为多个客户分配网络带宽资源。网络包含若干条链路，每条链路有固定的带宽容量。每个客户有多个服务请求，每个请求需要特定的带宽量，并在不同链路上产生不同的收益。目标是选择一组请求进行服务，使得总收益最大化，同时不违反任何链路的带宽容量限制。 具体参数： 链路集合：L = {1, 2, ..., m}，链路j的容量为C_ j 客户请求集合：R = {1, 2, ..., n}，每个请求i需要带宽a_ ij在链路j上，并产生收益p_ i 决策变量：x_ i = 1表示接受请求i，否则为0 数学模型（整数规划）： Maximize ∑ {i∈R} p_ i x_ i Subject to: ∑ {i∈R} a_ ij x_ i ≤ C_ j, ∀j∈L x_ i ∈ {0,1}, ∀i∈R 由于请求数量n可能非常大（例如数百万），直接求解整数规划不可行。我们使用列生成算法求解其线性规划松弛，再结合分支定界得到整数解。 解题过程 步骤1：构造限制主问题（RMP） 初始时，只考虑一个请求子集R' ⊆ R（例如空集或少量请求） RMP的线性规划松弛为： Maximize ∑ {i∈R'} p_ i x_ i Subject to: ∑ {i∈R'} a_ ij x_ i ≤ C_ j, ∀j∈L 0 ≤ x_ i ≤ 1, ∀i∈R' 步骤2：求解RMP并获得对偶变量 使用单纯形法求解当前RMP，得到最优解x* 和对偶变量值 对偶变量：设π_ j为对应容量约束∑a_ ij x_ i ≤ C_ j的对偶变量（π_ j ≥ 0） 步骤3：定价问题（子问题） 目标：检查是否存在未加入RMP的请求i∈R\R'，其检验数（reduced cost）为正 请求i的检验数：rc_ i = p_ i - ∑_ {j∈L} a_ ij π_ j 定价问题：寻找使rc_ i最大的请求i，即max_ {i∈R} {p_ i - ∑_ j a_ ij π_ j} 由于请求数量大，定价问题需要高效算法。在本问题中，可根据请求特征设计搜索策略。 步骤4：判断最优性并更新RMP 如果定价问题的最优值max rc_ i ≤ 0（或小于给定容忍度），则当前RMP解是原问题线性松弛的最优解，算法终止 否则，将检验数为正的请求对应的列（变量）加入RMP，返回步骤2 步骤5：获取整数解 得到线性松弛最优解后，使用分支定界法寻找整数解 在分支定界过程中，每个节点仍可用列生成求解线性松弛 实例演示 设网络有2条链路，容量C1=10, C2=15。现有3个请求（初始R'）： 请求1：带宽需求(a11=2, a12=3)，收益p1=5 请求2：带宽需求(3,1)，收益p2=4 请求3：带宽需求(1,2)，收益p3=3 初始RMP： Max 5x1 + 4x2 + 3x3 s.t. 2x1 + 3x2 + x3 ≤ 10 3x1 + x2 + 2x3 ≤ 15 0 ≤ x1,x2,x3 ≤ 1 求解得x1=1, x2=1, x3=1，收益=12，对偶变量π1=0.6, π2=1.2 定价问题：计算未加入请求的检验数。假设新请求i：带宽(2,2)，收益4.5 rc_ i = 4.5 - (2×0.6 + 2×1.2) = 4.5 - 3.6 = 0.9 > 0，应加入该列。 更新RMP，加入x4，重新求解。重复直到无正检验数请求，最后应用分支定界得整数解。 关键点 列生成有效处理大规模问题，仅动态生成必要变量 定价问题的效率至关重要，需利用问题结构优化 最终需结合整数规划方法得到实际可行解