经典的Benders分解算法将决策变量分为简单变量和复杂变量两类。其中复杂变量一般是指整数变量，而简单变量一般是指连续变量。在Benders考虑的一类特殊问题中，先将复杂变量的值固定，从而将问题规约为一个一般的线性规划问题（子问题），然后利用割平面的方式向主问题添加极点约束和极射线约束，以达到主问题缩小可行域的目的。因而，该分解算法的基本思想是将大问题分解为小问题（主问题和子问题），并且通过子问题构造主问题的可行约束，以使主问题的逐渐收敛。实质是一种行生成方法。
对于一个整数规划问题，与0-1整数规划问题中将离散变量的取值范围松弛为[0,1]之间的连续变量不同，拉格朗日松弛算法是将模型中的部分约束进行松弛，并且这些被松弛的约束并不是被完全去掉，而是利用拉格朗日乘子在目标函数上增加相应的惩罚项，对不满足这些约束条件的解进行惩罚。
列生成（Column generation）算法是一种用于求解大规模线性优化问题的非常高效的算法，被应用于调度问题、切割问题、车辆路径问题、选址问题等。列生成算法是一种可用于求解线性规划问题的精确算法，其本质是单纯形法的延伸扩展
点击空白处退出提示
评论