拉格朗日松弛：当我把约束扔进目标函数之后

去年年初，我参与了一个实际的车间调度项目。

车间里有 15 台机器，50 种不同的工件，每种工件有自己的加工时间、更换模具时间、优先级、交货期。约束条件列出来整整两页 A4 纸：某些工件必须在某些机器上加工；某些工件不能连续加工；模具更换时间在不同机器之间还不一样……

优化目标是尽量减少延迟罚款。听起来就是一个普通的 scheduling 问题，用 MIP 建模，Gurobi 求解，应该不难。

我们花了两周时间把模型建好，Gurobi 一跑——12 个小时没出结果。调参、缩小规模、加启发式规则，折腾了一个月，还是卡在 8 小时超时。

直到团队里一位老工程师说了一句话："试试把某些约束扔进目标函数里。"

那个方法叫拉格朗日松弛。

为什么约束会让求解器变慢

讲拉格朗日松弛之前，先说清楚一个问题：为什么加了约束之后，求解器会变慢？

MIP 求解器的核心是分支定界（Branch & Bound）。它先忽略整数约束，把问题当成连续问题来解，然后逐步分支、剪枝。约束越多、越复杂，线性规划松弛的下界就越紧，但每次迭代的计算量也越大。特别是一堆"耦合约束"（即同时涉及多个决策变量的约束），会让求解器的预处理和割平面生成变得极其耗时。

15台机器 × 50种工件的调度问题，其中有一类约束叫"机器能力约束"——它规定了在同一时间段内，每台机器最多只能加工一个工件。这类约束数量庞大，而且每个都涉及多个变量，导致整个问题变成一个超大规模的组合优化问题。

拉格朗日松弛的基本思想是：与其硬求解带所有约束的问题，不如把部分"麻烦"的约束吸收进目标函数里，给它们配上"惩罚价格"，转成一个更容易求解的无约束或松散约束问题。

拉格朗日松弛的数学原理

标准 MIP 问题的形式是这样的：

min  cᵀx s.t. Ax ≤ b          (硬约束，原问题的一部分)  Bx = d          (硬约束，另一部分)  x ∈ Zⁿ          (整数约束)

拉格朗日松弛的做法是：选择一组"麻烦"的约束（比如 Bx = d），把它们乘上一个拉格朗日乘子 λ，乘进去目标函数：

LR(λ) = min cᵀx + λᵀ(Bx - d) s.t.  Ax ≤ b  x ∈ Zⁿ

注意，现在问题里已经没有 Bx = d 这个约束了！它被"松弛"掉了，变成了目标函数里的一项——如果解满足 Bx = d，这一项为 0；如果不满足，就会有一个惩罚。

但惩罚价格 λ 是多少？这才是关键。

λ 的选择决定了你松弛后问题的质量。太大会过度惩罚，导致解偏离原问题；太小又不足以引导解接近可行域。拉格朗日松弛的核心任务是找最优的 λ，使得 LR(λ) 给出原问题的最好下界（对于最小化问题）。

找最优 λ 的过程叫次梯度优化（Subgradient Optimization），核心迭代：

import numpy as np  def lagrangian_relaxation(c, A, b, B, d, x_init=None, max_iter=500, step_size=0.01):  """  拉格朗日松弛算法  c: 目标函数系数  A: 保留的硬约束矩阵  b: 保留的硬约束上界  B: 要松弛的约束矩阵  d: 要松弛的约束右端项    返回：最优下界、最优解、对偶变量 λ  """  n = len(c)  # 变量个数  lambda_k = np.zeros(len(d))  # 初始拉格朗日乘子  best_bound = -np.inf  best_x = None    x = x_init if x_init is not None else np.zeros(n)    for k in range(max_iter):  modified_c = c + B.T @ lambda_k  x_star = solve_lagrangian_subproblem(modified_c, A, b)    primal_obj = c @ x_star  violation = B @ x_star - d  # 约束违反量  lr_value = primal_obj + lambda_k @ violation    if lr_value > best_bound:  best_bound = lr_value  best_x = x_star.copy()    subgradient = violation    step = step_size / np.sqrt(k + 1)    lambda_k = lambda_k + step * subgradient  lambda_k = np.maximum(lambda_k, 0)  # 对偶变量非负    return best_bound, best_x, lambda_k   def solve_lagrangian_subproblem(c_mod, A, b):  """  求解拉格朗日松弛子问题  这里用分支定界框架，但问题规模比原问题小得多  """  from scipy.optimize import milp, LinearConstraint, Bounds    constraints = LinearConstraint(A, -np.inf, b)  bounds = Bounds(0, np.inf)    integrality = np.ones(len(c_mod))  # 所有变量都是整数    result = milp(c_mod, constraints=constraints, bounds=bounds,   integrality=integrality)  return result.x

这段代码演示了拉格朗日松弛的核心循环：固定 λ 求解子问题 → 计算下界 → 更新乘子 → 重复。每一步的计算量都比原问题小得多，因为约束减少了。

实际项目中的松弛策略

回到车间调度项目。我们分析了所有约束之后，发现有两类约束最难处理：

第一类：机器能力约束（每个时间段每台机器只能加工一个工件） 第二类：工件顺序约束（某些工件必须在另一些工件之前完成）

