组合优化深度指南

关键词速览

关键词	解释
线性规划	目标函数和约束均为线性的优化问题
整数线性规划	变量受限为整数的LP
单纯形法	求解LP的多项式时间算法
割平面法	通过切割平面收紧松弛域
分支定界	系统化枚举搜索树
匈牙利算法	O(n³)求解二分图最大匹配
调度问题	作业与机器的资源分配
约束满足	CSP的求解框架
对偶理论	LP的解的边界理论
单纯形法	求解LP的多项式时间算法

摘要

组合优化是运筹学的核心领域，研究在离散结构上寻找最优解的数学规划方法。本文系统阐述线性规划（LP）、整数线性规划（ILP）的理论基础，介绍割平面法、分支定界法等精确求解技术，并以匈牙利算法和调度问题为例展示经典算法设计。组合优化的思想在人工智能的规划、推理和学习中具有广泛应用，是构建智能系统的基础工具箱。

---

1. 线性规划基础

1.1 LP的标准形式与矩阵表示

线性规划（Linear Programming）研究如下形式的问题：

标准形式：

$$\begin{array}{rl}\min & {\mathbf{c}}^T\mathbf{x}\\ \text{s.t.}& A\mathbf{x}\ge \mathbf{b}\\ & \mathbf{x}\ge 0\end{array}$$

其中：

• $\mathbf{c}\in {\mathbb{R}}^n$：目标函数系数向量
• $A\in {\mathbb{R}}^{m\times n}$：约束矩阵
• $\mathbf{b}\in {\mathbb{R}}^m$：右端向量
• $\mathbf{x}\in {\mathbb{R}}^n$：决策变量

1.2 单纯形法的几何直觉

单纯形法由George Dantzig于1947年提出，利用线性规划可行域的多面体结构：

Note

线性规划的最优解必定出现在多面体的某个顶点（极点）。单纯形法沿着可行方向从一顶点移动到相邻顶点，逐步优化目标值。

基本可行解（BFS）的定义： 对于 $m\times n$ 的约束矩阵，选择 $n$ 列构成基矩阵 $B$，则

$${\mathbf{x}}_B=B^{-1}\mathbf{b},{\mathbf{x}}_N=0$$

是基本可行解当且仅当 $B^{-1}\mathbf{b}\ge 0$。

1.3 单纯形法的迭代过程

def simplex(A, b, c):
    # 初始化：找到初始BFS或使用两阶段法
    
    while True:
        # 计算检验数（reduced costs）
        for each non-basic variable x_j:
            if reduced_cost[j] < 0:
                # 可以改善目标值，选择最负的检验数
                entering = j
                break
        
        if all reduced_cost >= 0:
            return current_solution  # 最优解
        
        # 判别比（最小比例测试）
        for each basic variable x_i:
            if A[:, entering] > 0:
                ratio = b[i] / A[i, entering]
                if ratio < min_ratio:
                    leaving = i
        
        # 基变换
        swap(entering, leaving)

单纯形法的时间复杂度：

• 理论上：指数时间（Klee-Minty立方体可达）
• 实践中：多项式时间（平滑分析 $O(m^{3}n)$）

1.4 对偶理论

每个LP问题都有一个对偶问题：

原问题（Primal）：

$$\begin{array}{rl}\max & {\mathbf{b}}^T\mathbf{y}\\ \text{s.t.}& A^T\mathbf{y}\le \mathbf{c}\\ & \mathbf{y}\ge 0\end{array}$$

对偶定理（Duality Theorem）：

• 弱对偶：若 $\mathbf{x}$ 可行，$\mathbf{y}$ 可行，则 ${\mathbf{c}}^T\mathbf{x}\le {\mathbf{b}}^T\mathbf{y}$
• 强对偶：若原问题有最优解，则对偶问题也有最优解，且目标值相等
• 最优性条件：${\mathbf{c}}^T{\mathbf{x}}^{\ast }={\mathbf{b}}^T{\mathbf{y}}^{\ast }$

Example

运输问题的对偶解释：$\mathbf{y}$ 可以看作各地点的”势”，约束保证每条弧的利润不超过边际成本。

---

2. 整数线性规划

2.1 ILP的定义与难度

整数线性规划（Integer Linear Programming）要求决策变量取整数值：

$$\begin{array}{rl}\min & {\mathbf{c}}^T\mathbf{x}\\ \text{s.t.}& A\mathbf{x}\ge \mathbf{b}\\ & \mathbf{x}\in {\mathbb{Z}}^n\end{array}$$

关键事实：ILP是NP难的。即使是简单的0-1背包问题或指派问题也是NP难的。

2.2 LP松弛

LP松弛通过移除整数约束得到连续问题：

$$\begin{array}{rl}\min & {\mathbf{c}}^T\mathbf{x}\\ \text{s.t.}& A\mathbf{x}\ge \mathbf{b}\\ & 0\le \mathbf{x}\le 1\end{array}$$

