列生成算法在整数规划中的应用示例 我将为您详细讲解列生成算法如何用于求解带整数约束的大规模线性规划问题。这个示例将展示列生成如何与分支定界结合（即分支定价），有效处理变量数量巨大的整数规划问题。 问题描述 考虑一个简化版的资本预算问题：某公司有5个潜在投资项目，每个项目需要不同数量的资金投入，并产生特定收益。公司总预算为100万元。目标是选择项目组合，在预算限制下最大化总收益。 由于项目可能需要分期投资或存在其他复杂因素，传统建模会引入大量变量。我们采用列生成方式，每个列代表一个可行的项目投资方案。 数学模型 主问题（MP）： 目标：最大化总收益 ∑ⱼ cⱼλⱼ 约束：∑ⱼ aᵢⱼλⱼ ≤ bᵢ (i=1,...,m) （资源约束） ∑ⱼ λⱼ = 1 （凸组合约束） λⱼ ≥ 0 （连续松弛） 其中λⱼ表示是否采用第j个方案，cⱼ是方案收益，aᵢⱼ是资源消耗。 解题过程 步骤1：初始化限制主问题（RMP） 首先构造一个初始可行解集合。最简单的是加入"空方案"（零收益、零消耗）和几个简单方案，确保RMP可行。初始RMP只有少量列，容易求解。 步骤2：求解RMP线性松弛 求解当前RMP的线性规划松弛，得到最优解λ* 和对应的对偶变量值πᵢ（资源约束）和σ（凸组合约束）。这些对偶变量为定价问题提供关键信息。 步骤3：定价问题（子问题） 定价问题目标是寻找 Reduced Cost 最大的列： maximize {cⱼ - ∑ᵢ πᵢaᵢⱼ - σ} 这通常是一个整数规划或组合优化问题。在本例中，定价问题是寻找收益权重最大的项目组合，其中收益权重 = 实际收益 - πᵢ×资源消耗。 步骤4：判断是否终止 如果定价问题找到的列 Reduced Cost > 0，说明该列能改善当前解，将其加入RMP，返回步骤2。如果 Reduced Cost ≤ 0，说明当前解已是最优，列生成过程结束。 步骤5：整数性处理 当线性松弛解包含分数值时，需要结合分支定界法： 在分支节点上继续使用列生成求解线性松弛 分支决策可能影响定价问题的结构 需要设计不破坏定价问题可解性的分支策略 关键技巧 稳定化技术：防止对偶变量震荡，加速收敛 分支策略：通常采用Ryan-Foster分支或基于原始变量的分支 启发式方法：利用定价问题寻找整数可行解 算法优势 仅生成有潜力的列，避免全枚举 内存效率高，适合大规模问题 可充分利用问题特殊结构 这个框架广泛应用于车辆路径、机组调度等组合优化问题，能有效处理变量数量指数级增长的情况。