LP-Relaxation

Definition / 定义

LP-relaxation（线性规划松弛）：在优化问题中，把原本要求为整数/离散的变量约束（如 (x \in {0,1}) 或 (x \in \mathbb{Z})）放宽为连续约束（如 (0 \le x \le 1) 或 (x \in \mathbb{R})），从而得到一个线性规划（LP）问题。它通常更容易求解，并常用于提供下界/上界、构造近似算法或作为分支定界等方法的基础。（该术语在一些语境下也可泛指“把难问题放宽成更易解的线性规划”的做法。）

Pronunciation / 发音

/ˌɛlˈpiː ˌriːlækˈseɪʃən/

Examples / 例句

We solved the LP-relaxation to get a quick lower bound.
我们先求解线性规划松弛，以快速得到一个下界。

Although the LP-relaxation is easy to solve, its solution may be fractional and must be rounded to form a valid integer solution.
尽管线性规划松弛容易求解，但它的解可能是分数，需要经过取整/舍入才能得到有效的整数解。

Etymology / 词源

LP 是 Linear Programming（线性规划） 的缩写；relaxation 在优化与数学中指“放宽约束”。合起来，LP-relaxation 就是“通过放宽（通常是整数性等）约束，把问题变成线性规划”的方法与结果。

Related Words / 相关词

• Linear Programming
• Integer Programming
• Mixed-Integer Programming
• Convex Optimization
• Feasible Region
• Duality
• Branch-and-Bound
• Cutting Plane
• Integrality Gap
• Lagrangian Relaxation

Literary Works / 文学与著作例证

• Integer and Combinatorial Optimization（Nemhauser & Wolsey）：系统讨论整数规划与各种松弛（含 LP 松弛）在界与算法中的作用。
• Theory of Linear and Integer Programming（Alexander Schrijver）：从理论角度深入讲解线性/整数规划与多面体方法，LP 松弛是核心概念之一。
• Approximation Algorithms（Vijay V. Vazirani）：多处使用 LP-relaxation 与对偶性来设计并分析近似算法。
• The Design of Approximation Algorithms（Williamson & Shmoys）：以大量实例展示如何用 LP 松弛与舍入得到近似解。
• Convex Optimization（Boyd & Vandenberghe）：讨论“松弛”作为把难问题转化为可解凸问题/线性问题的常见策略（与 LP 松弛相关）。