我们把第一类约束做了拉格朗日松弛——每台机器在每个时间段只能加工一个工件，这个约束涉及 15台 × 24个时间段 = 360 个约束，而且每个都耦合了 50 种工件的选择变量，是导致 MIP 规模爆炸的元凶。

松弛之后的子问题可以分解：每台机器独立求解自己的最优排产，因为机器之间没有耦合了！这就把一个 15×50 的联合优化问题分解成了 15 个独立的单机调度子问题。

class LagrangianDecomposedScheduler:  def __init__(self, machines, jobs, lambda_multipliers):  self.machines = machines  # 15台机器  self.jobs = jobs           # 50种工件  self.lambda_mult = lambda_multipliers  # 每台机器每个时间段的惩罚价格    def solve_machine(self, machine_id):  """  每台机器独立求解自己的排产问题  这个子问题规模：50种工件 × 24个时间段  Gurobi 求解时间：< 1秒  """  from gurobipy import Model, GRB, quicksum    m = Model(f"Machine_{machine_id}")  jobs = self.jobs    x = m.addVars(len(jobs), len(jobs), vtype=GRB.BINARY, name="x")    obj = quicksum(jobs[j].processing_cost * x[j, t]   for j in range(len(jobs)) for t in range(len(jobs)))  penalty = quicksum(  self.lambda_mult[machine_id][t] * x[j, t]  # 违反"同时只能一个"的惩罚  for j in range(len(jobs)) for t in range(len(jobs))  )  m.setObjective(obj + penalty, GRB.MINIMIZE)    m.addConstrs((quicksum(x[j, t] for t in range(len(jobs))) == 1   for j in range(len(jobs))), "one_per_job")    m.optimize()  return m.getAttr('X', x)    def solve_all(self):  """15台机器并行求解，总时间从8小时降到约2分钟"""  import concurrent.futures    results = {}  with concurrent.futures.ThreadPoolExecutor(max_workers=15) as executor:  futures = {executor.submit(self.solve_machine, mid): mid   for mid in range(len(self.machines))}  for future in concurrent.futures.as_completed(futures):  mid = futures[future]  results[mid] = future.result()  return results

把原来耦合的 360 个约束松弛掉之后，15 台机器可以并行求解自己的子问题。原来卡 8 小时的 MIP，变成了每台机器 < 1 秒的小问题。整体求解时间从 8 小时降到了 2 分钟。

松弛解怎么用：下界与可行解

拉格朗日松弛给出的不是原问题的可行解，而是一个下界（对于最小化问题）。真正能被生产使用的解，还需要从松弛解出发构造可行解，或者用启发式方法把松弛解"拉回"可行域。

有两个常用策略：

策略1：梯度下降 + 修复启发式 用拉格朗日乘子 λ 求出的解 x*，如果违反约束不严重，用贪心策略修复。比如松弛解里同一时间段排了两个工件到同一台机器，就保留优先级高的，延迟优先级低的。

策略2：次梯度优化里的"最佳可行解"追踪 在迭代过程中，每次更新 λ 时同时检查 x* 是否违反约束。如果违反量在可接受范围内，就记录为候选可行解。最终从这些候选里选最优的。

def repair_solution(x_star, B, d, max_violation=0.1):  """贪心修复：将违反约束的解转化为可行解"""  x_repaired = x_star.copy()  violation = B @ x_repaired - d    most_violated = np.argmax(violation)  while violation[most_violated] > max_violation:  violated_vars = np.where(B[most_violated] * x_repaired > 0)[0]  x_repaired[violated_vars[0]] = 0  # 简单粗暴：把第一个清零  violation = B @ x_repaired - d  most_violated = np.argmax(violation)    return x_repaired

松弛哪些约束：经验法则

不是所有约束都适合松弛。选错了约束，结果会适得其反。以下是经验法则：

适合松弛的约束：

• 数量多、耦合紧，增加求解难度的硬约束
• 松弛后子问题可以分解为独立小问题的
• 违反时惩罚代价容易量化的

不适合松弛的约束：

• 定义可行域核心的约束（松弛后子问题可能无界）
• 惩罚值难以准确设定的
• 违反后成本巨大的（应该保留作为硬约束）

实际项目中，我们通常先做约束重要性分析：把每个约束单独拎出来测试松弛效果，评估其对求解时间的影响和对下界质量的影响。两个指标都高的约束，是松弛的首选目标。

这个项目后来怎么样了

用拉格朗日松弛重做之后，15 台机器的车间调度问题在 2 分钟内得到了一个质量不错的可行解。和原来的 MIP 在 8 小时超时后强制中断的解相比，总延迟罚款只多了约 3.5%。

3.5% 的质量损失，换来 240 倍的速度提升，在实际生产中完全可以接受。而且这个下界本身也在迭代中不断改进，团队最终用它来说服管理层：当前解距离理论最优下界只有不到 2% 的差距，不可能再大幅优化了。

这就是拉格朗日松弛的价值：不是找到完美解，而是找到足够好的解，并且在足够短的时间内找到。 当你的优化问题卡在求解器里跑不出来的时候，把一些约束松掉，可能就是突破口。

测试开发之系统篇-Docker常用操作

了解更多

Python学习杂记

查看原文：拉格朗日松弛：当我把约束扔进目标函数之后

文章来源：

Python学习杂记

扫码关注公众号