拉格朗日松弛：一种优化方法，把原问题中“难处理”的约束用拉格朗日乘子并入目标函数，将其转化为更容易求解的子问题；通过调整乘子来得到原问题的下界（最小化问题）或上界（最大化问题），常用于整数规划与组合优化。
/ləˈɡræn(d)ʒiən ˌriːlækˈseɪʃən/
Lagrangian relaxation can turn a hard integer program into easier subproblems.
拉格朗日松弛可以把困难的整数规划转化为更容易求解的子问题。
By applying Lagrangian relaxation to the capacity constraints, we obtained a tight lower bound and improved the branch-and-bound search.
对容量约束进行拉格朗日松弛后，我们得到了较紧的下界，并改进了分支定界的搜索效率。
Lagrangian 来自法国数学家 Joseph-Louis Lagrange（拉格朗日），指用“拉格朗日函数/乘子”把约束纳入目标函数的思想；relaxation（松弛） 在优化中指“放宽/弱化某些约束以获得更易解的近似问题”。合起来即“用拉格朗日乘子对约束进行松弛”的方法。（在不同语境中也会涉及对偶、下界/上界与乘子更新等概念。）
Select Language