面对大规模整数规划/混合整数规划，往往直接采用割平面法和分支定界法求解是不现实的，这时候就需要对大规模整数规划/混合整数规划问题先进行分解和松弛，然后再进一步采用割平面法和分支定界法来帮助求解。

目前整数规划问题的分解/松弛的主流的方法有如下三种：

1 Benders decomposition (主要思想是行生成+割平面方法)

2 Dantzig-Wolfe decomposition (主要思想其实就是列生成)

3 Lagrangian decomposition (主要思想是 Lagrangian relaxation)

我们今天主要介绍的是 Lagrangian relaxation 方法，前两种方法我们会在后续笔记中进行更新。

1 拉格朗松弛中三问题（原问题，松弛问题，对偶问题）的关系

1.1 原问题

考虑如下线性整数规划问题：

约束（1.1） Dx≤d 可以看做是“难处理”的约束，约束（1.3）中 Ax≤b 可以看出是“容易处理”的约束。关于怎么具体定义啥是“难处理”约束，啥是“容易处理”约束我们会在第三节详细讨论这个问题。

1.2 松弛问题

由于在上述问题中约束（1.1）比较难处理，我们自然希望能把这个约束转化到目标函数上去可能会让问题变得简单一些，因此我们定义乘子 u=(u1,u2,...,um)∈Rm+ ，然后可得

我们把上面这个问题称之为松弛问题， u 称为拉格朗日乘子， z(u) 为对偶函数。

这里边要注意两点：一是拉格朗日乘子 u 是一个向量，它的维数和被松弛掉的约束的数量是一样的，而且拉格朗日乘子 u的符号是和被松弛约束相关的。如果被松弛约束是小于等于，那就需要拉格朗日乘子大于等于0，例如在本例子中约束（1.1）就是小于等于号，所以需要 u∈Rm+ 。如果被松弛约束是等于号，那就表明拉格朗日乘子不需要收到约束限制，即 u∈Rm 。

1.3 对偶问题

需要注意的是 z(u) 称之为对偶函数，它确实是一个函数，函数的输入为拉格朗日乘子，输出是（1.4）-（1.5）松弛问题的最优值。也就是说对偶函数是一个稍微特殊一点的函数，它的输入输出映射关系是由松弛问题（1.4）-（1.5）来决定的，每给一个 u 我就可以带入到松弛问题（1.4）-（1.5）去求解得到一个 z(u) 。进一步我们最大化对偶函数 z(u) 可以得到对偶问题：

对偶问题中是对 u 求极大化，就是在松弛问题的基础上找一个能使得 z(u) 变得最大的那个 u ，这个就是对偶问题的意义。

1.4 三个问题之间的关系

到这里我们梳理一下已经定义的三个问题，1原问题（1.1-1.3）；2松弛问题（1.4-1.5）；3对偶问题（1.6）。接下来我们就要简单分析下这个新得到的对偶问题和原问题到底是一个什么关系。那描述它们关系的定理就是弱对偶定理。

设原问题（P）为：

其对偶问题（D）为：

这样就得到了我们弱对偶定理的结论：

松弛问题是原问题的一个下界，而对偶问题是原问题最大的那个下界。

强对偶定理我们就不介绍了，因为绝大多数整数规划问题都是不满足强对偶定理的，所以我们基本就默认在面对整数规划问题的时候强对偶是很难成立的，只能保证弱对偶性。

2 为什么要用拉格朗日松弛？

1 拉格朗日松弛之后得到的问题下界要 大于等于 直接将0,1整数变量松弛为[0,1]连续变量的下界。一言以蔽之就是 拉格朗松弛得到的解的质量要好。

2 如果问题具有linked/coupling constraints那么采用拉格朗日松弛之后可以使得问题被分解，进而可以让问题的计算复杂度大大降低。

3 采用拉格朗日松弛之后我们会得到拉格朗日乘子，拉格朗日乘子反应了对偶的信息，那么用这个这个对偶信息可以做很多很多的事情。

