基于线性规划的图最小反馈弧集问题求解示例
我将为您讲解如何将图的最小反馈弧集问题建模为线性规划问题并求解。反馈弧集是指删除后能使有向图变为无环的边集合，我们的目标是找到权重最小的这样的集合。
问题描述
给定有向图G=(V,E)，每条边e∈E有非负权重w_e。反馈弧集是边集F⊆E，使得删除F后剩余图无环。目标是找到使总权重∑_{e∈F} w_e最小的反馈弧集。
问题建模为整数规划
关键观察：有向图无环当且仅当存在顶点拓扑排序。引入0-1变量：
- x_e=1表示边e在反馈集中（被删除），否则为0
- 对每个顶点v，引入位置变量p_v∈[0,|V|-1]表示其在拓扑排序中的位置
约束条件：对每条边(u,v)∈E，如果保留该边（x_e=0），则必须有p_u < p_v（即u在v之前）。这可通过大M法线性化：
p_u - p_v + 1 ≤ M*x_e （M为足够大常数，如|V|）
整数规划模型：
min ∑_{e∈E} w_ex_e
s.t. p_u - p_v + 1 ≤ |V|x_e ∀e=(u,v)∈E
0 ≤ p_v ≤ |V|-1 ∀v∈V
x_e ∈ {0,1}, p_v为整数
线性规划松弛
将整数约束松弛为连续约束：
x_e ∈ [0,1], p_v为实数
得到线性规划：
min ∑_{e∈E} w_ex_e
s.t. p_u - p_v + 1 ≤ |V|x_e ∀e=(u,v)∈E
0 ≤ p_v ≤ |V|-1 ∀v∈V
x_e ≥ 0
注意p_v的上界约束可省略（因目标函数不包含p_v，且大M约束已限制其范围）。
线性规划求解
- 该LP有|E|+|V|个变量和|E|个主要约束（加上非负约束）
- 可使用单纯形法或内点法求解
- 最优解中x_e通常为分数值，需要处理
随机舍入算法
LP解本身不是整数解，需要转化为反馈弧集：
- 随机选取θ∈[0,1)均匀分布
- 对每个顶点v，计算q_v = p_v + θ（p_v来自LP解）
- 按q_v值对顶点升序排列，得到拓扑序
- 所有违反该排序的边（即起点在终点之后的边）构成反馈弧集
理论保证
可证明：每条边e被选入反馈集的概率≤ x_e*ln(1 + 1/δ) + δ，其中δ为小常数。
这意味着期望权重不超过LP最优值的O(log|V|)倍。
实例演示
考虑4顶点有向图：边A→B(重3), B→C(重2), C→A(重4), A→D(重1), D→C(重1)。
LP求解得：x_{AB}=0.33, x_{BC}=0.33, x_{CA}=0.67, x_{AD}=0, x_{DC}=0
p_A=0, p_B=1.33, p_C=2, p_D=0.67
随机舍入：若θ=0.5，则q=[0.5,1.83,2.5,1.17]，排序A<D<B<C。
违反边：C→A（权重4），即最小反馈弧集为{C→A}，总权重4。
总结
该方法通过线性规划松弛和随机舍入，给出了最小反馈弧集问题的O(log n)近似算法，平衡了求解效率和解的质量。