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

Posted on 2026-06-14 In Course Notes , COMP5270 Word count in article: 6.8k Reading time ≈ 25 mins.

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

Part 1: Tutorial 10 详细题解

各题难度/要求说明：

Problems 1, 2, 3：需看过讲义，应自行尝试，对理解算法很重要。（Problem 3 将本周内容与第 4 章的去随机化联系起来。）
Problem 4：需用 Matlab 比较算法，实践线性规划库。
Problem 5：大体可做，子题 c) 较难（⋆）。
Problem 6：技术性较强、难度较高，是检验是否理解讲义证明的好题。
Problem 7：有时间则做，进阶练习，题解未提供。

Problem 1（Warm-up）：LP vs ILP

题目：回顾定义，总结 LP 和 ILP 的关键区别。

解答：

线性规划（LP，Linear Program）： - 在连续域上优化线性目标函数，满足线性约束 - 数学形式：，约束， - LP 是 P-complete：每个多项式时间可解的决策问题都可以表示为某个 LP - 存在多项式时间算法（单纯形法、内点法等）高效求解

整数线性规划（ILP，Integer Linear Program）： - 在 LP 基础上额外要求部分（或全部）变量取整数值，通常 - 可以编码更多问题，包括 NP-Hard 问题 - 一般情况下不知道如何高效求解（ILP 是 NP-Hard）

核心区别：LP 约束是连续的，有高效求解算法；ILP 添加了整数约束，表达能力更强但求解困难。LP 松弛（将 ILP 的整数约束松弛为连续约束）是联系两者的桥梁。

Problem 2：Max-Cut 的 ILP 公式与 LP 松弛

题目：将 Max-Cut 形式化为 ILP。
(a) 给出 LP 松弛，提出随机舍入策略。
(b) 证明，总是 LP 松弛的最优解。
(c) 此时你的舍入方案变成什么？

解答：

(a) ILP 公式：

对无向图，边权，变量表示顶点归属，表示边是否被割：

直觉：第一条约束保证若两顶点同侧（），则；第二条保证若，则；只有两顶点异侧时才可行。

LP 松弛：将松弛为，松弛为。

随机舍入策略：以概率将顶点放入集合（独立）。则边被割的概率为：

(b) 证明是最优 LP 解：

设对所有，对所有。

检验约束：（满足）；（满足）。

LP 目标值，即所有边权之和——这是 LP 的上界（因），故是最优 LP 解。

(c) 舍入方案退化为朴素随机算法：

当 LP 返回最优解时，"以概率将放入 "就变成"每个顶点独立以概率放入 "。这正是我们之前见过的简单随机算法，期望割值为。这说明此例中 LP 松弛没带来额外收益。

Problem 3：去随机化 Max-SAT 的 3/4-近似算法

题目：描述如何去随机化课堂上给出的 Max-SAT 3/4-近似算法。

解答：

使用条件期望法（Method of Conditional Expectations）。由于 3/4-近似是"两者取最优"算法（best-of-two），只需分别去随机化两个子算法。

去随机化 Theorem 48（朴素随机算法）：

对变量依次确定，每步选使条件期望最大的赋值：

不等号成立是因为，所以两者中较大的那个平均值。逐步迭代，每步保持期望值不降，最终得到确定性解，值。（条件期望值可在多项式时间内计算。）

去随机化 Theorem 49（LP 随机舍入）：

类似地：

（因为 Algorithm 22 以概率设，以概率设。）逐步迭代同样得到期望值不降的确定性解。

关于另一种去随机化方式的备注：也可以考虑枚举随机种子，但这需要 -wise 独立性（为最大子句长度）。-wise 独立需要随机比特，枚举需要时间；若最大子句长度，则这种方法不高效。

Problem 4：背包问题（Knapsack）的 LP/ILP 分析

题目：背包问题：个物品，物品价值，重量，背包容量，最大化总价值。
(a) ILP 公式 (b) LP 松弛（分数背包） (c) Matlab 求解 (d) 与贪心算法比较 (e) 与 ILP 最优解比较

解答：

(a) ILP：

变量表示是否选第件物品：

(b) LP 松弛（分数背包）：

