一般分配问题的拉格朗日松弛算法

在用分枝定界法解整数规划(IP)时,常以相应的线性规划(LP)为原问题的松弛问题。对于极小化问题来说,相应LP的目标函数的最小值就成为IP的目标函数的下界。对松弛问题的选择标准原则上为:1.与对应的IP的最优值要尽量接近。2.松弛问题要尽量容易解。[2]拉格朗日算子松驰法(LR)在这两方面要优于LP松弛法。LR引入一系列拉格朗日算子将原问题分解为几个容易解的子问题。