線性規劃鬆弛（LP relaxation）

許多困難的組合問題本質上關於是非選擇：要不要納入這個頂點、要不要選這個集合、要不要用這條邊。寫成數學，每個決定是一個被迫取 0 或 1 的變數，而「必須是 0 或 1」這個約束正是讓問題變成 NP 困難的元兇。線性規劃鬆弛做的是一件「故意作弊」的動作：它把那個整數性要求「鬆開」，讓每個變數可以是 0 到 1 之間的任何實數。所得的分數問題是一個線性規劃，我們能在多項式時間內求得最佳解。

以頂點覆蓋示範這套手法。給每個頂點 i 一個變數 x_i。我們要最小化 x_i 之和（被選頂點的數目），受限於：對每條邊 (i, j)，x_i + x_j >= 1（每條邊都必須有一個被選端點），且 x_i 屬於 {0, 1}。最後那個約束讓它成為整數規劃，NP 困難。鬆弛只是把 x_i 屬於 {0,1} 換成 0 <= x_i <= 1。現在它是線性規劃——線性目標、線性不等式、連續變數——而線性規劃能被高效求解。一個頂點現在可以被「選一半」（x_i = 0.5），這在物理上沒有意義，但數學上沒問題。關鍵而可靠的事實是：因為鬆弛允許「更多」的解（每個整數解仍被允許，外加分數解），它的最佳值只可能更好或相等。所以對最小化問題，LP-OPT <= 整數-OPT——鬆弛的值是真正最佳值的一個可計算下界。

那個下界就是鬆弛的全部理由。它遞給你一個具體、多項式時間算出的數，讓你拿演算法去比——和別處由匹配、MST 扮演的「OPT 替身」角色相同，但現在由一個完全通用、機械化、幾乎適用於任何你寫得出來的 0/1 問題的方法產生。代價是 LP 的答案通常是分數，因而不是真實解；你還得把那些分數轉回誠實的 0/1 決定，那正是捨入的工作。LP-OPT 與整數-OPT 之間的差距（整數性差距）限制了任何捨入能做到多好，本身也是一個深刻的研究對象。