将松弛为 ——允许"分数"地选物品：

(c) Matlab 代码及结果（物品设置：，，）：

v = (1:10).^2; w = (1:10); W = 20;
% LP relaxation (linprog minimises, so negate v):
linprog(-v, w, [W], [], [], zeros(1,10), ones(1,10));
% ILP (intlinprog):
intlinprog(-v, 1:10, w, [W], [], [], zeros(1,10), ones(1,10));

时 LP 解：（第 8 件取 1/8，第 9、10 件完整取）
时 LP 解：

(d) 与贪心对比（分数背包贪心）：

分数背包贪心策略：按单位重量价值从大到小排序，依次取。顺序，从第 10 件开始取，直到背包满（可取分数）。LP 松弛的最优解与贪心结果相同（分数背包贪心给出 LP 最优解）。

(e) ILP 最优解：时 ILP 最优解（选第 1、9、10 件）。整数约束使解与 LP 松弛不同。

Problem 5：Max-SAT 中偏置概率的分析

题目：假设 Max-SAT 实例中没有被否定的单元子句（每个子句长度，或者是非否定的单变量子句）。将朴素随机算法的设置概率从改为固定概率。

证明此方案给出期望 -近似。
最优化的选取。
(c)（⋆）去掉"无否定单元子句"的假设。
与 LP 舍入的保证比较。

解答：

(a) 证明 -近似：

考虑一个子句，设其含个否定文字、个非否定文字（，子句长度）。

子句不被满足的概率（所有否定文字对应变量取 1，所有非否定文字对应变量取 0）。

由，故（因为，对长度的子句）。

对长度为 1 的非否定单元子句：被满足概率。

故每个子句被满足的概率。由期望的线性性：

(b) 最优化 ：

令（两个表达式相等时取最大）：

（取正根）。此时 -近似。

(c)（⋆）去掉假设的推广：

设为"同时存在和单元子句"的变量集合，为"只存在单元子句"的变量集合。

对中变量的约束：无论如何赋值，中每个变量都会导致至少一个对应子句不被满足（则子句失败，则子句失败）。故（个子句中至少个无法同时满足）。

舍入方案：对，以概率设；对，以概率设（等价于翻转中变量后运行原方案）。

计算期望（取）：设为中非否定单元子句集，为中否定单元子句集，：

(d) 比较：，LP 舍入给出更好的界。

Problem 6（⋆）：直接用随机舍入得到 3/4-近似

题目：在 Algorithm 22 中，将替换为以概率设，其中满足。

画出上下界的图，确认满足条件的存在。
证明。
推导。
得出 3/4-近似结论。

解答：

(a)：可在 Mathematica 中画出：

Plot[{1 - 1/4^x, 1/4^(1-x)}, {x, 0, 1}, PlotLegends -> "Expressions"]

可见两条曲线之间有空间，满足条件的（如其线性插值）确实存在。

(b) 证明 ：

由的上界条件，得（由 ... 实际上直接用，）：

由 LP 约束，故：

(c) 推导（用凹性）：

令。是凹函数（二阶导），且，。

由凹性（，在上的割线不超过函数）：

(d) 3/4-近似结论：

最后一步由 Fact 46.1（LP 松弛值 ILP 最优值）得到。

Part 2: Week 10 讲义知识点——线性规划与随机舍入

§0 概述：近似算法的框架

本周核心主题：用线性规划（LP）和随机舍入设计近似算法。

算法设计工具演进：贪心、分治、动态规划…线性规划是又一强大工具。

近似算法的目标：对于 NP-Hard 问题（不知道如何精确求解），找到一个算法，输出解满足：

其中是近似比（对最大化问题）。若算法是随机的，则以高概率或期望满足此条件。

本章路线：ILP 公式 → LP 松弛 → 随机舍入 → 分析近似比。

§1 线性规划（LP）

Definition（线性规划，LP）：

其中是变量，是目标函数系数，，编码约束。

展开形式：

LP 的三个关键性质：

LP 是 P-complete：每个多项式时间可解的问题都可以表示为某个 LP。
理论上高效：每个 LP 可在时间多项式于（及精度）内求解至任意精度。
实践上高效：存在实际算法（单纯形法、内点法等）可快速求解 LP，工业界广泛使用。