关系：

$$OP{T}_{LP}\le OP{T}_{ILP}$$

LP松弛提供ILP最优解的下界（最小化问题）。

---

3. 割平面法

3.1 Gomory切割的理论基础

割平面法（Cutting Plane Method）由Ralph Gomory于1958年提出，通过逐步添加有效不等式（valid inequalities）收紧松弛域。

Gomory不等式的构造：

对于最优LP表中的第 $i$ 行（基本变量 $x_B$）：

$$x_{B_i}+\sum _{j\in N}{a}_{ij}{x}_j=b_i$$

将系数分离为整数部分和小数部分：

$$x_{B_i}+\sum _{j\in N}\lfloor a_{ij}\rfloor x_j-\sum _{j\in N}\{a_{ij}\}{x}_j=\lfloor b_i\rfloor +\{b_i\}$$

其中 $\{a\}=a-\lfloor a\rfloor$ 表示小数部分。

利用 $x_j\ge 0$ 和 $\{a_{ij}\}<1$，得到Gomory切割：

$$-\sum _{j\in N}\{a_{ij}\}{x}_j\le \{b_i\}$$

或者写作：

$$\sum _{j\in N}\{a_{ij}\}{x}_j\ge \{b_i\}$$

Warning

纯Gomory切割在实践中收敛较慢，通常与其他方法（如分支定界）结合使用。

3.2 割平面法的收敛性

有限收敛性：如果所有切割面在有限步内产生一个整数极点，则算法有限步收敛。

实际策略：

1. 先运行单纯形法得到LP最优解
2. 如果解不整数，继续添加割平面
3. 重复直到解整数或无有效割平面

---

4. 分支定界法

4.1 分支定界的框架

分支定界（Branch and Bound）是求解ILP的经典框架，结合枚举与剪枝：

def branch_and_bound(ILP):
    # 初始化上界（ incumbent solution）
    best_solution = +∞
    best_value = +∞
    
    # 初始化问题栈（待处理子问题）
    problem_stack = [root_ILP]
    
    while problem_stack:
        P = problem_stack.pop()
        
        # 求解LP松弛
        LP_sol = solve_simplex(P.LP_relaxation)
        
        if LP_sol.value >= best_value:
            continue  # 剪枝：下界不优于当前最优
        
        if LP_sol.is_integer():
            # 更新最优解
            best_solution = LP_sol
            best_value = LP_sol.value
            continue
        
        # 分支：选择一个非整数变量 x_j
        j = select_fractional_var(LP_sol)
        
        # 创建两个子问题
        P1 = P + constraint(x_j <= floor(x_j))
        P2 = P + constraint(x_j >= ceil(x_j))
        
        problem_stack.push(P1)
        problem_stack.push(P2)
    
    return best_solution

4.2 关键技术的改进

节点选择策略：

• 深度优先（DFS）：快速到达叶节点，但可能错过好解
• 最佳优先（BFS）：总是选择最小下界节点，接近最优
• 混合策略：结合两者

变量选择策略：

• 最_fractional变量：选择小数部分最接近0.5的变量
• 最大影响变量：选择系数对目标函数影响最大的变量

割平面加速： 在每个节点添加Gomory切割加速收敛（分支切割框架）。

4.3 下界估计：拉格朗日松弛

对于难以处理的约束，将惩罚项加入目标函数：

$$L(\lambda )=\underset{x\in S}{\min }\{c^{T}x+{\lambda }^T(b-Ax)\}$$

拉格朗日下界：$L(\lambda )$ 对所有 $\lambda \ge 0$ 成立。通过次梯度优化最大化 $L(\lambda )$ 得到最优下界。

---

5. 匈牙利算法：二分图匹配

5.1 问题定义

匈牙利算法（Hungarian Algorithm）由Harold Kuhn于1955年提出，用于求解二分图的最大权完美匹配问题：

形式化：

$$\begin{array}{rl}\max & \sum _{i,j}{w}_{ij}{x}_{ij}\\ \text{s.t.}& \sum _j{x}_{ij}=1,\forall i\\ & \sum _i{x}_{ij}=1,\forall j\\ & x_{ij}\in \{0,1\}\end{array}$$

5.2 算法实现

def hungarian(cost_matrix):
    n = len(cost_matrix)
    
    # Step 1: 行归约（每行减去最小值）
    for i in range(n):
        min_val = min(row)
        cost_matrix[i] -= min_val
    
    # Step 2: 列归约（每列减去最小值）
    for j in range(n):
        min_val = min(row[j] for row in cost_matrix)
        for i in range(n):
            cost_matrix[i][j] -= min_val
    
    # Step 3: 覆盖所有零元素的最少直线数
    while True:
        row_cover, col_cover = find_min_vertex_cover(cost_matrix)
        
        if len(row_cover) + len(col_cover) == n:
            # 找到完美匹配
            break
        
        # Step 4: 调整矩阵
        min_uncovered = find_min_uncovered(cost_matrix)
        for i in range(n):
            for j in range(n):
                if i in row_cover and j not in col_cover:
                    cost_matrix[i][j] -= min_uncovered
                elif i not in row_cover and j in col_cover:
                    cost_matrix[i][j] += min_uncovered
        
    return extract_matching(cost_matrix)

