查看“︁线性规划的松弛”︁的源代码

[[File:IP_polytope_with_LP_relaxation.png|right|thumb|300px|A (general) [[integer program]] and its LP-relaxation]]
在数学中，[[0-1整数规划]]的'''线性规划的松弛'''是这样的问题：把每个变量必须为0或1的约束，替换为较弱的每个变量属于[[区间]][0,1]的约束。

也就是说，对于原整数规划的每个下列形式的约束：
:<math>x_i\in\{0,1\}</math>
我们转而使用一对线性约束来代替：
:<math>0 \le x_i \le 1.</math>

这样产生的松弛是[[线性规划]]，因此得名线性规划的松弛。这种[[松弛技术 (数学)|松弛技术]]把[[NP难]]的最优化问题（整数规划）转化为一个相关的[[多项式时间]]可解的问题（线性规划）。我们可以用松弛后的线性规划的解来获得关于原整数规划的解的信息。

==例子==
考虑[[集覆盖问题]]，该问题的线性规划松弛最先由{{harvtxt|Lovász|1975}}详细研究。在该问题中，给定输入为一族[[集合 (数学)|集合]]''F'' = {''S''<sub>0</sub>, ''S''<sub>1</sub>, ...}；任务是找到其中的一个集合数量尽可能少的子族，其[[并集]]也是''F''。

若想把该问题形式化为0-1整数规划，对每个集合''S<sub>i</sub>''构造一个[[指示变量]]''x<sub>i</sub>''，它取值为1当''S<sub>i</sub>''属于所选子族时，取0当其不属于。那么一个有效的覆盖可由一个满足下列约束的对指示变量的赋值来描述：
:<math>\textstyle x_i\in\{0,1\}</math>
（即只允许指定的指示变量值）并且，对于每个并集''F''的元素''e<sub>j</sub>''：
:<math>\textstyle \sum_{\{i\mid e_j\in S_i\}} x_i \ge 1</math>
（即覆盖每个元素）。最小的对应指示变量赋值的集覆盖满足这些约束且最小化线性目标函数：
:<math>\textstyle \min \sum_i x_i.</math>
这个集覆盖问题的线性规划松弛描述了一个''分数覆盖''，其中输入集被赋予权值，使得包含每个元素的这些集合的总权值至少是1，且所有集合的总权值最小。

==对精确解的分支定界==
在近似理论中，线性规划的松弛也有应用。线性规划在计算困难的最优化问题的最优解时的[[分支定界]]算法中也扮演着重要角色。

==割平面方法==
两种有着相同的目标函数和相同的可行解集因而等价的整数规划，可能有着非常不一样的线性规划松弛：一种线性规划松弛可从几何上视为包含了所有可行解并排除了所有其余0-1向量的[[凸多面体]]，而且有无穷多的多面体都具有这种性质。理想情况下，我们想把可行解的[[凸包]]作为松弛来使用，因为这种多面体上的线性规划将自动产生原整数规划的正确解。尽管如此，一般情况下，这种多面体有指数多的面且难以构造。典型的松弛，比如我们前面讨论过的集覆盖问题的松弛，构造了一个严格包含可行解的凸包且排除可解非松弛问题的0-1向量的多面体。

==参考文献==
* {{citation | contribution = Polyhedral combinatorics: An annotated bibliography | first1 = Karen | last1 = Aardal | first2 = Robert | last2 = Weismantel | title = Annotated Bibliographies in Combinatorial Optimization | publisher = Wiley | year = 1997 | url = http://www.cs.uu.nl/research/techreps/repo/CS-1996/1996-27.pdf | accessdate = 2011-05-09 | archive-date = 2016-03-03 | archive-url = https://web.archive.org/web/20160303225955/http://www.cs.uu.nl/research/techreps/repo/CS-1996/1996-27.pdf }}.
* {{citation | title=The relaxation method for linear inequalities | last=Agmon | first=Shmuel | journal=Canadian Journal of Mathematics | year=1954 | volume=6 | pages=382–392 | url=http://www.math.ca/cjm/v6/p382 | accessdate=2011-05-09 | archive-date=2012-02-24 | archive-url=https://web.archive.org/web/20120224031945/http://www.math.ca/cjm/v6/p382 }}.
* {{citation | title = Solution of a large-scale traveling-salesman problem | first1 = George | last1 = Dantzig | authorlink1 = George Dantzig | first2 = D. R. | last2 = Fulkerson | authorlink2 = D. R. Fulkerson | first3 = Selmer | last3 = Johnson | journal = Journal of the Operations Research Society of America | volume = 2 | issue = 4 | year = 1954 | pages = 393–410 | doi = 10.1287/opre.2.4.393}}.
* {{citation | title = A threshold of ln ''n'' for approximating set cover | journal = Journal of the ACM | year = 1998 | pages = 634–652 |volume = 45 | issue = 4 | last = Feige | first = Uriel | authorlink = Uriel Feige | doi = 10.1145/285055.285059}}.
* {{citation | first = Ralph E. | last = Gomory | authorlink = Ralph E. Gomory | title = Outline of an algorithm for integer solutions to linear programs | journal = [[Bulletin of the American Mathematical Society]] | doi = 10.1090/S0002-9904-1958-10224-4 | volume = 64 | year = 1958 | pages = 275–278}}.
* {{citation | title = On the ratio of optimal integral and fractional covers | last = Lovász | first = László | authorlink = László Lovász | journal = Discrete Mathematics | volume = 13 | pages = 383–390 | year = 1975 | doi = 10.1016/0012-365X(75)90058-8 }}.
* {{citation | title=The relaxation method for linear inequalities | last1=Motzkin | first1=T. S. | author1-link=Theodore Motzkin | first2=I. J. | last2=Schoenberg | author2-link=Isaac Jacob Schoenberg | journal=Canadian Journal of Mathematics | year=1954 | volume=6 | pages=393–404 | url=http://www.math.ca/cjm/v6/p393 | accessdate=2011-05-09 | archive-date=2012-02-24 | archive-url=https://web.archive.org/web/20120224032026/http://www.math.ca/cjm/v6/p393 }}.
* {{citation | title= Randomized rounding: A technique for provably good algorithms and algorithmic proofs|first1=Prabhakar|last1=Raghavan|first2=Clark D. |last2=Thompson|journal=Combinatorica|volume=7|issue=4|year=1987|pages=365–374|doi=10.1007/BF02579324}}.
* {{citation | contribution = Randomized rounding without solving the linear program | first = Neal E. | last = Young | title = Proc. 6th ACM-SIAM Symp. Discrete Algorithms (SODA) | year = 1995 | url = http://portal.acm.org/citation.cfm?id=313689 | pages = 170–178}}.

[[分类:线性规划]]
[[分类:松弛方法]]
[[分类:组合优化]]
[[分类:多面体组合]]