拉格朗日松弛(Lagrange relaxation),理学-数学-运筹学-整数规划,常见的求解大规模整数规划或混合整数规划的有效方法。对偶理论和方法是最优化的基本工具,也是整数规划中内容最丰富,应用最广泛的松弛方法之一。考虑一般整数规划问题:式中是有限整数集。令。在不同的应用模型中,函数以及可能具有不同的结构和特殊性质。假设约束是所谓的“难”处理约束,即它们的存在使最优化问题很难求解,而是所谓的“容易”处理约束。拉格朗日松弛的基本思想是把难处理的约束通过乘子移到目标函数上去,只在优化问题中保留容易处理的约束,从而得到原问题的一个松弛问题,而最优的松弛问题可通过以乘子为变量的对偶问题来求得。问题的可行域可定义为。对于,构造拉格朗日函数如下:。极小化可得问题(P)的拉格朗日松弛问题:,称为对偶函数。拉格朗日对偶问题可表示如下:。弱对偶定理:。弱对偶定理表明对偶问题(D)为原问题(IP)的最优值提供了一个下界。在某些情况下,可通过求解对偶问题(D)找到原问题(IP)的最优解。类似于线性整数规划的情况,弱对偶性成立,故总是能提供原问题的一个下界。