動機
通訊系統可分配半單位傳輸時間,卻不能安裝半個不可分割的中繼裝置。編譯器要決定是否啟用某項轉換,同時給已啟用工作分配連續處理時間。整數規劃把這些離散選擇寫進模型;移除整數性雖可能令計算較容易,卻改變了甚麼決策算可行。
線性鬆弛仍有作用。最大化時,允許額外分數點只會提高最佳值,因此鬆弛最優值是整數模型的上界。這是可行集包含關係的結果,不依賴某個軟件。把分數答案直接當成可實現決策,正是丟失了建整數模型的理由。
真正困難是證明沒有漏掉更好選擇。分枝定界把整數決策分成窮盡情況,再用有效上界整批排除。有效不等式則刪去分數點而保留全部整數決策。另有特殊矩陣結構保證頂點全是整數,使線性鬆弛已能解決離散問題;這種保證必須證明,不能由小例子猜出。
定義
定義 3.1.1
(整數模型、鬆弛、現有最佳解及界)
整數線性最大化問題可寫為
二元變量只可取零或一;混合整數模型只要求指定變量為整數。線性鬆弛把整數限制改成實數限制,其他條件不變。
現有最佳解必須是真正可行的整數點,其值 是最大值的下界。有效上界 必須不小於相關搜尋區域內每個可行整數目標值。
整數可行點的凸包稱為整數包。對全部整數可行點成立的線性不等式稱為有效不等式;加入它可收緊鬆弛而不改變原整數問題。要把某不等式用作割平面,必須先證明它保留每個整數決策,不能只看它是否刪去目前分數點。
概念視角幾何
整數規劃是在整數包上的線性規劃
設整數可行集 有限且非空,其整數包為 ,鬆弛多面體為 。則 是頂點都在 中的多胞形,而線性目標在 上的最大值於某個頂點取得,所以 。由於 ,鬆弛界只會更大。有效不等式恰好是在 上成立的線性不等式;每個割平面都把 推向 ,而下面的整數性定理描述的正是 的有界情況。
建模也是推理。若二元 表示是否啟用工作,而連續工作量有已知上界 ,限制 使停用時工作量為零,但不迫使啟用時工作量嚴格為正。 必須由模型推導:過小刪掉合法安排,過大則使鬆弛變弱。
整數矩陣若每個方形子矩陣的行列式都為零、正一或負一,稱為全單模。這要求檢查所有方形子式,並非只看整個矩陣的一個行列式。對本節的非空有界多面體,全部頂點都是整數便保證它等於整數點凸包,稱為整多面體。
定理/命題
命題 3.1.2
(鬆弛界為剪枝提供理由)
最大化搜尋節點若有已證明的有限鬆弛上界 ,而現有整數解值為 ,則 時此節點不能改善現有解。鬆弛不可行表示節點內沒有整數可行點。鬆弛最優點若已是整數,便同時解決該節點的整數問題。
只求一個最優解時,相等也可剪枝;若要列出全部最優解,同界節點可能藏有其他最優點,須另外處理。目標值差距也不是決策向量之間的距離。
定理 3.1.3
(全單模令基本解成為整數)
設整數矩陣 全單模且有滿行秩,右端 為整數向量。則 的每個基本可行解都是整數。若此標準形線性問題有已取得的有限最優值,便有整數最優解。
矩陣性質及整數右端缺一不可。只有整數係數並不足夠。結論也不是每個可行或最優點都為整數;整數頂點的凸組合仍可能有分數座標。
定理 3.1.4
(有向圖的關聯矩陣是全單模的)
有向圖的節點—弧關聯矩陣(每條弧在弧尾放 、在弧頭放 )是全單模的。附加單位行或單位列後仍保持全單模。
證明思路
證明
(嵌套可行集與窮盡分枝)
節點的整數可行集包含在鬆弛可行集內,故所有整數目標都不超過鬆弛最優值,也不超過其有效上界。若上界不高於已取得的整數值,便不能有改善。空的鬆弛集沒有整數子集;若鬆弛最優點恰為整數,它已在子集內取得同一上界。
若鬆弛最優點的某個指定整數座標為分數 ,每個整數座標值恰好符合以下一邊:
兩個子節點涵蓋父節點全部整數點,並排除目前分數解。完整證書需要這個窮盡分解,以及每個葉節點的關閉理由:不可行、上界足夠,或鬆弛最優點已整數。只展示搜尋過的最好點,還不是全局證明。
全部指定整數變量若有有限整數上下界,且不重複處理相同節點,這種分枝有限步終止。每次沿樹往下都把至少一個整數座標區間嚴格縮短,路徑長度受原區間寬度總和限制;分枝數有限且深度有界,樹便有限。無界整數域需要額外論證,本節不作普遍終止保證。
證明
(單模基矩陣的整數逆矩陣)
全單模定理取任意非奇異基矩陣 。其行列式為非零子式,故必為正負一。伴隨矩陣公式顯示 的每項都是整數餘因子除以正負一,因此仍是整數。 為整數,非基本座標為零。再用線性規劃的基本最優代表定理,只要線性最優值已取得,便得到整數最優點。
網絡矩陣為甚麼符合條件
證明
(對子式大小歸納)
有向圖的關聯矩陣 在弧尾放負一,在弧頭放正一。非自環弧有兩個相反非零項;自環弧的頭尾貢獻抵消,整列為零。任取方形子矩陣:若某列全零,行列式為零;若某列只有一個非零項,沿列展開降為較小子式的正負值;若每列都有兩個非零項,兩項符號相反,所有行相加為零,行列式也為零。歸納即證全單模。
證明透視
相反符號在何處被使用
歸納分三種情況,只有最後一種用到圖的結構。零列及只有一個非零項的列,對任何元素屬於 的矩陣都可處理:前者給出零行列式,後者經展開化為較小的子式。關鍵情況是方形子矩陣中每一列都保留兩個非零項。此時相反符號 與 使每列之和為零,全一的行組合消失,故行列式為零。
沒有方向時失效的正是這一步。三角形的無向關聯矩陣每列都有兩個 ,其行列式為 。證明也從未用到圖的大小或連通性,所以刪去行、附加單位行或單位列都可用同一展開處理。
刪去冗餘關聯行保留此性質,附加單位列或單位行也可用同一展開法證明。具容量的流可寫為
任一子式先沿鬆弛列展開,再沿只剩單個原變量項的容量行展開,便化為關聯子式。移除冗餘等式可得到滿行秩。因此整數供需及容量給出整數頂點;最小費用流即使用線性規劃求解,也有整數最優代表。任意新增耦合限制未必保留這個證明。
例題詳解
例題 3.1.5
(一棵附完整證書的小搜尋樹)
二元工作開關 最大化 ,限制 。鬆弛加上 ,最優點 值四;先分配給係數較大的 ,餘下半單位總額給 。
按 分枝。 時鬆弛最優為 ,產生整數現有解值三。 時 ,鬆弛上界為 。由於原整數目標係數及變量都整數,實際目標是整數,故此節點可用向下取整上界三,不能改善現有解。
兩個子節點涵蓋 的全部值,各有合法結論,故 全局最優。若沒有整數目標假設,單憑 並不能剪枝,仍需下一步分枝或更強證書。上界中的任何取整步驟都必須有自己的假設。
例題 3.1.6
(把鬆弛解向下取整仍會丟失最優值)
二元選擇滿足
鬆弛按收益與容量比 分配,得 、值 。也可獨立證明:容量乘 再加 的 倍,所得係數逐一不小於目標係數,上界為 。
向下取整給 、值七,但 可行且值八。若 ,其他兩項都放不下,值至多七;若 ,其餘兩項都可選,值至多八。這兩種窮盡情況證明整數最優值八。
項目一、二合用容量七大於五,形成覆蓋,故有效不等式 保留每個二元可行點。分數最優點的左邊為 ,因此被割去。一條覆蓋不等式未必足以描述整個整數包。
例題 3.1.7
(辨認結構性整數保證及其限制)
整數容量、整數供需的網絡流頂點由上述關聯矩陣論證保證為整數。例如單弧模型的尾端供一、頭端需一,容量至少一時,唯一可行弧流便是一。
但純量模型 最大化 ,其一階子式為二,不全單模;鬆弛頂點為半,整數最優為零。整數數據並沒有阻止分數頂點。
即使係數矩陣全單模, 的非整數右端仍給半這個分數最優值。反過來,不全單模也不表示每個右端都有差距: 最大化 時,兩個模型都以一最優。定理提供充分結構保證,不是判斷每個個別實例的必要條件。
常見錯誤
常見錯誤
(取整只是啟發式,不是證明)
向下取整只是啟發式。非負係數的容量上界模型中,它保持可行,卻不保證最優;等式、負係數或下限需求則連可行性也可能破壞。向上取整甚至可超出普通容量上限,每次都要重查實際限制。
常見錯誤
(上界必須涵蓋節點內每個整數點)
最大化的某個鬆弛可行點只提供已取得的值,不自動是上界。上界應來自已證明的鬆弛最優值、對偶可行點或有效不等式論證。中途停止的求解器所給的目前點與其已證明的界,意義並不相同。不能因分數座標「接近整數」便跳過精確條件;數值容差另須明確政策及可行性重查。
常見錯誤
(鬆弛無界不證明存在改善的整數點)
鬆弛無界也不保證整數模型有改善射線。例如指定 整數,限制 而最大化 ,鬆弛無界但整數可行集空。
有效割不能只憑排除目前觀察到的分數最優點來證明,必須保留全部整數可行點。覆蓋不等式依賴二元上界及非負容量係數;把同一公式套在不受限制的整數重數上會改變論證,並可能刪去可行解。
反例模式
整數頂點不表示每個最優點都整數
錯誤推論是全單模保證軟件回傳的任何最優點都整數。取 ,目標恆為零;矩陣全單模且兩個頂點為整數,但中點 也最優,它是兩頂點的平均。正確結論是在定理假設下存在整數基本最優點。若算法回傳最優面內點,整多面體性質本身不會把該點自動變成整數。
總結
整數限制改變可行集。鬆弛界、窮盡分枝及有效割各提供最優性證明的一部分;某些網絡矩陣直接保證整數頂點。向下取整目標界需要整數目標,基本終止證明需要有限整數域,全單模結論需要整數右端;每個假設都有實際工作。
練習
快速檢查
(第一例把目標改為 ,求鬆弛值及整數值,寫出兩種情況的完整證書。)
解答 · 答案
鬆弛容許 ,值 ,例如 達到。整數情況若 ,二元 給值至多三;若 ,容量迫使 ,也至多三。 及 都達到三,所以三是整數最優值。分數決策能達到較大鬆弛值,卻非可實現二元安排。
快速檢查
(證明背包例的 是有效覆蓋不等式。 也有效嗎?)
解答 · 答案
同選一、三用容量六大於五,所以二元可行點至多選其中一個。二、三的容量和恰為五,點 可行,卻違反第二個提議,故後者無效且會刪去真實最優解。
快速檢查
(最大化節點有已證上界 ,現有解值十一。若所有目標值整數能否剪枝?若目標另含係數二分之一的連續變量呢?)
解答 · 答案
整數目標不超過 ,只求一個最優解時可以關閉。連續項取消這個整數保證,節點可能有 等超過十一的值;單憑原上界便不能關閉。
快速檢查
(證明把鬆弛點 向下取整會違反整數需求 ,另給可行整數點。最小化時鬆弛界方向如何?)
解答 · 答案
向下取整是一,違反下限;整數二可行。最小化在更大的鬆弛集合上取最小值得到下界,實際可行整數解則提供上界。與最大化相比,偏好方向反轉,兩種界的角色也反轉。
快速檢查
(證明全單模矩陣附加一個單位列後仍全單模。為甚麼不能據此宣稱任意耦合行也安全?)
解答 · 答案
任取方形子式,不含新列時原已符合條件;含新列而其中全零時行列式為零;否則沿其唯一非零項展開,得到原矩陣較小子式的正負值,仍為零或正負一。任意耦合行可有很多非零項,這種單項展開未必適用,需要另外證明其子式性質。