§2 整数线性规划（ILP）与 LP 松弛

Definition（整数线性规划，ILP）：

在 LP 的基础上，要求部分（或全部）变量取整数值，通常。

ILP 的优势：可以编码更多问题，包括 NP-Hard 问题（如 Max-SAT、背包、覆盖问题等）。

ILP 的劣势：一般情况下不知道高效求解方法（ILP 本身是 NP-Hard）。

策略：将 ILP 的整数约束松弛为连续约束，转化为可高效求解的 LP——即 LP 松弛（LP relaxation）。

Definition（LP 松弛）：将 ILP 中替换为（连续约束），得到的 LP 称为原 ILP 的 LP 松弛。

Fact 46.1（LP 松弛与 ILP 最优值的关系）：

设是 ILP（最大化问题）的最优值，是其 LP 松弛的最优值，则：

（对最小化问题，不等号反向：。）

证明：ILP 的可行域是 LP 可行域的子集（整数点连续可行域），故 LP 可以取到更大的目标值。

§3 Min-Cut 的 ILP 公式（示例）

问题：有向图，边权，源，汇，求 - 最小割。

变量：（边是否在割中）；（顶点是否与汇同连通分量）。

ILP：

LP 松弛：将替换为。

§4 随机舍入——Min-Cut 示例

核心思想：LP 给出（连续解），我们需要整数解。

确定性舍入（阈值）的问题：若所有，则全部舍入为 1，可能产生很差的割。无法从 LP 解中获取有效信息。

Algorithm 21（Min-Cut 的随机舍入）：

均匀随机选取
对所有：若则设，否则设
返回

Theorem 47（随机舍入给出最优 Min-Cut）：Algorithm 21 返回的割满足：

证明：

由期望的线性性：

（负号因为这是最小化问题，val 是割的负权重和。）

对每条边：

（由 LP 约束，若，则，区间长度，落在其中的概率。）

故：

（Fact 46.1 的最小化版本：。）

同时，总是一个有效割，故。结合，以及且，故以概率 1——随机舍入总是返回最优割！

注：此结论强于"期望最优"——事实上以概率 1 返回最优解。但对 Min-Cut，我们早已有 Max-Flow 的高效算法，此例主要是为了说明方法。

§5 Max-SAT 问题

Definition（Max-SAT）：

给定个布尔变量和个子句，每个子句是文字的析取（OR）：

子句的长度（文字数量）。目标：找赋值最大化满足的子句数。

无损假设：(1) 所有子句不同；(2) 同一子句中和不同时出现（否则子句自动满足）；(3) 每个文字在每个子句中至多出现一次。

Fact 47.1：Max-SAT 是 NP-Hard（即便判断是 NP-Complete）。

§6 Max-SAT：朴素随机算法

Theorem 48（1/2-近似）：对每个变量独立均匀随机赋值，期望满足个子句（-近似）。

证明：

对固定子句（长度），不被满足的概率（个文字全部取错）。

故被满足的概率（因）。

推论：对 Max-E3SAT（每子句恰好 3 个文字），被满足概率，给出 -近似。

§7 Max-SAT 的 ILP 公式与 LP 松弛

ILP 公式（图 15）：

变量：（对应）；（子句是否被满足）：

约束解读：对子句，若它被满足（），则至少有一个文字为真；左侧求和正好统计为真的文字数，保证若子句标记为满足则确实有真文字。

Lemma 48.1：上述 ILP 的最优值等于。

LP 松弛（图 16）：将松弛为，保持所有线性约束不变。

§8 Max-SAT：LP 随机舍入

Algorithm 22（Max-SAT 的 LP 随机舍入）：

求解 LP 松弛（图 16），得最优解
对每个：以概率独立设
返回

Theorem 49（-近似）：Algorithm 22 给出期望 -近似。

证明：

设子句中含个文字。由独立性：

LP 约束给我们：

由 AM-GM 不等式（Fact 49.1，见下节），乘积均值的幂：

故：