总结起来这三条就是：1拉格朗日松弛解的质量高；2拉格朗日松弛解的速度快；3拉格朗日松弛提供了对偶的信息可以方便干其它的一些事情。

第二条性质一般是显然的，第三条性质要根据实际问题去考量。那么本节着重论证最难说明的第一条：拉格朗日松弛解的质量高。考虑如下线性整数规划问题：

将其中的整数约束松弛为连续约束可得：

针对原问题（2.1-2.3）采用拉格朗日松弛，松弛掉约束（2.1），可得如下的对偶问题：

我们接下来就是论证拉格朗日松弛的对偶问题（2.7-2.8）的解要优于 直接连续松弛的问题（2.4-2.6）。

显然在式（2.7-2.8）中一个max套着min就显得比较复杂，我们接下来就致力于把里边的min消去。首先由于约束集合 X 是一个只包含整数点的集合，我们假设其中包含有 N 个整数点，分别为 {x1,...,xN} ，接着我们将上式改写为如下表达式：

从（2.9）到（2.10）是因为这是一个整数规划问题，只需要穷举所有可行的整数点即可。从（2.10）到（2.11-2.13）是用到优化问题等价性一个原理：极大化最小值就是极大化下界。最终整理可得问题（2.11-2.13），易知（2.11-2.13）是一个线性规划问题，我们将（2.11-2.13）构成的线性规划问题转化对偶问题（如何得到线性规划对偶请查阅线性规划相关教材 这里不再赘述）可得：

其中 π 为对偶变量。令:

我们可以知道：

其中 Conv 表示凸包。

带入到上面的线性规划对偶问题重新整理可得：

由于(2.11-2.13)是一个线性规划问题满足强对偶定理，所以其和对偶问题(2.17-2.19)是完全等价的。这里我们要记住 X={0,1}，n 是一个整数点构成的集合，大多数情况下对于整数集合点的凸包也是很难计算出来的。

如果我们进一步将整数集合 x∈Zn 松弛为 x∈Rn ，那么整理可得（注意这个转化会扩大可行域的范围并不等价）

由于从（2.17-2.19）转化到（2.20-2.22）我们直接是把 x∈Zn 松弛为 x∈Rn 是直接扩大了可行域的。观察到式（2.22）此时凸包里边的元素本身已经是凸集了，所以凸包运算已经不起作用了，进一步把凸包去掉，可得到到等价的优化问题：

不难发现问题（2.23-2.26）就是我们最开始提到的连续松弛的问题 (2.4-2.6)。

所以综上所述可得定理2.1：

优化问题（2.20-2.22） = 连续松弛问题（2.4-2.6）≤ 优化问题（2.17-2.19） = 拉格朗日松弛对偶问题（2.7-2.8） ≤ 原问题（2.1-2.3）

简单总结一下以上结论成立的原因：

第一个等号成立是因为 优化问题（2.20-2.22）等价于优化问题（2.23-2.26）并且等价于连续松弛问题。

第二个小于等于号成立是因为 从优化问题（2.17-2.19）到优化问题（2.20-2.22）我们把 x∈Zn 松弛为 x∈Rn

第三个小于等于号成立是因为 弱对偶定理，这个我们上一节已经说明过了。

3 选择松弛哪个约束（以广义指派问题为例）

在拉格朗日松弛方法中比较重要的一点是松弛哪个约束？在第一节刚开始我们也提到了“难处理”的约束和“容易处理”的约束。我们是松弛掉了“容易处理”的约束而保留下了“难处理”约束。但是遇到实际问题中并没有办法量化去定义什么是“难处理”，什么是“容易处理”，所以选择哪个约束并没有一成不变的方法，大致会基于以下几个因素去 trade off ：

1 拉格朗日松弛之后对偶问题解的质量的好坏。

2 拉格朗日松弛的松弛问题后的子问题求解难易程度。

