有些線性規劃的變量多得難以逐一列出,但每個變量的意義都很簡單。在切割備料問題中,一個變量表示採用某個單條原料切割方案的次數。可行方案可能很多,實際解通常只用其中少數。列生成先以一小部分方案求解,再用另一個優化問題判斷是否有值得加入的方案。停止的證據來自對偶性,而不是因為我們暫時想不到其他方案。
以下假設模式集合有限且計算精確;重要限制會在文中說明。
動機
假設每條原料長 10,產品長度分別是 3 和 4。一條原料可以切成三件第一類、兩件第二類,或兩件第一類加一件第二類。模式記錄單條原料產生的各類件數。這個小例子可以枚舉所有模式,但當類別和原料長度增加時,枚舉可能很繁重。我們希望有嚴謹方法挑選模式,而無須預先猜對哪些有用。
定義
設 是有限、非空的模式集合。模式 產生非負向量 ,成本為 。對需求 ,考慮完整主問題
這裏容許 為分數;若它表示原料條數,這就是整數問題的鬆弛。不等式容許超額生產;若要求生產量恰好等於需求,對偶變量的符號限制便不同。
對非空子集 ,受限主問題只保留 中的變量。將其餘變量設為零,可把受限可行解延伸為完整主問題的可行解。受限問題的對偶是
對候選對偶向量 ,模式的約化成本為 。定價問題是在所有 上最小化 。這是另一個優化問題,不能只檢查已在 中的模式。
定理與命題
定理 17.1.1
(定價給出的全局證書)
假設受限主問題可行,且取得有限最優值。設 分別是其原始和對偶最優解。若每個 均滿足 ,則將 的其餘分量補零後得到 (1) 的最優解,且 是完整對偶的最優解。
證明與思路
證明
(弱對偶補上受限問題留下的缺口)
受限對偶可行性給出 。定價條件補上所有遺漏的不等式 ,因此 對完整對偶可行。對任何完整主問題可行解 ,由非負性得到
這直接證明弱對偶。受限主問題可行且最優值有限,線性規劃強對偶性給出 的目標值等於 。補零後的解對完整主問題可行,並達到剛得到的下界,因此兩者分別為完整原始問題和對偶問題的最優解。此證書涵蓋整個線性規劃,卻不保證分數解是整數解。
證明透視
定價究竟證明甚麼
受限原始解也是完整問題的可行解,所以其值是完整最小值的上界。受限對偶解可能違反某個遺漏列的不等式,未必對完整對偶可行。定價正是檢查所有缺失的不等式;若沒有違反,同一個數亦是下界,兩個界便相等。
命題 17.1.2
(有限模式下的有限列生成)
假設 有限、所有成本 非負、初始受限主問題可行,且每次都精確求解受限主問題。每一輪選取受限對偶最優解 並精確求解定價:若最小約化成本為負,加入一個達到該最小值的模式;否則停止。此程序經有限次加列後停止,並給出完整主問題的最優解與對偶證書。
證明
(從有限集合中加入互不相同的模式)
由 對受限對偶可行, 中的模式都不會有負約化成本。因此每次加入的模式均為新模式,最多加入 次。之後每個受限問題仍可行,因為原解仍可使用;成本和變量均非負,目標值以下界零限制。由線性規劃最優值存在定理,每輪均取得有限最優值。停止時,精確定價檢查了完整對偶的所有不等式,上述定理便給出結論。
非負成本確保每輪的最優值有限;更一般的成本需要另外證明有界。加入負約化成本的列後,下一輪最優目標值不一定嚴格下降:退化可能使其不變。這裏的有限終止依靠每次加入不同的列,並非依靠目標值嚴格下降。
例題詳解
例題 17.1.3
(兩類產品和一個有用的遺漏模式)
長度為 10 的原料每條成本為 1,兩類產品長度為 3 和 4,需求為 。模式 的分量是非負整數且滿足 。先取 ,受限主問題為
其最優解為 ,值為 。對偶最優解是 ,因為 、。定價即在整數 和 下最大化 。 只可能是 0、1、2;分別得到最大值 、、。因此 的約化成本為 ,應加入該模式。
加入後,使用兩次模式 ,恰好滿足需求,值為 2。為證明最優,取 。當 時,所有模式中 的最大值分別是 。因此每個模式的對偶值都不超過其單位成本, 對完整對偶可行。其目標值 ,等於上述原始解。線性規劃最優值是 2;這個解同時使用整數條原料,所以也是整數最優解。
例題 17.1.4
(分數主問題值不是原料條數)
保留相同原料和產品長度,改為每類需求一件。分數方案 、 滿足兩類需求,成本為 。對偶向量 對所有模式仍可行,目標值亦為 ,故這是線性規劃最優值。整數最優值則為 1:一條 已滿足需求,且任何整數可行解至少使用一條。把兩個分數變量各自向上取整恰好使用兩條,並非最優。
例題 17.1.5
(零需求與不唯一的受限對偶解)
保留相同原料和模式,需求改為 ,並再次由 開始。受限主問題是在 、、 下最小化 ,最優解為 ,值為 1。其對偶是在 、、 下最大化 ,所以每個 ()都是最優解:零需求令 無法確定。
取 時,定價在所有模式上最大化 ,最大值是 的 1,所有約化成本非負,完整線性規劃最優值被證明為 1。若改取 ,模式 的約化成本是 。加入它並不降低受限最優值:只用 需要 ,成本為 ,所以最優值仍是 1。負約化成本反映的是所選的對偶解,而加入模式也未必嚴格改善目標值。
常見錯誤
反例模式
受限最優不代表完整最優
第一個例子中,使用最初兩種模式的最優值是 ,但遺漏的 有負約化成本,完整問題存在兩條原料的解。因此受限問題已求至最優,仍不能單獨證明全局最優。反過來說,負約化成本表示所選對偶證書失效,並不保證下一個受限目標值嚴格下降。
常見錯誤
(把定價啟發式找不到模式當作證書)
定價啟發式可以找到有用模式;但它找不到模式,不能證明所有約化成本非負。精確定價,或最小約化成本的一個非負的有效下界,才提供所需證書。約化成本取決於所選的對偶最優解;另一個對偶最優解可能給出不同的約化成本。第三個例題正好展示這種依賴。
快速檢查
快速檢查
(為甚麼受限目標值是完整最小值的上界?)
解答 · 答案
因為將所有遺漏變量設為零,任何受限可行方案仍對完整主問題可行。對最小化問題增加選擇不會令最優值上升。
習題
快速檢查
(對上述長度為 10 的模式,判斷 是否對完整對偶可行;若否,明確指出違反的不等式。)
解答 · 答案
不可行。 滿足 ,但其對偶不等式要求 ,顯然不成立。
快速檢查
(需求為 時,驗證分數最優值 和整數最優值 1,不要假設取整一定能求解整數問題。)
解答 · 答案
第二個例子的分數解與達到相同值的可行對偶解證明線性規劃值為 。一條 已滿足需求,而正需求排除零條原料,因此整數值為 1。
快速檢查
(若受限最優值為 9,其對偶向量在所有模式上的最小約化成本為 0,完整線性規劃最優值是多少?整數最優值必定為 9 嗎?)
解答 · 答案
由定價證書和受限原始、對偶目標值相等,完整線性規劃值為 9。若沒有成本為 9 的整數可行方案或進一步整數分析,不能斷言整數值為 9;它可能更大,如第二個例子所示。
快速檢查
(若只近似求解定價,抽查所得最小約化成本為 ,這能證明完整線性規劃最優嗎?還需要甚麼事實?)
解答 · 答案
不能。未檢查的模式可能有負約化成本。若能嚴謹證明所有模式上的最小值下界至少為零,或精確求得全局最小值非負,便足以證明。