COMP5270 Week 10 总结：Linear Programming and Randomised Rounding（题解 + 知识点）

Posted on Edited on In , Word count in article: 4.4k Reading time ≈ 16 mins.

课程: COMP5270 - Randomness, Probability, and Algorithms
学期: S1 2026
来源: Week 10 - Linear Programming and Randomised Rounding, Week 10 - Tutorial 10 (Solutions)

Part 1: Tutorial 10 详细题解

Warm-up

Problem 1: LP 与 ILP 的区别

题目: 回忆 LP 和 ILP 的定义，并总结它们的关键区别。

题解:

LP: Linear Programming

LP 的形式是：在线性约束下优化线性目标函数。

标准形式：

subject to:

变量 是连续实数。

LP 可以在 polynomial time 内求解到任意精度；实践中也有成熟 solver。

ILP: Integer Linear Programming

ILP 与 LP 类似，但额外要求某些变量是整数，常见是：

这让 ILP 可以表达组合优化问题，例如 set cover、Max-SAT、knapsack、Max-Cut 等。

但 ILP 一般是 NP-hard，不能期望 polynomial-time exact solver。

核心差异

项目 LP ILP
变量 连续 整数/0-1
可解性 polynomial-time solvable generally NP-hard
表达能力 较弱 可表达很多组合问题
用法 relaxation 后求 fractional solution 原始 combinatorial formulation

本题用到的知识点:

  1. LP 是连续线性优化。
  2. ILP 加整数约束，表达能力更强但更难。
  3. LP relaxation 是 approximation algorithm 的常见起点。

Problem 2: Max-Cut 的 ILP 与 LP relaxation

题目: 把 Max-Cut 写成 ILP；给出 LP relaxation 和 randomized rounding；证明某个 fractional solution 总是 optimal；说明 rounding 变成什么。

题解:

设图 ，边权 。对每个顶点 定义：

表示 在 cut 的哪一侧。

对每条边 定义：

表示边 是否被 cut。

ILP

目标：

约束：

如果 ，两个约束会迫使 ；如果 ，允许 。

LP relaxation

把 integrality constraints 放松为：

Rounding

一个自然方案是独立地把每个顶点放入 ：

则边 被 cut 的概率：

为什么 总是 LP optimal?

设：

检查约束：

可行。

目标值是：

这是 LP 能达到的最大可能值，因为 。所以它是 LP optimal。

rounding 变成什么?

因为所有 ，rounding 就是每个顶点独立地以概率 放入 cut 一侧。这正是之前 Max-Cut 的简单随机算法。

每条边被 cut 概率：

所以期望 cut value：

LP relaxation 对这个 formulation 没带来更好结果。

本题用到的知识点:

  1. 用 vertex-side variable 和 edge-cut variable 写 ILP。
  2. LP relaxation 可能太弱，出现 integrality gap。
  3. Randomized rounding 可把 fractional 解释成概率。
  4. Max-Cut 简单随机算法是 approximation。

Problem 3: Derandomise Max-SAT 的 approximation

题目: 说明如何 derandomise 课堂上的 Max-SAT -approximation algorithm。

题解:

课堂的 算法是 best-of-two：

  1. naive random assignment；
  2. LP relaxation 后 randomized rounding；
  3. 返回满足 clauses 更多的 assignment。

要 derandomise，可以分别对两个 randomized algorithm 用 method of conditional expectations。

1. Naive random assignment

变量按顺序固定 。每一步比较：

和：

选择条件期望更大的值。

因为：

至少一个分支不低于当前条件期望。最终得到 deterministic assignment，其 value 至少为原 randomized expectation。

2. LP randomized rounding

LP rounding 中：

变量不一定是 。条件期望分解为：

仍然至少有一个分支的条件期望不低于当前值。每一步取更大分支即可。

3. Best-of-two

分别 derandomise 两个算法后，得到两个 deterministic assignments，返回更好的那个。因为每个都保持了对应 randomized expectation，所以 best-of-two 的 guarantee 保留。

本题用到的知识点:

  1. Method of conditional expectations。
  2. 非均匀 Bernoulli rounding 下的条件期望分解。
  3. Best-of-two approximation 可分别 derandomise。

Problem Solving

Problem 4: Knapsack 的 ILP、LP relaxation 与 fractional greedy

题目: Knapsack 中物品 价值 、重量 ，容量 。写 ILP、LP relaxation，并比较 fractional knapsack greedy 和 ILP。

题解:

定义：

表示是否选物品 。

a) ILP

subject to:

b) LP relaxation

把：

放松为：

这就是 fractional knapsack。

c) 给定实例

题目给：

所以 value/weight ratio：

越大的 越值得选。

当 ，fractional greedy 从 、 开始选：

  • 选 ，重量 10，价值 100；
  • 选 ，重量 9，价值 81；
  • 剩余容量 1，只能选 的 。

所以 LP 解：

当 ，剩余容量变成 6，所以 选 ：

d) 与 fractional greedy 比较

Fractional knapsack 的 greedy strategy 就是按：

从大到小排序，尽量选满。因此与 LP relaxation optimal solution 相同。

e) ILP optimal