3 拉格朗日松弛对偶问题求解难易程度。

针对第1点拉格朗日松弛解的质量的好坏可以使用定理2.1来评价，而针对2,3两点需要根据具体问题来具体确定。我们以广义指派问题为例来说明：

观察广义指派问题的约束，广义指派问题含有两大类主要的约束（3.2）和（3.3）。如果分别松弛约束（3.2）和（3.3）就可以得到两种不同的松弛方法。

松弛方法1（松弛3.2约束）：

进一步整理可得：

观察上式发现可以实现松弛问题的分解 ：

其中 zi(u) 为：

也就是说原始的松弛问题 Z1(u) 被拆分为 N 个子问题 zi(u) ，观察上式不难发现每个子问题zi(u)实际上就是一个背包问题。也就是说求解松弛问题我们需要求解 N 个背包问题即可。由于背包问题本身是NP-hard的，所以该松弛问题的求解是NP-hard的。

接下来我们套用定理2.1来评价该松弛问题解的质量：

由上式可知松弛方法1的质量要优于直接对原问题做连续松弛。

松弛方法2（松弛3.3约束）：

进一步整理可得：

观察上式发现可以实现松弛问题的分解：

其中 zi(v) 为

上述问题求解非常简单可以用如下表达式得到：

上式本质上就是在 M 个数中找出最小的那个，所以算法复杂度为 O(N) ，又因为要求解 N 次，合并起来可得松弛问题 Z2(v)求解的算法复杂度为 O(NM)

接下来我们套用结论1来评价该松弛问题的质量可得：

由上式可知松弛方法2的质量等于直接对原问题做连续松弛。

对比松弛方式1和松弛方式2可得下表：

	松弛方式1	松弛方式2
松弛解的质量	较好	较差
松弛问题求解难度	较难（是背包问题）	较易（M个数找最小的问题）
对偶问题求解难度	相同	相同

由此可见，松弛方式1得到的解的质量是比较好的，但是其松弛问题的求解本身要稍微困难一点，而松弛方式2得到的解的质量和原来采用连续松弛对比没有任何提升，但是其松弛问题的求解比较容易。总体来说 No free lunch，面对具体问题如何选取要松弛的约束是一门艺术，并不存在一个统一的法门。如何做取舍，如何去trade off 这是我们做算法设计的人需要根据具体问题具体情况去认真考虑的问题。

4 拉格朗日松弛求解广义指派问题代码

好了到这里我们已经基本解决了拉格朗日松弛的理论方面的分析，本节将侧重算法实现，将会以广义指派问题为例采用拉格朗日松弛来求解广义指派问题。我们以广义指派问题中的松弛方法1为例给出拉格朗日松弛算法的基本流程为：

Step 1: 初始化乘子 u∈Rn

Step 2: 求解松弛问题（3.5-3.7）

Step 3: 采用次梯度法更新拉格朗日乘子 u∈Rn ，并判断是否满足停止条件，若满足则跳到Step2，若不满足则跳转到Step 2继续。

将以上过程画图形象表达就是一个迭代的过程（如下图所示），先求解松弛问题更新 x ，然后用次梯度法更新乘子 u，如此往复不停，直至若干次之后达到收敛。 需要注意的是在第 k 步迭代的时候，求解松弛问题的时候， x 是决策变量， u 是常数，那么 u 的值采用上一步迭代值即可。同理，更新次梯度的时候， u 又变成了变量，而 x 当做是常数，那么 x 的值采用上一步迭代值即可。

我们这里以上一节中的广义指派问题为例，在 python 环境中实现拉格朗日松弛对广义指派问题进行求解，松弛方式采用的是方式1。首先采用了 pyomo 生成我们的优化数学模型，如下所示：

model = ConcreteModel()

model.M, model.N = Set(initialize=range(n_agent)), Set(initialize=range(n_job))

model.c, model.a = Param(model.M, model.N, initialize = init_c), Param(model.M, model.N, initialize = init_a)

