整数编程算法设计与分析笔记

最编程 2024-04-20 12:25:45

...

课上讲了带权点覆盖问题的整数规划，考试可能会给一个问题让你建立整数规划模型。

带权点覆盖的整数规划（ILP）

对每一个点 $i$ ，用bool变量 $x_{i}$ 表示其是否在点覆盖集合中。 $x_{i}=0$ ，点 $i$ 不在点覆盖中； $x_{i}=1$ 点 $i$ 在点覆盖中。因此，整数规划带权点覆盖问题转换为：
$(ILP)min\sum_{i\in V}w_{i}x_{i}$
$s.t. \; x_{i}+x_{j}\geq 1\;(i,j)\in E$
$x_{i}\in \{0,1\}\;i\in V$
整数规划的最优解 $x^{*}$ ，就对应于权值最小的点覆盖 $S=\{i\in V:x^{*}_{i}=1\}$
但点覆盖的整数规划是一个NP难问题，因此我们希望能找到它的近似算法，牺牲准确度以快速求解。很容易想到把它转化为线性规划问题，并找到它的近似程度。建立如下线性规划，注意第三式：
$(LP)min\sum_{i\in V}w_{i}x_{i}$
$s.t. \; x_{i}+x_{j}\geq 1,\;(i,j)\in E$
$x_{i}≥0,\;i\in V$
线性规划的约束条件不如整数规划苛刻，所以线性规划（LP）的最优解≤整数规划（ILP）的最优解。但会带来一个问题，加入点覆盖集合中的点 $i$ 其 $x_{i}$ 极有可能是分数，会呈现如下形式

线性规划可能得到的点覆盖

那么，如何找到点覆盖问题线性规划与整数规划得到的解之间的关系？
定理：如果 $x$ 是LP的最优解，那么点覆盖 $S=\{i\in V:x_{i}≥ \frac{1}{2}\}$ ，且是准确解的2倍近似。
分别证明：
pf1. 对于边 $(i,j)\in E$ ，
点覆盖中有 $x_{i}+x_{j} \geq 1$ ，则 $x_{i}\geq \frac{1}{2}$ 或 $x_{j}\geq \frac{1}{2}$ （边 $(i,j)$ 被覆盖）.
pf2. 设点覆盖的准确值为 $S^{*}$ ，有
$\sum _{i \in S^{*}}{w_{i}} \geq\sum_{i\in S}{w_{i}x_{i}}\geq \frac{1}{2}\sum_{i\in S}w_{i}$ .
第一个不等式：根据整数规划的最优解不小于线性规划这一性质放缩；
第二个不等式： $x_{i}\geq \frac{1}{2}$ .

我的疑惑
整数规划的解不大于线性规划是指 $\sum_{i\in S^{*}}w_{i}x_{i}\geq \sum_{i\in S}w_{i}x_{i}$ ，前一个（整数规划）的 $x_{i}$ 可以省略，因为整数规划得到的点覆盖中的点 $i$ 其 $x_{i}=1$ 。而线性规划得到的点覆盖最小权值是 $\sum_{i\in S}w_{i}$ ，不乘以 $x_{i}$ （注意这里的 $x_{i}$ 可以是分数），因为当 $x_{i}\geq\frac{1}{2}$ 就把点 $i$ 加入了点覆盖，算权值只将各点权值相加即可。（应该是这样吧，哪个大佬看见有不同的想法戳我）