LP Relaxation

定义 Definition

LP relaxation（线性规划松弛）：在优化中，把原本要求变量取整数/0-1（或其他离散约束）的模型放宽为允许变量取连续值的线性规划（LP），从而更容易求解，并常用于得到下界/上界、设计近似算法或作为分支定界、割平面等方法的基础。（该术语也可能在更广义上指“把约束放松以得到更易解的模型”。）

发音 Pronunciation (IPA)

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

例句 Examples

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

Although the LP relaxation gives a fractional solution, it helps identify which constraints are tight and guides the branch-and-bound search.
尽管线性规划松弛会给出分数解，它仍能帮助找出哪些约束是紧的，并指导分支定界搜索。

词源 Etymology

LP 是 Linear Programming（线性规划） 的缩写；relaxation 来自拉丁语 relaxare，意为“放松、松开”。在优化语境里，“relax” 指放宽约束（例如把“必须为整数”放宽为“可以为小数”）。

相关词 Related Words

• Linear Programming
• Integer Programming
• Mixed-Integer Programming
• Constraint
• Relaxation
• Feasible Region
• Bound
• Branch-and-Bound
• Cutting Plane
• Duality

文学与著作中的用例 Literary Works

• Integer and Combinatorial Optimization（Nemhauser & Wolsey）——系统讨论整数规划与其 LP relaxation 及界的作用。
• Theory of Linear and Integer Programming（Alexander Schrijver）——从理论角度使用并分析 LP relaxations。
• Introduction to Linear Optimization（Bertsimas & Tsitsiklis）——在算法与建模章节中频繁提到 LP relaxation 作为整数规划的基础工具。
• Linear Programming（Robert J. Vanderbei）——在与整数规划相关内容中提及通过 LP relaxation 获得可计算的近似与界。