model.capacity = Param(model.M, initialize = capacity)

model.x = Var(model.M, model.N, within = Binary)

model.constrs1 = Constraint(model.M, rule = capacity_rule)

model.constrs2 = Constraint(model.N, rule = one_rule)

接下来就是松弛掉约束，我们用model.u表示乘子，接着松弛掉约束，然后将松弛的约束转化到目标函数上构成新的目标函数。最后我们求解松弛问题是会用到gurobi的。

model.u = Param(model.N, initialize = 0.0, mutable=True)

lagrangian_relaxation = Relaxation()

lagrangian_relaxation.relax_constrs(relaxed_constrs=model.constrs2)

lagrangian_relaxation.set_objective(model, relaxed_obj_rule)

solver = SolverFactory("gurobi", solver_io = "python")

创建对偶问题duality_model，然后采用迭代算法来求解。

u = np.ones(len(model.constrs2))

duality_model = Duality(u_init = u)

max_iter = 200 # 最大迭代次数

for k in range(max_iter):

    set_u(model, u)  # 将乘子u传递给松弛问题

    solution = solver.solve(model) # 调用gurobi求解松弛问题

    duality_model.get_subgrad(relaxed_model = model) # 获得对偶问题的次梯度

    duality_model.get_step_size() # 计算步长

    u = duality_model.update() # 更新乘子

    duality_model.print_status(k, max_iter) # 打印一些中间求解过程

参考文献：

[1] 孙小玲，李端，整数规划，科学出版社，2010

[2] Laurence A. Wolsey, Integer Programming, Wily, 2021

[3] Bragin M A, Luh P B, Yan J H, et al. Convergence of the Surrogate Lagrangian Relaxation Method[J]. Journal of Optimization Theory and Applications, 2015, 164(1): 173-201.

---

转载自知乎文章《【整数规划(七)】整数规划的拉格朗日松弛（理论分析+Python代码实现）》，作者 王源

 

面对大规模整数规划/混合整数规划，往往直接采用割平面法和分支定界法求解是不现实的，这时候就需要对大规模整数规划/混合整数规划问题先进行分解和松弛，然后再进一步采用割平面法和分支定界法来帮助求解。

目前整数规划问题的分解/松弛的主流的方法有如下三种：

1 Benders decomposition (主要思想是行生成+割平面方法)

2 Dantzig-Wolfe decomposition (主要思想其实就是列生成)

3 Lagrangian decomposition (主要思想是 Lagrangian relaxation)

我们今天主要介绍的是 Lagrangian relaxation 方法，前两种方法我们会在后续笔记中进行更新。

1 拉格朗松弛中三问题（原问题，松弛问题，对偶问题）的关系

1.1 原问题

考虑如下线性整数规划问题：

约束（1.1） Dx≤d 可以看做是“难处理”的约束，约束（1.3）中 Ax≤b 可以看出是“容易处理”的约束。关于怎么具体定义啥是“难处理”约束，啥是“容易处理”约束我们会在第三节详细讨论这个问题。

1.2 松弛问题

由于在上述问题中约束（1.1）比较难处理，我们自然希望能把这个约束转化到目标函数上去可能会让问题变得简单一些，因此我们定义乘子 u=(u1,u2,...,um)∈Rm+ ，然后可得

我们把上面这个问题称之为松弛问题， u 称为拉格朗日乘子， z(u) 为对偶函数。

这里边要注意两点：一是拉格朗日乘子 u 是一个向量，它的维数和被松弛掉的约束的数量是一样的，而且拉格朗日乘子 u的符号是和被松弛约束相关的。如果被松弛约束是小于等于，那就需要拉格朗日乘子大于等于0，例如在本例子中约束（1.1）就是小于等于号，所以需要 u∈Rm+ 。如果被松弛约束是等于号，那就表明拉格朗日乘子不需要收到约束限制，即 u∈Rm 。