对 ，课程 solution 给出 ILP optimal：

即选物品 ，总重量：

总价值：

而 fractional LP 对 的价值是：

LP relaxation 的最优值高于 ILP，这是正常的，因为 LP feasible region 更大。

本题用到的知识点:

  1. Knapsack 的 0-1 ILP。
  2. LP relaxation 对应 fractional knapsack。
  3. Fractional knapsack greedy 按 value/weight ratio。
  4. Relaxation optimum 是 ILP optimum 的上界。

Problem 5: 无 negated unit clauses 的 biased random assignment

题目: Max-SAT 没有 negated unit clause。若每个变量以固定概率 设为 1，分析 approximation，优化 ，再讨论如何去掉假设。

题解:

a) 证明 approximation

考虑任意 clause 。

若它是 unit clause，由假设只能是非 negated：

它被满足的概率是：

若 clause 长度至少 2，设其中 negated literals 有 个，non-negated literals 有 个，。

它不被满足，意味着：

  • 所有 negated literals 为 false，即对应 ；
  • 所有 non-negated literals 为 false，即对应 。

概率：

因为 ，所以 ，且 ，有：

所以 clause 被满足概率至少：

综合 unit 和 non-unit：

因此：

b) 优化

最大化：

最优在两者相等时：

即：

正根：

此时 approximation ratio 也是约 。

c) 去掉 no negated unit clause 假设

设：

  • ：同时含有 unit clauses 和 的变量集合；
  • ：只含有 negated unit clause 的变量集合。

对 ，改为以概率 设 ，这样 被满足概率是 。

对其他变量，仍以概率 设为 1。

若 ，unit clauses 和 不可能同时满足，所以最优解至少要丢掉每个 中的一条 clause：

随机方案对除 中 negated unit clauses 以外的 clauses，满足概率至少 。因此：

d) 与 LP rounding 比较

这里得到：

而 LP rounding 的 guarantee 是：

所以 LP rounding 更好。

本题用到的知识点:

  1. Biased random assignment。
  2. Clause satisfied probability 分 unit 和 length 。
  3. 解 优化 min guarantee。
  4. 用结构性上界 处理冲突 unit clauses。

Problem 6: 直接 randomized rounding 得到 Max-SAT approximation

题目: LP rounding 中不设 ，而设：

其中 满足：

证明得到 expected approximation。

题解:

设 clause 的 LP constraint 中对应：

b) 不满足概率上界

Clause 不满足概率：

由 的上下界：

对 negated literal：

所以：

c) 满足概率至少

因此：

函数：

在 上是 concave，且：

凹函数在弦上方，所以：

因此：

d) 总期望

用期望线性性：

而 LP optimum 至少 ILP optimum：

所以：

本题用到的知识点:

  1. LP relaxation 的 表示 clause 被满足的 fractional extent。
  2. 随机 rounding 的 clause failure probability 是乘积。
  3. 用指数上下界把乘积转成 。
  4. Concavity 给 。

Advanced

Problem 7: 线性函数 rounding 也能给

题目: 若设：

证明也能直接得到 expected approximation。

题解:

Week 10 solution PDF 没给完整答案，下面给出标准推导。

对任意 literal，令它在 LP clause constraint 中的贡献为：

是正是负

则：

若 literal 是正的 ，它为 false 的概率：

若 literal 是负的 ，它为 false 需要 ，概率：

因此 clause 不满足概率：

设 clause 长度为 。由 AM-GM：

所以满足概率至少：

定义：

它在 上是 concave，且 。因此：

检查：

其中 时取等号或刚好成立， 时左边更大。

于是：

求和得到：

本题用到的知识点:

  1. Linear randomized rounding。
  2. AM-GM 把 failure probability product 转成 average。
  3. LP clause constraint 给 。
  4. Concavity + endpoint lower bound 得 。

Part 2: Week 10 讲义知识点

0. 基础版导读：LP relaxation 和 rounding 的套路

Week 10 的主题是 Linear Programming and Randomised Rounding。这一周的核心套路是：

先把难的离散优化问题写成整数规划 ILP；再放松成 LP；解 LP 得到分数解；最后把分数解 rounding 成合法整数解。

很多组合优化问题本来要求变量只能取 0/1。例如：

选择不选择

这类问题常常是 NP-hard。LP relaxation 把约束 放宽成：

这样 LP 可以在多项式时间内求解，但得到的 可能是分数。Rounding 的任务就是把分数解变成整数解，并证明目标值不会变差太多。

LP relaxation 为什么给 bound?

如果是 maximization problem：

  • ILP feasible solutions 是 LP feasible region 的子集。
  • 所以 LP optimum 至少和 ILP optimum 一样大。

即：

LP optimum 是一个 upper bound。做 approximation 时常用：

如果是 minimization problem，方向会反过来，LP optimum 是 lower bound。

randomized rounding 怎么理解?

Randomized rounding 把 LP 解中的分数当成概率。例如 ，就以概率 0.7 令 ，以概率 0.3 令 。

这样做的好处是：

所以很多 linear objective 的期望可以直接对应 LP objective。难点在于约束是否仍满足、以及 clause/edge 被满足的概率是多少。

