图着色问题ILP模型的LP松弛问题对偶求解咨询

首先，你的LP松弛是完全正确的——把原ILP里的0-1变量放松到[0,1]区间，保留所有约束，这是标准的松弛方式。接下来我会一步步带你推导这个LP的对偶问题，尽量讲得直白些：

第一步：明确原LP的结构 #

先把你的LP松弛重新整理成更清晰的形式（去掉冗余的x_{v,c} ≤1约束，因为∑_c x_{v,c}=1且x_{v,c}≥0，自然每个x_{v,c}不会超过1）：

$$
\min \sum_{c \in C} w_c \
\text{s.t.} \

1. \quad \sum_{c \in C} x_{v,c} = 1 \quad \forall v \in V \quad \text{（每个顶点必须分配至少一个颜色）} \
2. \quad x_{u,c} + x_{v,c} \leq w_c \quad \forall (u,v) \in E, c \in C \quad \text{（相邻顶点不能同时用某颜色，除非该颜色被标记为“使用”）} \
3. \quad w_c \leq 1 \quad \forall c \in C \quad \text{（颜色的使用标记不超过1）} \
4. \quad x_{v,c} \geq 0, w_c \geq 0 \quad \forall v \in V, c \in C
   $$

第二步：分配对偶变量 #

对偶问题的变量对应原LP的每个约束，规则是：

• 原极小化问题的等式约束对应自由对偶变量（无符号限制）
• 原极小化问题的≤不等式约束对应非负对偶变量

我们给每个约束分配变量：

• 对每个顶点v的等式约束（规则1），分配自由变量α_v
• 对每个边(u,v)和颜色c的不等式约束（规则2），分配非负变量β_{(u,v),c} ≥ 0
• 对每个颜色c的不等式约束（规则3），分配非负变量δ_c ≥ 0

第三步：写出对偶的目标函数 #

对偶是极大化问题，目标函数等于原LP约束右端项乘以对应对偶变量的总和：
$$
\max \sum_{v \in V} 1 \cdot \alpha_v + \sum_{(u,v) \in E,c \in C} 0 \cdot \beta_{(u,v),c} + \sum_{c \in C} 1 \cdot \delta_c
$$
简化后就是：
$$
\max \sum_{v \in V} \alpha_v + \sum_{c \in C} \delta_c
$$

第四步：写出对偶的约束条件 #

对偶的约束对应原LP的每个变量，要求“对偶变量的线性组合 ≤ 原目标函数中该变量的系数”：

1. 针对变量x_{v,c}：原目标函数中它的系数是0。它在原约束里的出现位置：
   • 顶点v的等式约束里系数为1（对应α_v）
   • 所有包含v的边(u,v)的约束里系数为1（对应β_{(u,v),c}）
     所以约束为：
     $$
     \alpha_v + \sum_{u: (u,v) \in E} \beta_{(u,v),c} \leq 0 \quad \forall v \in V, c \in C
     $$
2. 针对变量w_c：原目标函数中它的系数是1。它在原约束里的出现位置：
   • 所有边(u,v)的约束里系数为-1（对应β_{(u,v),c}）
   • 颜色c的上界约束里系数为1（对应δ_c）
     所以约束为：
     $$
     -\sum_{(u,v) \in E} \beta_{(u,v),c} + \delta_c \leq 1 \quad \forall c \in C
     $$

第五步：简化对偶问题 #

我们可以消去冗余的对偶变量，让问题更简洁：

• 对于δ_c：因为目标函数要最大化∑δ_c，且约束是δ_c ≤ 1 + ∑_{(u,v)∈E}β_{(u,v),c}，同时δ_c≥0，所以最优的δ_c就是1 + ∑_{(u,v)∈E}β_{(u,v),c}（这个值肯定非负，因为β≥0）。把它代入目标函数：
  $$
  \max \sum_{v \in V} \alpha_v + \sum_{c \in C} \left(1 + \sum_{(u,v) \in E}β_{(u,v),c}\right)
  $$
  展开后：
  $$
  \max |C| + \sum_{v \in V} \alpha_v + \sum_{(u,v) \in E,c \in C}β_{(u,v),c}
  $$
• 对于α_v：约束要求α_v ≤ -∑_{u:(u,v)∈E}β_{(u,v),c}对所有c∈C，所以α_v的最大值是min_{c∈C} \left(-∑_{u:(u,v)∈E}β_{(u,v),c}\right)。代入目标函数后，最终对偶问题可以简化为只含β变量的形式：
  $$
  \max |C| + \sum_{v \in V} \min_{c \in C} \left(-\sum_{u:(u,v) \in E}β_{(u,v),c}\right) + \sum_{(u,v)∈E,c∈C}β_{(u,v),c} \
  \text{s.t.} \
  β_{(u,v),c} ≥ 0 \quad \forall (u,v)∈E,c∈C
  $$

这样就得到了简化后的对偶问题。如果需要验证正确性，可以用互补松弛条件：原LP和对偶LP的最优解满足，原约束取等号时对应对偶变量非零，对偶约束取等号时对应原变量非零。

备注：内容来源于stack exchange，提问作者mNugget