1.3 对偶问题

需要注意的是 z(u) 称之为对偶函数，它确实是一个函数，函数的输入为拉格朗日乘子，输出是（1.4）-（1.5）松弛问题的最优值。也就是说对偶函数是一个稍微特殊一点的函数，它的输入输出映射关系是由松弛问题（1.4）-（1.5）来决定的，每给一个 u 我就可以带入到松弛问题（1.4）-（1.5）去求解得到一个 z(u) 。进一步我们最大化对偶函数 z(u) 可以得到对偶问题：

对偶问题中是对 u 求极大化，就是在松弛问题的基础上找一个能使得 z(u) 变得最大的那个 u ，这个就是对偶问题的意义。

1.4 三个问题之间的关系

到这里我们梳理一下已经定义的三个问题，1原问题（1.1-1.3）；2松弛问题（1.4-1.5）；3对偶问题（1.6）。接下来我们就要简单分析下这个新得到的对偶问题和原问题到底是一个什么关系。那描述它们关系的定理就是弱对偶定理。

设原问题（P）为：

其对偶问题（D）为：

这样就得到了我们弱对偶定理的结论：

松弛问题是原问题的一个下界，而对偶问题是原问题最大的那个下界。

强对偶定理我们就不介绍了，因为绝大多数整数规划问题都是不满足强对偶定理的，所以我们基本就默认在面对整数规划问题的时候强对偶是很难成立的，只能保证弱对偶性。

2 为什么要用拉格朗日松弛？

1 拉格朗日松弛之后得到的问题下界要 大于等于 直接将0,1整数变量松弛为[0,1]连续变量的下界。一言以蔽之就是 拉格朗松弛得到的解的质量要好。

2 如果问题具有linked/coupling constraints那么采用拉格朗日松弛之后可以使得问题被分解，进而可以让问题的计算复杂度大大降低。

3 采用拉格朗日松弛之后我们会得到拉格朗日乘子，拉格朗日乘子反应了对偶的信息，那么用这个这个对偶信息可以做很多很多的事情。

总结起来这三条就是：1拉格朗日松弛解的质量高；2拉格朗日松弛解的速度快；3拉格朗日松弛提供了对偶的信息可以方便干其它的一些事情。

第二条性质一般是显然的，第三条性质要根据实际问题去考量。那么本节着重论证最难说明的第一条：拉格朗日松弛解的质量高。考虑如下线性整数规划问题：

将其中的整数约束松弛为连续约束可得：

针对原问题（2.1-2.3）采用拉格朗日松弛，松弛掉约束（2.1），可得如下的对偶问题：

我们接下来就是论证拉格朗日松弛的对偶问题（2.7-2.8）的解要优于 直接连续松弛的问题（2.4-2.6）。

显然在式（2.7-2.8）中一个max套着min就显得比较复杂，我们接下来就致力于把里边的min消去。首先由于约束集合 X 是一个只包含整数点的集合，我们假设其中包含有 N 个整数点，分别为 {x1,...,xN} ，接着我们将上式改写为如下表达式：

从（2.9）到（2.10）是因为这是一个整数规划问题，只需要穷举所有可行的整数点即可。从（2.10）到（2.11-2.13）是用到优化问题等价性一个原理：极大化最小值就是极大化下界。最终整理可得问题（2.11-2.13），易知（2.11-2.13）是一个线性规划问题，我们将（2.11-2.13）构成的线性规划问题转化对偶问题（如何得到线性规划对偶请查阅线性规划相关教材 这里不再赘述）可得：

其中 π 为对偶变量。令:

我们可以知道：

其中 Conv 表示凸包。

带入到上面的线性规划对偶问题重新整理可得：

由于(2.11-2.13)是一个线性规划问题满足强对偶定理，所以其和对偶问题(2.17-2.19)是完全等价的。这里我们要记住 X={0,1}，n 是一个整数点构成的集合，大多数情况下对于整数集合点的凸包也是很难计算出来的。