Max-SAT 的基本模型

Max-SAT 给一组 clauses，每个 clause 是若干 literals 的 OR。目标是让尽量多 clauses 为 true。

ILP 常用变量：

  • 表示 boolean variable 是否取 true。
  • 表示 clause 是否被满足。

如果 clause 中有 positive literal ，它贡献 ；如果有 negative literal ，它贡献 。约束大致是：

LP relaxation 允许 。

naive random assignment 的 和

如果每个 variable 独立以概率 取 true，一个长度为 的 clause 不满足的概率是：

所以满足概率是：

长度至少 1 时，这至少是 。如果所有 clauses 长度至少 2，则至少是 。

Week 10 的重点是：普通随机赋值和 LP rounding 各有优势。短 clause 上 LP rounding 强，长 clause 上 naive random assignment 已经很好。把两者取 best-of-two，可以得到 approximation。

LP randomized rounding 的证明套路

LP rounding 中，令 variable 以概率 取 true。

对一个 clause ，设它包含的 LP literal values 是 。不满足概率是：

所以满足概率是：

LP 中有：

证明 approximation ratio 时，常用 或 AM-GM，把乘积上界转成关于 的表达式。

derandomisation 是什么?

如果一个 randomized algorithm 的期望值至少是某个 bound，那么一定存在某次随机选择达到至少这个期望。Derandomisation 的目标是不用随机也找到这样的选择。

Week 10 常用 method of conditional expectation：

  1. 按顺序给变量赋值。
  2. 每次尝试 和 。
  3. 选择使“剩余随机过程的条件期望”更大的那个值。
  4. 条件期望不会下降，所以最后得到的确定性解至少达到初始期望。

这也是 tutorial 中 derandomise Max-SAT 的核心。

Knapsack 的 LP relaxation

0/1 Knapsack 要么拿某个 item，要么不拿。LP relaxation 允许拿 item 的一部分。

Fractional knapsack 可以按 value/weight ratio 贪心求最优：先拿单位价值最高的 item，直到容量用完，最后一个 item 可以只拿一部分。

但 0/1 knapsack 不允许拿一部分，所以 fractional optimum 是 upper bound，不一定可行。题目常让你比较：

  • ILP optimum：真正 0/1 最优。
  • LP optimum：允许分数后的上界。
  • rounding 或 greedy 得到的可行解。

做题时怎么下手?

  • 看到优化问题：先定义 0/1 变量，再写 objective 和 constraints。
  • 写 relaxation：把 改成 。
  • 证明 approximation：先和 LP optimum 比，再用 LP optimum bound ILP optimum。
  • 分析 randomized rounding：计算每个 clause/edge/item 被满足或被选中的概率。
  • Derandomise：写条件期望，并说明每步选择不会降低它。

1. LP 标准形式

LP：

subject to:

线性目标、线性约束、连续变量。

课程重点不是 LP solver，而是 LP relaxation + rounding 作为 approximation algorithm design pattern。

2. ILP 与 LP relaxation

组合问题常能写成 ILP：

将其放松成：

得到 LP relaxation。

对 maximization：

对 minimization 方向相反。

3. Rounding

LP 解通常是 fractional，不是原问题可行解。Rounding 把 fractional solution 转成 integral solution。

常见：

  • deterministic rounding；
  • randomized rounding；
  • threshold rounding。

分析目标：证明 rounding 后的 expected value 或 high-probability value 接近 ，再由 与 的关系得到 approximation。

4. Min-Cut 的 LP rounding 示例

对 directed - min-cut，可把 cut 写成 ILP，再 LP relax。

Random threshold rounding：

  1. 取 ；
  2. 若 ，令 ，否则 0。

对边 ：

因此期望 cut value 不超过 LP optimum，而任何 cut 又不可能低于 true min-cut，所以实际上得到 optimal cut。

5. Max-SAT naive randomized algorithm

每个变量独立均匀随机赋值。

长度为 的 clause 不满足概率：

满足概率：

所以：

对 Max-E3SAT，长度全为 3，则：

6. Max-SAT 的 ILP

变量：

  • 表示 Boolean variable ；
  • 表示 clause 是否被满足。

ILP：

subject to:

LP relaxation：

7. Max-SAT LP randomized rounding

解 LP 得 。

随机设置：

对 clause ，不满足概率：

用 AM-GM 和 LP constraint 可得：

总期望：

8. Best-of-two 得到

Naive random algorithm 对长 clauses 好。

LP rounding 对短 clauses 好。

运行两个算法，取更好的 solution。因为：

可证明：

9. Derandomisation

Random assignment 类算法通常可用 conditional expectations derandomise。

核心模板：

选择使条件期望更大的分支，最终 deterministic value 至少达到原 expected value。

本周核心记忆

主题 关键结论
LP continuous variables, polynomial-time solvable
ILP integer variables, generally hard
LP relaxation maximization 中
Randomized rounding fractional value 当概率
Max-SAT naive approximation
Max-SAT LP rounding approximation
Best-of-two Max-SAT approximation
AM-GM Max-SAT LP rounding 的关键
Conditional expectation 可 derandomise rounding/assignment