線性規劃的鬆弛

A (general) integer program and its LP-relaxation

在數學中，0-1整數規劃的線性規劃的鬆弛是這樣的問題：把每個變量必須為0或1的約束，替換為較弱的每個變量屬於區間[0,1]的約束。

也就是說，對於原整數規劃的每個下列形式的約束：

$x_{i}\in \{0,1\}$

我們轉而使用一對線性約束來代替：

$0\leq x_{i}\leq 1.$

這樣產生的鬆弛是線性規劃，因此得名線性規劃的鬆弛。這種鬆弛技術把NP難的最優化問題（整數規劃）轉化為一個相關的多項式時間可解的問題（線性規劃）。我們可以用鬆弛後的線性規劃的解來獲得關於原整數規劃的解的信息。

例子

考慮集覆蓋問題，該問題的線性規劃鬆弛最先由Lovász (1975)詳細研究。在該問題中，給定輸入為一族集合F = {S₀, S₁, ...}；任務是找到其中的一個集合數量儘可能少的子族，其併集也是F。

若想把該問題形式化為0-1整數規劃，對每個集合S_i構造一個指示變量x_i，它取值為1當S_i屬於所選子族時，取0當其不屬於。那麼一個有效的覆蓋可由一個滿足下列約束的對指示變量的賦值來描述：

$\textstyle x_{i}\in \{0,1\}$

（即只允許指定的指示變量值）並且，對於每個併集F的元素e_j：

$\textstyle \sum _{\{i\mid e_{j}\in S_{i}\}}x_{i}\geq 1$

（即覆蓋每個元素）。最小的對應指示變量賦值的集覆蓋滿足這些約束且最小化線性目標函數：

$\textstyle \min \sum _{i}x_{i}.$

這個集覆蓋問題的線性規劃鬆弛描述了一個分數覆蓋，其中輸入集被賦予權值，使得包含每個元素的這些集合的總權值至少是1，且所有集合的總權值最小。

對精確解的分支定界

在近似理論中，線性規劃的鬆弛也有應用。線性規劃在計算困難的最優化問題的最優解時的分支定界算法中也扮演著重要角色。

割平面方法

兩種有著相同的目標函數和相同的可行解集因而等價的整數規劃，可能有著非常不一樣的線性規劃鬆弛：一種線性規劃鬆弛可從幾何上視為包含了所有可行解並排除了所有其餘0-1向量的凸多面體，而且有無窮多的多面體都具有這種性質。理想情況下，我們想把可行解的凸包作為鬆弛來使用，因為這種多面體上的線性規劃將自動產生原整數規劃的正確解。儘管如此，一般情況下，這種多面體有指數多的面且難以構造。典型的鬆弛，比如我們前面討論過的集覆蓋問題的鬆弛，構造了一個嚴格包含可行解的凸包且排除可解非鬆弛問題的0-1向量的多面體。

參考文獻

• Aardal, Karen; Weismantel, Robert, Polyhedral combinatorics: An annotated bibliography, Annotated Bibliographies in Combinatorial Optimization (PDF), Wiley, 1997 [2011-05-09], （原始內容 (PDF)存檔於2016-03-03） .
• Agmon, Shmuel, The relaxation method for linear inequalities, Canadian Journal of Mathematics, 1954, 6: 382–392 [2011-05-09], （原始內容存檔於2012-02-24） .
• Dantzig, George; Fulkerson, D. R.; Johnson, Selmer, Solution of a large-scale traveling-salesman problem, Journal of the Operations Research Society of America, 1954, 2 (4): 393–410, doi:10.1287/opre.2.4.393 .
• Feige, Uriel, A threshold of ln n for approximating set cover, Journal of the ACM, 1998, 45 (4): 634–652, doi:10.1145/285055.285059 .
• Gomory, Ralph E., Outline of an algorithm for integer solutions to linear programs, Bulletin of the American Mathematical Society, 1958, 64: 275–278, doi:10.1090/S0002-9904-1958-10224-4 .
• Lovász, László, On the ratio of optimal integral and fractional covers, Discrete Mathematics, 1975, 13: 383–390, doi:10.1016/0012-365X(75)90058-8 .
• Motzkin, T. S.; Schoenberg, I. J., The relaxation method for linear inequalities, Canadian Journal of Mathematics, 1954, 6: 393–404 [2011-05-09], （原始內容存檔於2012-02-24） .
• Raghavan, Prabhakar; Thompson, Clark D., Randomized rounding: A technique for provably good algorithms and algorithmic proofs, Combinatorica, 1987, 7 (4): 365–374, doi:10.1007/BF02579324 .
• Young, Neal E., Randomized rounding without solving the linear program, Proc. 6th ACM-SIAM Symp. Discrete Algorithms (SODA): 170–178, 1995 .