如果我们进一步将整数集合 x∈Zn 松弛为 x∈Rn ，那么整理可得（注意这个转化会扩大可行域的范围并不等价）

由于从（2.17-2.19）转化到（2.20-2.22）我们直接是把 x∈Zn 松弛为 x∈Rn 是直接扩大了可行域的。观察到式（2.22）此时凸包里边的元素本身已经是凸集了，所以凸包运算已经不起作用了，进一步把凸包去掉，可得到到等价的优化问题：

不难发现问题（2.23-2.26）就是我们最开始提到的连续松弛的问题 (2.4-2.6)。

所以综上所述可得定理2.1：

优化问题（2.20-2.22） = 连续松弛问题（2.4-2.6）≤ 优化问题（2.17-2.19） = 拉格朗日松弛对偶问题（2.7-2.8） ≤ 原问题（2.1-2.3）

简单总结一下以上结论成立的原因：

第一个等号成立是因为 优化问题（2.20-2.22）等价于优化问题（2.23-2.26）并且等价于连续松弛问题。

第二个小于等于号成立是因为 从优化问题（2.17-2.19）到优化问题（2.20-2.22）我们把 x∈Zn 松弛为 x∈Rn

第三个小于等于号成立是因为 弱对偶定理，这个我们上一节已经说明过了。

3 选择松弛哪个约束（以广义指派问题为例）

在拉格朗日松弛方法中比较重要的一点是松弛哪个约束？在第一节刚开始我们也提到了“难处理”的约束和“容易处理”的约束。我们是松弛掉了“容易处理”的约束而保留下了“难处理”约束。但是遇到实际问题中并没有办法量化去定义什么是“难处理”，什么是“容易处理”，所以选择哪个约束并没有一成不变的方法，大致会基于以下几个因素去 trade off ：

1 拉格朗日松弛之后对偶问题解的质量的好坏。

2 拉格朗日松弛的松弛问题后的子问题求解难易程度。

3 拉格朗日松弛对偶问题求解难易程度。

针对第1点拉格朗日松弛解的质量的好坏可以使用定理2.1来评价，而针对2,3两点需要根据具体问题来具体确定。我们以广义指派问题为例来说明：

观察广义指派问题的约束，广义指派问题含有两大类主要的约束（3.2）和（3.3）。如果分别松弛约束（3.2）和（3.3）就可以得到两种不同的松弛方法。

松弛方法1（松弛3.2约束）：

进一步整理可得：

观察上式发现可以实现松弛问题的分解 ：

其中 zi(u) 为：

也就是说原始的松弛问题 Z1(u) 被拆分为 N 个子问题 zi(u) ，观察上式不难发现每个子问题zi(u)实际上就是一个背包问题。也就是说求解松弛问题我们需要求解 N 个背包问题即可。由于背包问题本身是NP-hard的，所以该松弛问题的求解是NP-hard的。

接下来我们套用定理2.1来评价该松弛问题解的质量：

由上式可知松弛方法1的质量要优于直接对原问题做连续松弛。

松弛方法2（松弛3.3约束）：

进一步整理可得：

观察上式发现可以实现松弛问题的分解：

其中 zi(v) 为

上述问题求解非常简单可以用如下表达式得到：

上式本质上就是在 M 个数中找出最小的那个，所以算法复杂度为 O(N) ，又因为要求解 N 次，合并起来可得松弛问题 Z2(v)求解的算法复杂度为 O(NM)

接下来我们套用结论1来评价该松弛问题的质量可得：

由上式可知松弛方法2的质量等于直接对原问题做连续松弛。

对比松弛方式1和松弛方式2可得下表：

	松弛方式1	松弛方式2
松弛解的质量	较好	较差
松弛问题求解难度	较难（是背包问题）	较易（M个数找最小的问题）
对偶问题求解难度	相同	相同