设，这是关于的凹函数（在上），且。由凹性（函数在割线上方）：

又由（标准极限），故。

§9 AM-GM 不等式

Fact 49.1（算术-几何平均不等式，AM-GM）：

对任意：

即几何平均算术平均。

等号成立当且仅当。

在 Max-SAT 证明中的应用：将乘积（）与和（LP 约束左侧）联系起来，是将 LP 约束用于概率分析的关键桥梁。

§10 "两者取最优"——3/4-近似

核心观察：

朴素随机算法对长子句效果好（大时）；
LP 随机舍入对短子句效果好（时保证满足概率，时保证，单调递减趋于）。

两者互补，合并可获得更好保证！

Theorem 50（3/4-近似，"两者取最优"）：

同时运行 Theorem 48（朴素随机）和 Theorem 49（LP 随机舍入），返回两个解中较好的那个，期望给出 -近似。

证明：

设分别为两个算法的输出，则：

（由式 (64) 和 (67)，以缩放后者。）

关键不等式：对任意整数及（特别地，对时）：

（此不等式对的整数成立，对需单独验证。）

故：

§11 各算法近似比对比

算法	近似比	特点
朴素随机（Theorem 48）		极简，对长子句效果更好
朴素随机（Max-E3SAT）		每子句恰好 3 个文字时的特例
LP 随机舍入（Theorem 49）		需求解 LP 松弛，对短子句好
两者取最优（Theorem 50）		结合两者，付出两倍运行时间

已知最优近似比：Max-SAT 的最优（多项式时间）近似比为（Håstad 1997 年证明了是 NP-Hard），可通过更精细的 LP/SDP 舍入达到。

§12 本章知识点总览

概念	内容
LP（线性规划）	，，；P-complete，多项式时间可解
ILP（整数线性规划）	加整数约束；表达力更强；NP-Hard
Fact 46.1	（最大化），松弛只能做得更好
LP 松弛	将松弛为，得到可高效求解的 LP
随机舍入	将的 LP 解解释为概率，随机生成整数解
Algorithm 21	Min-Cut 随机舍入；Theorem 47：期望值最优割，且以概率 1 最优
Fact 47.1	Max-SAT 是 NP-Hard
Theorem 48	朴素随机 -近似（ for E3SAT）
Max-SAT ILP	个子句变量，约束保证满足的文字数
Lemma 48.1	Max-SAT ILP 最优值
Fact 49.1	AM-GM 不等式：乘积均值的幂
Algorithm 22	Max-SAT LP 随机舍入：
Theorem 49	LP 舍入 -近似；凹性 + AM-GM
Theorem 50	"两者取最优" -近似

Part 3: Week 10 Quiz 回顾

来源：Canvas Quiz，整理自 5270-questions-organized.md。每题含中英文题目、正确答案及知识点解析。

Question 1

[EN] Linear Programming is concerned with maximising (or minimising) a ________ function subject to ________ constraints.

[CN] 线性规划关注在_约束下最大化（或最小化）_函数。

选项	答案
linear/linear	✅
convex/linear	❌
arbitrary/linear	❌
linear/convex	❌

知识点：LP 的标准形式： subject to ，。目标函数和约束均为线性（仿射），不允许二次或更高次项。

Question 2

[EN] We have efficient (polynomial-time in the number of variables, constraints, and representation of the problem) algorithms to solve linear programs (LPs).

[CN] 我们有高效（多项式时间）算法求解线性规划（LP）。

选项	答案
False	❌
True	✅

知识点：LP 可在多项式时间内求解（如 Ellipsoid 方法、Interior Point 方法），是 P-complete 问题。Simplex 方法实践中很快但理论上最坏情况指数时间。

Question 3

[EN] An Integer Linear Program (ILP) is like an LP, but the objective function is integer-valued.

[CN] 整数线性规划（ILP）与 LP 类似，但目标函数是整数值。

选项	答案
False	✅
True	❌

知识点：ILP 要求变量（整数），而非目标函数为整数值。目标函数仍是线性函数，只是变量被约束为整数，这使问题变为 NP-Hard。

Question 4

[EN] We have efficient (polynomial-time in the number of variables, constraints, and representation of the problem) algorithms to solve integer linear programs (ILPs).

