動機
分數最優點指出線性鬆弛過於寬鬆之處,但拒絕該點很容易,很多不等式都辦得到。真正要求是保留每個整數可行點。割的理由必須來自整數性、行方程及變量符號,而不是只看當前答案畫一條線。
表格割使用簡單算術:整數部分加上非負變量乘係數分數部分,必須保留右端同一個分數餘數。若後者加權和非負,它就不能落在零與所需正餘數之間,因而得到當前分數基違反的不等式。
加割後,下個線性最優點仍可能分數。連續有效割可使上界下降,卻永遠不在有限步達到整數答案。要論證算法,必須指定如何選割、如何解線性問題,以及何時必須分枝。有效性與有限終止是兩份不同的數學承諾。
定義
定義 7.1.1
(分數部分與純整數表格行)
實數 的下取整為不大於它的最大整數,分數部分 。考慮
本純整數推導要求出現的每個變量,包括普通鬆弛,都為整數。目前基本點令非基本量全零、,所以違反整數性。
有理原數據若需要整數鬆弛表示,應先以正公分母乘各不等式,再加鬆弛。整數係數及整數右端配整數決策,才保證普通鬆弛整數。人工量或新連續量不因出現在表格中就自動變整數。
割平面對全部整數可行點有效,並違反某個指定鬆弛點。分枝割平面節點包含祖先限制、有效新增割及分枝變量域。最大化節點的線性值只有在最優性或另一對偶上界已證明後,才能作上界;任意鬆弛可行點的值不能代替它。
定理/命題
定理 7.1.2
(純整數 Gomory 分數不等式)
在上述行假設下,每個整數可行點滿足
目前非基本量全零的基本點違反它。負係數必用數學下取整,不能向零截斷。
命題 7.1.3
(聚合及取整產生有效割)
設 且 為整數,取 使 為整數行,則全部整數可行點滿足
這稱為聚合取整或 Chvátal–Gomory 不等式。對上界限制,聚合乘數必非負。
定理 7.1.4
(一組足夠的有限分枝割平面策略)
指定整數變量都有有限整數上下界,每個處理的節點線性問題不可行或有已取得的有限最大值。每節點只用有效割,在關閉或分枝前只產生有限個割,並以有限終止精確方法解線性子問題。按分數整數座標的下取整/上取整析取分枝,最終處理所有存活節點,則搜尋有限終止,證明整數不可行或回傳全局最優。
在節點線性問題符合上述條件時,策略也適用於保留連續變量的混合整數模型,但純整數分數割不能因此套在連續列上。無界鬆弛需要另外有效的整數無界分析,或先假設鬆弛有界,不能單憑線性無界就宣稱節點已解決。
證明思路
證明
(同餘與非負性給出分數割)
把行中各係數與右端拆成整數、分數部分,移項得
分數加權和非負,且與右端有同一個嚴格介於零與一的餘數,所以最小非負可能值就是該餘數。這證明割。當前非基本量全零,左邊加權和為零,小於正右端,故確實分離目前點。
負係數沒有障礙,例如 而非負半。連續變量卻破壞關鍵步:整數係數乘連續值未必整數,原來同餘關係便不成立。這正是不能把純整數公式直接當混合整數公式的理由。
證明透視
每個假設在分數割中的位置
記 。證明有三個輸入和一個收尾步驟。每個變量都是整數,使 為整數;連續列破壞的正是這一步,下面的反例會說明。下取整的約定使每個 都在 內,再加上變量非負,便得 。收尾步驟把這些與 結合:整數 大於 ,所以至少為 。
假設 只用於分離。若餘數為零,不等式便是 ,有效卻無用。分離本身不需要任何關於整數點的事實:目前基本解的每個非基本座標都是零,所以 。
證明
(非負聚合與整數取整)
聚合定理以非負乘數相加得 。左邊已知為整數,所以不超右端下取整。證明不用最優表格或特定目標。有效割也可能不違反目前點;這時它雖合法,卻沒有分離該點。
證明
(有限樹上的覆蓋與現任解不變量)
有限搜尋維持兩個不變量:每個原整數可行點仍被某個活節點涵蓋,除非已由有效關閉證書處理;每個現有最佳解都是真正整數可行點。有效割保留前者,兩邊分枝覆蓋父域;不可行、整數鬆弛最優及足夠上界則合法關閉。
沿樹往下,每個分枝使至少一個整數區間嚴格縮短一個整數單位,深度不超原區間寬度總和,故二元樹有限。每節點有限割與有限線性求解給有限工作。所有節點關閉後,不變量保證沒有更佳整數點;若未找到任何可行整數點,便證不可行。
搜尋必須最終處理全部活節點。即使抽象樹有限,若安排方式永遠重做無關工作,仍不構成終止算法。某節點若無限加割,亦違反有限工作條件,即使每個割合法、每次線性求解都完成。
例題詳解
例題 7.1.5
(負表格係數貢獻正分數)
取純整數非負行
兩個非基本係數分數部分都為半,因 。割為 ,即 。
鬆弛基 被刪去;整數點 及 都滿足行及割。把負係數的分數部分錯當負數,就得到不受證明支持的另一式,並非容許的軟件慣例。
例題 7.1.6
(兩個有效割的強度不同)
最大化 ,限制 , 非負整數。鬆弛最優 值 。各限制乘三分之一再相加得 ,左端整數,故割 。點 都達二,完整關閉目標差距。
另引整數鬆弛 ,基本行為
標準左邊係數是 ,分數部分均 。分數割為 ,即鬆弛和至少半。由 ,直接線性形式是 。它有效且刪舊解,卻弱於聚合割二;不能聲稱每個分數割一步都封住全部差距。
概念視角代數
分數割其實是聚合取整割
表格割是改頭換面的 Chvátal–Gomory 割。由 ,該行給出 ;左邊是整數,故不超過 。把它從行方程中減去,正好得到 。在上例中, 的行給出 ,代入 便回到 。
例題 7.1.7
(一般整數樹以兩個證書關閉)
最大化 ,限制 , 非負整數。容量還給 。鬆弛先用較高單位容量收益的 到三,再用 ,值十六。
分枝 或 。前者給 值十五。後者有
點 達十三,所以這是精確節點上界,低於現有十五,可關閉。兩邊覆蓋 的全部整數情況,並非只處理二元值,故十五全局最優。
反例模式
連續非基本變量不能套純整數割
設 , 非負整數、 連續。可行點 存在;純整數公式卻會以 得 ,錯刪可行點。修補是保留純整數假設,或另外推導適當混合整數不等式,不能把連續列自行宣稱整數。
有效且嚴格改善仍可不終止
最大化整數 ,原限制 ,整數最優一。依次加有效有理割 ,。第一步以後,每個新割都刪去前次鬆弛最優並嚴格改善上界,但每個有限階段最優仍分數且大於一,只在極限靠近答案。
這不反駁某個選割及字典序重優化規則完整指定的 Gomory 有限收斂定理;它反駁的是「有效加嚴格改善必有限」這個過強說法。專門純割收斂證明另需條件;本節證明的策略是限制每節點割數,再以窮盡分枝保終止。
常見錯誤
常見錯誤
(左端不是整數時把右端下取整)
只有左端已知整數,才可把上界右端下取整。有理係數乘整數變量未必整數:由 不能推出 ,否則會刪去整數點 。負聚合乘數也未必保留上界方向。兩種錯誤都可能刪掉真正最優點。
常見錯誤
(加割後沿用舊的原始比值檢驗)
新割可令舊原始基不可行,即使整數模型未變。重優化須恢復原始或對偶不變量,不能不檢查可行性就沿用舊比值檢驗。精確的線性規劃終止可由第一階段及前一單元的防循環規則提供。
常見錯誤
(沒有目標格點便以小差距關閉節點)
小目標差距不等於精確關閉,除非已證目標值落在可用取整的格點;連續目標項可以取消這保證。數值容差與係數尺度另須分析。
總結
分數割由同餘及非負性而來;聚合割由非負組合再用整數取整而來。兩者都要明確假設,強度也不同。有限搜尋另外需要有界整數域、每節點有限割工作、終止精確線性求解及完整處理;單有有效性並不足夠。
練習
快速檢查
(從純整數行 推導分數割。)
解答 · 答案
分數部分為 ,因 ;右端餘數 。故 ,即 ,非基本量全零時確實違反。
快速檢查
(對整數 的限制 ,聚合得到 的有效界,與分數交點比較。)
解答 · 答案
各乘四分之一相加得 ,再用左端整數得 。分數交點 被刪去; 達二,所以在另加非負性時同樣證明最大和二。
快速檢查
(一般整數例把 明寫出來,會否刪去根節點分數解?)
解答 · 答案
不會。點 已滿足此界。它是證有限域的有效限制,卻不分離目前點;有效、分離及強度是不同性質。
快速檢查
(給一維不終止割例一個有限搜尋策略,指出原割序列缺少哪項假設。)
解答 · 答案
最多作固定有限次割,然後對分數 分成 與 。後者與原上界矛盾,前者取得整數最優一。原序列缺少分枝前有限工作規則,即使整數域有界、每個後續割嚴格改善也不夠。