由此可见，松弛方式1得到的解的质量是比较好的，但是其松弛问题的求解本身要稍微困难一点，而松弛方式2得到的解的质量和原来采用连续松弛对比没有任何提升，但是其松弛问题的求解比较容易。总体来说 No free lunch，面对具体问题如何选取要松弛的约束是一门艺术，并不存在一个统一的法门。如何做取舍，如何去trade off 这是我们做算法设计的人需要根据具体问题具体情况去认真考虑的问题。

4 拉格朗日松弛求解广义指派问题代码

好了到这里我们已经基本解决了拉格朗日松弛的理论方面的分析，本节将侧重算法实现，将会以广义指派问题为例采用拉格朗日松弛来求解广义指派问题。我们以广义指派问题中的松弛方法1为例给出拉格朗日松弛算法的基本流程为：

Step 1: 初始化乘子 u∈Rn

Step 2: 求解松弛问题（3.5-3.7）

Step 3: 采用次梯度法更新拉格朗日乘子 u∈Rn ，并判断是否满足停止条件，若满足则跳到Step2，若不满足则跳转到Step 2继续。

将以上过程画图形象表达就是一个迭代的过程（如下图所示），先求解松弛问题更新 x ，然后用次梯度法更新乘子 u，如此往复不停，直至若干次之后达到收敛。 需要注意的是在第 k 步迭代的时候，求解松弛问题的时候， x 是决策变量， u 是常数，那么 u 的值采用上一步迭代值即可。同理，更新次梯度的时候， u 又变成了变量，而 x 当做是常数，那么 x 的值采用上一步迭代值即可。

我们这里以上一节中的广义指派问题为例，在 python 环境中实现拉格朗日松弛对广义指派问题进行求解，松弛方式采用的是方式1。首先采用了 pyomo 生成我们的优化数学模型，如下所示：

model = ConcreteModel()

model.M, model.N = Set(initialize=range(n_agent)), Set(initialize=range(n_job))

model.c, model.a = Param(model.M, model.N, initialize = init_c), Param(model.M, model.N, initialize = init_a)

model.capacity = Param(model.M, initialize = capacity)

model.x = Var(model.M, model.N, within = Binary)

model.constrs1 = Constraint(model.M, rule = capacity_rule)

model.constrs2 = Constraint(model.N, rule = one_rule)

接下来就是松弛掉约束，我们用model.u表示乘子，接着松弛掉约束，然后将松弛的约束转化到目标函数上构成新的目标函数。最后我们求解松弛问题是会用到gurobi的。

model.u = Param(model.N, initialize = 0.0, mutable=True)

lagrangian_relaxation = Relaxation()

lagrangian_relaxation.relax_constrs(relaxed_constrs=model.constrs2)

lagrangian_relaxation.set_objective(model, relaxed_obj_rule)

solver = SolverFactory("gurobi", solver_io = "python")

创建对偶问题duality_model，然后采用迭代算法来求解。

u = np.ones(len(model.constrs2))

duality_model = Duality(u_init = u)

max_iter = 200 # 最大迭代次数

for k in range(max_iter):

    set_u(model, u)  # 将乘子u传递给松弛问题

    solution = solver.solve(model) # 调用gurobi求解松弛问题

    duality_model.get_subgrad(relaxed_model = model) # 获得对偶问题的次梯度

    duality_model.get_step_size() # 计算步长

    u = duality_model.update() # 更新乘子

    duality_model.print_status(k, max_iter) # 打印一些中间求解过程

参考文献：

[1] 孙小玲，李端，整数规划，科学出版社，2010

[2] Laurence A. Wolsey, Integer Programming, Wily, 2021

[3] Bragin M A, Luh P B, Yan J H, et al. Convergence of the Surrogate Lagrangian Relaxation Method[J]. Journal of Optimization Theory and Applications, 2015, 164(1): 173-201.

---

转载自知乎文章《【整数规划(七)】整数规划的拉格朗日松弛（理论分析+Python代码实现）》，作者 王源