时间复杂度：$O(n^3)$，其中 $n$ 为矩阵维度。

5.3 正确性证明框架

引理1：行归约和列归约不改变任何完美匹配之间的相对权重差。

引理2：如果覆盖零元素的最小直线数等于 $n$，则零元素对应的边构成一个完美匹配，其权重等于行归约和列归约减少的总量，因此是最优匹配。

引理3：Step 4的矩阵调整保持所有完美匹配的相对权重，并创造新的零元素以推进算法。

---

6. 调度问题与约束满足

6.1 调度问题的分类

调度问题（Scheduling）将作业分配到时间资源和机器资源上：

问题类型	约束	目标
单机调度	作业有处理时间、截止时间	最小化迟到作业数
并行机调度	$m$ 台等价机器	最小化makespan
作业车间	每作业有工序顺序	最小化总完工时间
开放车间	工序无顺序约束	最小化makespan

6.2 P||C_max问题：多台平行机器的调度

问题：$n$ 个作业，$m$ 台平行机器，每作业处理时间 $p_j$，目标是最小化最大完工时间（makespan）$C_{\max }$。

下界：

$$LB=\max \left\{\underset{j}{\max }{p}_j,\frac{1}{m}\sum _j{p}_j\right\}$$

LPT（Longest Processing Time）算法：

1. 按处理时间降序排列作业：$p_1\ge p_2\ge ...\ge p_n$
2. 依次分配到当前负载最小的机器

LPT的近似比：$\frac{4}{3}-\frac{1}{3m}$（对任意 $m\ge 2$）

6.3 约束满足问题（CSP）

约束满足问题（Constraint Satisfaction Problem）是调度和资源配置的统一框架：

形式化：

• 变量集合 $X=\{x_1,...,x_n\}$
• 域集合 $D=\{D_1,...,D_n\}$
• 约束集合 $C=\{c_1,...,c_m\}$

求解方法：

def backtrack_search(CSP):
    if all_variables_assigned():
        return current_assignment  # 成功
    
    var = select_unassigned_variable()
    
    for value in order_domain_values(var):
        if is_consistent(var, value):
            assign(var, value)
            
            # 前向检验
            if forward_checking():
                result = backtrack_search(CSP)
                if result:
                    return result
            
            unassign(var, value)
    
    return None  # 失败回溯

弧一致性（AC-3）算法： 对于二元CSP，消除违反弧一致性的值：

$$\forall (x_i,x_j)\in C:\forall a\in D_i,\exists b\in D_j:(a,b)\text{ 满足约束}$$

---

7. 组合优化在AI中的应用

7.1 神经网络的组合优化视角

神经网络训练可以被视为非凸组合优化问题：

• 权重空间离散化后的搜索
• 使用分支定界进行网络架构搜索（NAS）

7.2 马尔可夫链蒙特卡洛与组合优化

MCMC方法在图割、聚类等组合优化问题上广泛应用，如图像分割的Graph Cut算法。

7.3 强化学习的规划

强化学习的核心问题——寻找最优策略，可以建模为在状态-动作空间上的组合优化：

技术	应用
动态规划	值函数迭代
线性规划	策略优化
割平面法	近似动态规划
约束满足	任务规划

---

8. 计算复杂度总结

问题	复杂度	最优算法
LP	P	单纯形/内点法
ILP	NP难	分支定界
二分图匹配	P	匈牙利算法
一般图匹配	P	Edmonds算法
最大流	P	Dinic/推送-重标记
旅行商（度量）	APX难	Christofides
调度 $P		C_{\max}$

---

参考来源

1. Bertsimas, D., & Tsitsiklis, J. (1997). Introduction to Linear Optimization. Athena Scientific.
2. Wolsey, L. A. (1998). Integer Programming. Wiley.
3. Kuhn, H. W. (1955). The Hungarian Method for the Assignment Problem. Naval Research Logistics Quarterly.
4. Lawler, E. L. (1976). Combinatorial Optimization: Networks and Matroids. Holt.
5. Schrijver, A. (2003). Combinatorial Optimization: Polyhedra and Efficiency. Springer.

---

相关文档

• 计算复杂性理论深度 - 问题的固有难度分析
• 近似算法详解 - NP难问题的实用近似
• 在线算法详解 - 无完整信息的决策
• 随机算法深度 - 概率方法在优化中的应用