[CN] 我们有高效算法求解整数线性规划（ILP）。

选项	答案
True	❌
False	✅

知识点：ILP 是 NP-Hard 的（一般情形）。整数约束使得可行域变成离散集合，目前没有已知多项式时间算法。这正是为什么研究 LP 松弛 + 随机舍入的近似方法。

Question 5

[EN] Every problem which can be solved in polynomial time can be phrased as an LP.

[CN] 所有多项式时间可解的问题都可表述为 LP。

选项	答案
True	✅
False	❌

知识点：LP 是 P-complete：所有 P 中的问题都可多项式时间归约到 LP（反过来，LP 也可在多项式时间内解决）。这说明 LP 是 P 中最"困难"的问题之一。

Question 6

[EN] Only NP-Hard problems can be formulated as ILPs.

[CN] 只有 NP-Hard 问题才能表述为 ILP。

选项	答案
False	✅
True	❌

知识点：任何决策问题（包括 P 中的问题）都可表述为 ILP，只要变量和约束足够表达。ILP 作为形式语言非常强大，不局限于 NP-Hard 问题。

Question 7

[EN] The optimal solution to the LP relaxation of an ILP typically are not solutions to the original ILP.

[CN] ILP 的 LP 松弛的最优解通常不是原 ILP 的解。

选项	答案
False	❌
True	✅

知识点：LP 松弛将放宽为，最优解通常是分数值（如），不满足整数约束。随机舍入的目的就是将分数解转化为合法整数解。

Question 8

[EN] Randomised rounding is the general idea to take the optimal solution of an ___ and round its value to integers to get a valid solution to the original ___ while being able to relate its value to that of the ___.

[CN] 随机舍入（Randomised Rounding）的一般思想是：取_的最优解，将其值舍入为整数，得到原_的有效解，同时能将其值与____的值关联。

选项	答案
LP/ILP/LP	✅
ILP/LP/LP	❌
LP/ILP/ILP	❌

知识点：流程：① 求解 LP 松弛得分数最优解；② 随机舍入得整数解；③ 分析的期望目标值与的关系（从而也关联），推出近似比。

Question 9

[EN] The LP relaxation + randomised rounding algorithm for Max-SAT seen in class gives a ____-factor approximation (in expectation).

[CN] 课上讲的 LP 松弛 + 随机舍入算法对 Max-SAT 给出____近似比（期望）。

选项	答案
	✅
	❌
	❌
	❌

知识点：Theorem 49：对个文字的子句，满足概率。故 LP 舍入给出近似。结合朴素随机的近似，两者取最优（Theorem 50）可达近似。

Question 10

[EN] The LP relaxation + randomised rounding algorithm for Min-CUT seen in class gives a ____-factor approximation (in expectation).

[CN] 课上讲的 LP 松弛 + 随机舍入算法对 Min-Cut 给出____近似比（期望）。

选项	答案
	❌
	❌
	✅
	❌

知识点：Theorem 47：Min-Cut 的 LP 松弛 + 随机舍入以概率 1 给出最优解（精确算法），近似比为 1。原因是 Min-Cut LP 松弛极其特殊——最优分数解可直接被随机舍入到最优整数解，期望值。

Week 10 Quiz 速查表

题号	核心概念	正确答案
1	LP 定义	linear/linear
2	LP 多项式可解	True
3	ILP 定义	False（变量整数，非目标函数）
4	ILP 可解	False（NP-Hard）
5	P LP	True
6	非 NP-Hard 也可 ILP	False
7	LP 松弛解 ILP 解	True
8	Rounding 三阶段	LP/ILP/LP
9	Max-SAT 近似比
10	Min-Cut 近似比	（精确）

高频混淆点： - ILP 要求变量整数，不是目标函数（Q3）——容易误理解定义 - ILP NP-Hard，LP 多项式时间（Q2 vs Q4）——两者差距是核心 - Max-SAT LP 舍入，结合朴素随机后 （Q9）——注意两个近似比都要记 - Min-Cut LP 舍入是精确的（近似比 = 1）（Q10）——特殊性质