基于线性规划的图边着色问题求解示例
我将为您讲解基于线性规划的图边着色问题的求解方法。这是一个经典的图论优化问题，我们先用线性规划建立模型，然后分析求解过程。
1. 问题描述
给定一个简单无向图 G=(V, E)，其中 V 是顶点集合（|V|=n），E 是边集合（|E|=m）。边着色问题要求为每条边分配一种颜色，使得相邻的两条边（即共享同一个顶点的边）不能使用同一种颜色。我们的目标是使用尽可能少的颜色来完成这样的着色。
这个问题在数学上等价于图的边色数 χ'(G)（chromatic index）的计算。Vizing定理告诉我们：对于简单图，边色数要么等于最大度 Δ(G)，要么等于 Δ(G)+1，但具体判断属于哪一类是NP困难的。
2. 线性规划建模
我们先建立一个整数线性规划模型。
2.1 决策变量
设 K 是一个足够大的颜色数上界（例如 K = m，因为最多需要 m 种颜色）。
定义两组决策变量：
- x_ek：二元变量，如果边 e 被着上颜色 k，则 x_ek = 1，否则为 0。
- y_k：二元变量，如果颜色 k 被至少一条边使用，则 y_k = 1，否则为 0。
2.2 目标函数
最小化被使用的颜色总数：
minimize Σ_{k=1}^{K} y_k
2.3 约束条件
- 每条边必须恰好着一种颜色：
Σ_{k=1}^{K} x_ek = 1, ∀ e ∈ E
- 相邻边不能同色（对于每个顶点 v 和每种颜色 k，在 v 处关联的边至多一条使用颜色 k）：
Σ_{e ∈ δ(v)} x_ek ≤ 1, ∀ v ∈ V, ∀ k = 1,...,K
其中 δ(v) 表示与顶点 v 关联的边集合。
- 如果至少有一条边使用了颜色 k，则 y_k 必须为 1：
x_ek ≤ y_k, ∀ e ∈ E, ∀ k = 1,...,K
等价于：如果存在某个 e 使 x_ek = 1，则强制 y_k ≥ 1，又由于 y_k 是二元变量且目标最小化，所以 y_k 会被推向 1。
- 变量类型：
x_ek ∈ {0,1}, ∀ e ∈ E, ∀ k = 1,...,K
y_k ∈ {0,1}, ∀ k = 1,...,K
3. 线性规划松弛与对偶问题
3.1 松弛模型
将整数约束松弛为连续约束：
0 ≤ x_ek ≤ 1
0 ≤ y_k ≤ 1
其他约束不变。这个线性规划松弛的最优值 ≤ 整数规划的最优值（即 χ'(G)）。
3.2 对偶问题（理解结构）
原松弛问题（记为 P）可以写成以下更紧凑的形式：
目标：min 1^T y
约束：
- A x = 1 （每条边一种颜色）
- B x ≤ 1 ⊗ 1 （相邻约束，其中 ⊗ 表示张量积）
- x_ek ≤ y_k
- x ≥ 0, y ≥ 0
写出其拉格朗日函数并得到对偶问题（记为 D），对偶变量分别为：
- α_e：对应每条边必须着一种颜色的约束
- β_vk ≥ 0：对应顶点 v 处颜色 k 的相邻约束
- γ_ek ≥ 0：对应 x_ek ≤ y_k 的约束
对偶问题具有最大化形式，其具体表达式有助于分析算法性能，但此处我们关注原始问题的求解。
4. 求解策略
由于整数规划是NP难的，我们通常采用以下策略：
4.1 列生成思路（颜色生成）
注意到颜色种类 K 可能很大，我们可以隐式地考虑所有可能的“匹配着色”。因为每种颜色 k 对应的边集必须是一个匹配（即不相邻的边集合）。
重新建模：令 M 为图 G 中所有匹配的集合。对于每个匹配 M_j ∈ M，引入变量 z_j ≥ 0 表示该匹配（颜色）被使用的“程度”。由于每条边必须被覆盖，且我们希望最小化使用的匹配数，得到集合覆盖型整数规划：
min Σ_{j} z_j
s.t. Σ_{j: e ∈ M_j} z_j ≥ 1, ∀ e ∈ E
z_j ∈ {0,1}
松弛 z_j ∈ {0,1} 为 z_j ≥ 0，这就是一个线性规划。但匹配数量指数级，因此可以使用列生成：
- 限制主问题：只考虑一部分匹配。
- 定价子问题：寻找一个匹配 M_j，其对应的约简成本 c̄_j = 1 - Σ_{e ∈ M_j} π_e < 0，其中 π_e 是对应边 e 覆盖约束的对偶变量。
- 子问题实际上是在边权为 π_e 的图中寻找最大权匹配（因为若 c̄_j < 0，则 1 - Σ π_e < 0 ⇒ Σ π_e > 1，所以我们要找 Σ π_e 最大的匹配）。
- 最大权匹配可以在多项式时间内解决（例如开花算法）。
- 迭代添加负约简成本的匹配列，直到无负约简成本列，则得到松弛最优解。
4.2 分数解的处理与整数化
线性规划松弛最优解可能是分数（例如，三条边形成一个三角形，松弛最优解为 3/2 种颜色，每条边被两个匹配各覆盖 1/2）。但根据 Edmonds 的匹配多面体理论，对于二分图，松弛是整数解（即 χ'(G) = Δ）。对于非二分图（有奇圈），可能产生分数解。
舍入策略：线性规划松弛值提供了下界。实际边色数至少为 Δ，且至多为 Δ+1（Vizing定理）。我们可以：
- 求解松弛得到分数匹配覆盖。
- 将分数解转化为 Δ 或 Δ+1 种颜色的可行边着色（可能需要复杂组合算法，如 Vizing 算法的推广）。
5. 具体算例演示
考虑一个简单的三角形图（三个顶点，三条边构成一个圈）。
- 顶点：{1,2,3}
- 边：e12, e23, e31
- 最大度 Δ = 2
5.1 线性规划模型（简化颜色数上界 K=3）
变量：x_ek, k=1,2,3; y_k, k=1,2,3
约束：
每条边一种颜色：
(1) x_e12,1 + x_e12,2 + x_e12,3 = 1
(2) x_e23,1 + x_e23,2 + x_e23,3 = 1
(3) x_e31,1 + x_e31,2 + x_e31,3 = 1
每个顶点处每种颜色至多一条边：
对于颜色1：
(4) x_e12,1 + x_e31,1 ≤ 1 （顶点1）
(5) x_e12,1 + x_e23,1 ≤ 1 （顶点2）
(6) x_e23,1 + x_e31,1 ≤ 1 （顶点3）
类似地对于颜色2、颜色3也有约束（共9个约束）。
连接变量约束：
(7) x_e12,1 ≤ y_1, x_e12,2 ≤ y_2, x_e12,3 ≤ y_3
(8) x_e23,1 ≤ y_1, ...
(9) x_e31,1 ≤ y_1, ...
目标：min y1 + y2 + y3
5.2 松弛求解（直观分析）
我们猜测一种分数解：
- 颜色1：边 e12 和 e23 各用 1/2，但它们在顶点2冲突？不，检查顶点2约束：x_e12,1 + x_e23,1 ≤ 1，1/2 + 1/2 = 1，满足。
- 颜色2：边 e23 和 e31 各用 1/2（顶点3约束满足）。
- 颜色3：边 e31 和 e12 各用 1/2（顶点1约束满足）。
每条边恰好两种颜色各 1/2，例如边 e12：颜色1用1/2，颜色3用1/2，和为1。
此时 y1 = y2 = y3 = 1/2（因为每种颜色被使用程度最大为1/2，但约束 x_ek ≤ y_k 迫使 y_k ≥ 1/2，目标最小化会令 y_k = 1/2）。
目标值 = 1.5。
5.3 解释
三角形图的边色数整数解是 3（因为它是奇长圈，需要3种颜色），但线性规划松弛给出下界 1.5 ≈ 2（实际上 Δ=2，松弛下界 ≤ χ' ≤ Δ+1=3）。这里松弛值 1.5 小于整数解 3，显示存在整数间隙。
6. 实际应用与扩展
- 二分图：松弛总是整数解，且 χ'(G) = Δ，可以通过求解松弛直接得到最优边着色（例如将问题转化为最大匹配反复求解）。
- 一般简单图：松弛值可能非整数，但总是满足 Δ ≤ LP_opt ≤ χ' ≤ Δ+1。因此若松弛值 > Δ，则 χ' = Δ+1；若松弛值 = Δ 且能得到整数解，则 χ' = Δ。
- 算法实现：可以使用列生成求解匹配覆盖的线性规划松弛，然后利用 Vizing 算法构造 Δ+1 边着色，这给出了一个近似比为 (Δ+1)/Δ 的近似算法，当 Δ 大时接近最优。
总结
我们通过线性规划建模图的边着色问题，并介绍了列生成求解大规模匹配覆盖模型的方法。虽然整数规划求解困难，但线性规划松弛提供了紧下界，结合图论知识（Vizing定理）能设计有效近似算法。这种方法展示了线性规划与组合优化问题的深刻联系。