1. 從“分蛋糕”到“做決策”整數(shù)規(guī)劃到底是什么如果你曾經(jīng)遇到過這樣的問題公司有5個(gè)項(xiàng)目但預(yù)算只夠啟動(dòng)其中3個(gè)怎么選才能讓總收益最大或者物流中心需要向10個(gè)城市送貨每輛車的裝載量有限如何安排最少的車輛跑完所有路線再或者學(xué)校排課如何把有限的教室和老師在互不沖突的時(shí)間段里安排給不同的班級(jí)這些問題背后都有一個(gè)共同的數(shù)學(xué)靈魂在起作用——那就是整數(shù)規(guī)劃。簡(jiǎn)單來說整數(shù)規(guī)劃是數(shù)學(xué)規(guī)劃的一個(gè)分支。你可以把它想象成我們熟悉的“線性規(guī)劃”加上了“整數(shù)”的緊箍咒。在線性規(guī)劃里你的決策變量比如生產(chǎn)多少產(chǎn)品、分配多少資源可以是任意實(shí)數(shù)比如生產(chǎn)3.14臺(tái)機(jī)器、分配2.5噸原料這在數(shù)學(xué)上完全可行。但在現(xiàn)實(shí)世界里很多決策必須是整數(shù)你不能雇傭半個(gè)員工不能購買半架飛機(jī)不能開設(shè)半家門店。當(dāng)這些決策變量被強(qiáng)制要求取整數(shù)值0, 1, 2, 3...時(shí)線性規(guī)劃就升級(jí)成了整數(shù)規(guī)劃。其中有一種特例極為常見且強(qiáng)大那就是0-1整數(shù)規(guī)劃。這里的變量只能取0或1代表了“是”或“否”、“選”或“不選”的二元決策。文章開頭提到的項(xiàng)目選擇問題就可以為每個(gè)項(xiàng)目定義一個(gè)0-1變量選這個(gè)項(xiàng)目變量就等于1不選就等于0。這種模型天生就是為了處理“選擇”、“指派”、“覆蓋”這類離散決策而生的。所以整數(shù)規(guī)劃的核心價(jià)值就在于它將數(shù)學(xué)的嚴(yán)謹(jǐn)性與現(xiàn)實(shí)的離散性橋接了起來。它不滿足于給出一個(gè)“理論上最優(yōu)但現(xiàn)實(shí)中無法執(zhí)行”的分?jǐn)?shù)解而是執(zhí)著地尋找那個(gè)“現(xiàn)實(shí)中可行且數(shù)學(xué)上最優(yōu)”的整數(shù)解。從芯片設(shè)計(jì)中的電路布局、航空公司機(jī)組排班、金融領(lǐng)域的投資組合優(yōu)化選擇哪些股票、買多少手手?jǐn)?shù)必須是整數(shù)到能源系統(tǒng)的發(fā)電機(jī)組啟停調(diào)度整數(shù)規(guī)劃的身影無處不在。它是一位沉默的“最優(yōu)解架構(gòu)師”在無數(shù)個(gè)離散的可能性中為我們找出那條最經(jīng)濟(jì)的路徑。2. 核心武器庫三類經(jīng)典整數(shù)規(guī)劃模型與建模心法理解了整數(shù)規(guī)劃是什么接下來就要看看我們手里有哪些趁手的“模型武器”。不同的現(xiàn)實(shí)問題對(duì)應(yīng)著不同結(jié)構(gòu)的數(shù)學(xué)模型。掌握這幾類經(jīng)典模型及其建模思路是把你遇到的實(shí)際問題“翻譯”成數(shù)學(xué)語言的關(guān)鍵第一步。2.1 背包問題資源約束下的最優(yōu)選擇這是最直觀的一類問題。想象你有一個(gè)容量有限的背包面前有一堆物品每個(gè)物品有自己的價(jià)值和重量。你的目標(biāo)是在不超過背包容量的前提下選出總價(jià)值最高的一組物品。這就是經(jīng)典的0-1背包問題。建模示例公司有1000萬研發(fā)預(yù)算有5個(gè)潛在項(xiàng)目。項(xiàng)目i預(yù)計(jì)收益為p_i萬元所需研發(fā)投入為c_i萬元。是否投資項(xiàng)目i用0-1變量x_i表示。決策變量x_i 1表示選擇項(xiàng)目ix_i 0表示不選。目標(biāo)函數(shù)最大化總收益Max Z Σ(p_i * x_i)。約束條件總投入不能超預(yù)算Σ(c_i * x_i) 1000。注意這是最基礎(chǔ)的背包模型。實(shí)際問題中約束可能更復(fù)雜比如項(xiàng)目間存在依賴關(guān)系選了A才能選B這可以通過添加額外的約束來實(shí)現(xiàn)例如x_B x_A。2.2 指派問題如何實(shí)現(xiàn)最佳匹配這類問題關(guān)注的是如何將一系列“任務(wù)”最有效地分配給一系列“執(zhí)行者”通常是一對(duì)一的分配。比如將不同的工作分配給不同的機(jī)器每臺(tái)機(jī)器做一項(xiàng)工作或者將不同的客戶分配給不同的銷售代表。建模示例有4項(xiàng)任務(wù)J1-J4和4名員工E1-E4。員工i完成任務(wù)j所需的時(shí)間或成本為c_{ij}。目標(biāo)是找到一種分配方案使總耗時(shí)或總成本最小且每項(xiàng)任務(wù)有且僅有一名員工負(fù)責(zé)每名員工也僅負(fù)責(zé)一項(xiàng)任務(wù)。決策變量x_{ij} 1表示將任務(wù)j分配給員工i否則為0。目標(biāo)函數(shù)最小化總成本Min Z ΣΣ(c_{ij} * x_{ij})。約束條件每個(gè)任務(wù)必須被分配一次對(duì)每個(gè)任務(wù)jΣ_i x_{ij} 1。每個(gè)員工必須被分配一個(gè)任務(wù)對(duì)每個(gè)員工iΣ_j x_{ij} 1。指派問題是整數(shù)規(guī)劃中結(jié)構(gòu)非常特殊的一類它有高效的專用算法如匈牙利算法但用通用整數(shù)規(guī)劃求解器同樣可以解決。2.3 集合覆蓋與選址問題用最少的點(diǎn)覆蓋最大的面這類問題在物流、公共服務(wù)領(lǐng)域極為常見。目標(biāo)是選擇最少數(shù)量的“設(shè)施點(diǎn)”如倉庫、消防站、5G基站使得所有“需求點(diǎn)”如客戶小區(qū)、城市街區(qū)都能在一定的服務(wù)半徑內(nèi)被至少一個(gè)設(shè)施點(diǎn)覆蓋。建模示例某市計(jì)劃新建急救中心有8個(gè)候選地點(diǎn)。需要確保全市15個(gè)主要街區(qū)中每個(gè)街區(qū)在10公里范圍內(nèi)至少有一個(gè)急救中心。已知每個(gè)候選地點(diǎn)能覆蓋哪些街區(qū)覆蓋關(guān)系可用一個(gè)0-1矩陣表示。目標(biāo)是使建設(shè)的急救中心數(shù)量最少。決策變量y_j 1表示在候選地點(diǎn)j建設(shè)急救中心否則為0。目標(biāo)函數(shù)最小化建設(shè)總數(shù)Min Z Σ y_j。約束條件對(duì)每個(gè)街區(qū)i它必須被至少一個(gè)已建設(shè)的中心覆蓋。即對(duì)所有能覆蓋街區(qū)i的候選地點(diǎn)j至少有一個(gè)y_j 1。用數(shù)學(xué)表達(dá)對(duì)每個(gè)街區(qū)iΣ_{j ∈ S_i} y_j 1其中S_i是能覆蓋街區(qū)i的所有候選地點(diǎn)集合。選址問題變體很多比如加上建設(shè)成本不同、需求點(diǎn)權(quán)重人口不同等但核心的覆蓋思想不變。2.4 建模心法從現(xiàn)實(shí)到模型的“翻譯”藝術(shù)把實(shí)際問題變成數(shù)學(xué)模型是最考驗(yàn)功力的環(huán)節(jié)。這里有幾個(gè)我總結(jié)的心得定義變量是關(guān)鍵的第一步首先要問自己需要做出哪些決策這些決策中哪些必須是整數(shù)通常選擇、數(shù)量、順序、指派關(guān)系都需要用整數(shù)變量來刻畫。對(duì)于數(shù)量用一般整數(shù)變量對(duì)于是否用0-1變量。目標(biāo)要單一且可量化目標(biāo)函數(shù)通常是最小化成本、時(shí)間、距離或者最大化利潤、覆蓋率、滿意度。確保目標(biāo)是能用決策變量的線性組合表達(dá)的。如果有多目標(biāo)需要將其轉(zhuǎn)化為單目標(biāo)例如使用加權(quán)和法或者將其中一個(gè)目標(biāo)設(shè)為約束。約束是現(xiàn)實(shí)的鐐銬仔細(xì)梳理所有限制條件資源上限錢、人、時(shí)間、邏輯關(guān)系如果A則BA和B不能同時(shí)選、物理規(guī)律產(chǎn)能限制、政策要求最低服務(wù)標(biāo)準(zhǔn)等。每一個(gè)條件都要轉(zhuǎn)化為一個(gè)或多個(gè)線性不等式或等式。善用0-1變量表達(dá)復(fù)雜邏輯這是建模中最巧妙的部分。例如固定成本問題如果生產(chǎn)某種產(chǎn)品需要先支付一筆固定設(shè)備費(fèi)無論生產(chǎn)多少然后再按單位成本計(jì)費(fèi)。可以引入一個(gè)0-1變量y表示是否生產(chǎn)和一個(gè)連續(xù)變量x表示產(chǎn)量。約束可以寫成x M * y其中M是一個(gè)很大的數(shù)Big-M法。這樣如果y0則x必須為0如果y1則x可以在一個(gè)合理范圍內(nèi)取值。目標(biāo)函數(shù)中則加上固定成本項(xiàng)f * y?；コ膺x擇項(xiàng)目A和項(xiàng)目B至多選一個(gè)。約束x_A x_B 1。依賴關(guān)系選項(xiàng)目B必須先選項(xiàng)目A。約束x_B x_A。把現(xiàn)實(shí)世界的復(fù)雜關(guān)系用簡(jiǎn)潔的數(shù)學(xué)不等式編織起來這個(gè)過程本身就充滿了美感與挑戰(zhàn)。3. 算法內(nèi)功分支定界法是如何“抽絲剝繭”找最優(yōu)的模型建好了扔給求解器一會(huì)兒就出結(jié)果了。但你知道求解器在背后經(jīng)歷了怎樣一場(chǎng)“頭腦風(fēng)暴”嗎理解最核心的求解算法——分支定界法不僅能讓你在結(jié)果異常時(shí)有所洞察更能提升你建模的“算法友好性”。別被名字嚇到我們可以用一個(gè)簡(jiǎn)單的例子來還原這個(gè)過程。假設(shè)我們有一個(gè)最大化問題的整數(shù)規(guī)劃只有兩個(gè)整數(shù)變量x1和x2。第一步放松先求個(gè)“天花板”首先算法會(huì)暫時(shí)“忘記”變量必須是整數(shù)的要求把它當(dāng)作一個(gè)普通的線性規(guī)劃問題來求解。這個(gè)解稱為線性松弛解。因?yàn)榧s束變少了去掉了整數(shù)要求這個(gè)解的目標(biāo)函數(shù)值比如利潤一定不低于原整數(shù)問題的最優(yōu)值。它為我們提供了一個(gè)最優(yōu)值的“上界”對(duì)于最大化問題就像一個(gè)理想中的“天花板”。但這個(gè)解很可能不是整數(shù)解比如x12.5, x23.7。第二步分支給非整數(shù)變量“做選擇”既然x12.5不是整數(shù)我們就必須做出選擇在最終的整數(shù)解里x1要么2要么3。它不可能在2和3之間。于是我們把原問題**分解分支**成兩個(gè)子問題子問題1在原問題基礎(chǔ)上增加約束x1 2。子問題2在原問題基礎(chǔ)上增加約束x1 3。 這樣我們就把那個(gè)討厭的非整數(shù)解x12.5從這兩個(gè)子問題的可行域中排除出去了。這兩個(gè)子問題覆蓋了原問題所有可能的整數(shù)解且互不重疊。第三步定界與剪枝高效排除“差生”對(duì)每個(gè)新生成的子問題我們繼續(xù)求解它的線性松弛問題。這時(shí)會(huì)出現(xiàn)幾種情況松弛問題無解那么這個(gè)子問題下肯定也沒有整數(shù)解整個(gè)分支可以剪掉丟棄。松弛解是整數(shù)解太棒了我們找到了原問題的一個(gè)可行整數(shù)解。它的目標(biāo)值記為我們目前找到的“下界”對(duì)于最大化問題也就是我們目前掌握的“地板”。松弛解的目標(biāo)值 當(dāng)前下界即使這個(gè)子問題未來能找到整數(shù)解其目標(biāo)值也不會(huì)比我們已經(jīng)掌握的“地板”更好了對(duì)于最大化問題。那么這個(gè)分支也沒有繼續(xù)探索的價(jià)值剪掉。松弛解非整數(shù)且目標(biāo)值 當(dāng)前下界這個(gè)分支還有潛力可能藏著更好的整數(shù)解。我們把它放回待探索列表等待后續(xù)繼續(xù)對(duì)它進(jìn)行分支比如再選一個(gè)非整數(shù)變量x2來分。第四步迭代直到“天花板”碰到“地板”算法會(huì)不斷地從待探索列表中選取一個(gè)子問題進(jìn)行分支、求解松弛、定界和剪枝。這個(gè)過程就像在一棵不斷生長的決策樹上進(jìn)行搜索。上界所有待探索子問題的松弛解目標(biāo)值中最大的那個(gè)就是全局上界。下界我們目前找到的所有可行整數(shù)解中目標(biāo)值最好的那個(gè)就是全局下界。隨著搜索進(jìn)行上界會(huì)不斷下降因?yàn)榉种г黾蛹s束下界會(huì)不斷上升因?yàn)檎业礁玫恼麛?shù)解。當(dāng)全局上界和全局下界的差距縮小到我們?cè)O(shè)定的精度范圍內(nèi)時(shí)搜索就可以停止了。此時(shí)我們持有的那個(gè)“下界”對(duì)應(yīng)的整數(shù)解就是問題的最優(yōu)解或非常接近最優(yōu)。為什么這個(gè)方法有效它避免了暴力枚舉所有可能的整數(shù)組合那是指數(shù)級(jí)爆炸的。通過求解松弛問題它能快速評(píng)估一個(gè)分支的“潛力”上界并及時(shí)把沒有希望的分支剪掉極大地縮小了搜索范圍。這就像在迷宮中你總是先站在高處松弛解望一眼如果這條路盡頭的房間上界看起來還不如你手里已經(jīng)找到的寶藏下界好那這條岔路根本就不用進(jìn)去搜了。在實(shí)際使用求解器時(shí)我們雖然不直接操控這個(gè)過程但理解它有助于我們解讀日志當(dāng)求解器輸出“Gap 0.01%”時(shí)你就知道它已經(jīng)找到了一個(gè)解并且證明了不存在比它好過0.01%的其他解。優(yōu)化模型一個(gè)“緊”的線性松弛即松弛解離整數(shù)解很近能極大地加速求解。這意味著你的模型 formulation 很好分支定界效率會(huì)很高。處理超時(shí)如果時(shí)間有限可以設(shè)置一個(gè) Gap 容忍度比如5%讓求解器找到一個(gè)“足夠好”的解就停止而不必追求絕對(duì)最優(yōu)。4. 實(shí)戰(zhàn)用PythonPuLP求解一個(gè)投資組合問題理論說得再多不如親手跑一遍代碼來得實(shí)在。我們用一個(gè)具體的投資組合優(yōu)化問題來演示如何從建模到求解走完全流程。我們將使用Python和一個(gè)非常友好的優(yōu)化建模庫——PuLP。問題描述假設(shè)你是一個(gè)投資者有100萬資金。市場(chǎng)上有5支股票S1-S5可供選擇。每支股票有一個(gè)預(yù)期的年化收益率r_i一個(gè)風(fēng)險(xiǎn)系數(shù)risk_i這里為簡(jiǎn)化假設(shè)風(fēng)險(xiǎn)可用系數(shù)量化以及一個(gè)最低起購金額min_i。此外出于分散風(fēng)險(xiǎn)考慮你規(guī)定最多選擇3支股票。如果選擇了高風(fēng)險(xiǎn)risk_i 5的股票S2則必須同時(shí)選擇一支低風(fēng)險(xiǎn)risk_i 3的股票S1作為對(duì)沖。每支股票的投資金額必須是其最低起購金額的整數(shù)倍。我們的目標(biāo)是在滿足上述所有約束的前提下最大化投資組合的預(yù)期總收益。步驟1環(huán)境準(zhǔn)備與數(shù)據(jù)定義首先確保安裝了pulp庫pip install pulp。然后我們定義問題數(shù)據(jù)。import pulp # 定義股票數(shù)據(jù) (名稱 收益率% 風(fēng)險(xiǎn)系數(shù) 最低起購金額-萬元) stocks { S1: {return: 8, risk: 2, min_lot: 10}, S2: {return: 15, risk: 6, min_lot: 20}, S3: {return: 10, risk: 4, min_lot: 15}, S4: {return: 12, risk: 5, min_lot: 25}, S5: {return: 9, risk: 3, min_lot: 30}, } total_capital 100 # 總資金 100萬元 max_stocks_to_choose 3步驟2建立整數(shù)規(guī)劃模型我們用PuLP來聲明問題、變量、目標(biāo)和約束。# 1. 創(chuàng)建問題實(shí)例指定為最大化問題 prob pulp.LpProblem(Stock_Investment_Portfolio, pulp.LpMaximize) # 2. 定義決策變量 # 變量 x_i: 是否選擇股票i (0-1變量) x {i: pulp.LpVariable(fx_{i}, catBinary) for i in stocks} # 變量 y_i: 購買股票i的份數(shù) (正整數(shù)變量份數(shù)投資金額/最低起購金額) y {i: pulp.LpVariable(fy_{i}, lowBound0, catInteger) for i in stocks} # 3. 定義目標(biāo)函數(shù)最大化總收益 # 總收益 Σ (收益率 * 最低起購金額 * 購買份數(shù)) prob pulp.lpSum([stocks[i][return]/100.0 * stocks[i][min_lot] * y[i] for i in stocks]) # 4. 定義約束條件 # 4.1 資金約束總投資額不超過總資金 prob pulp.lpSum([stocks[i][min_lot] * y[i] for i in stocks]) total_capital # 4.2 邏輯約束只有選擇了股票i (x_i1)才能購買它 (y_i1)。同時(shí)購買份數(shù)不能超過一個(gè)很大的數(shù)M這里用資金上限估算 M total_capital // min([data[min_lot] for data in stocks.values()]) # 一個(gè)足夠大的整數(shù) for i in stocks: prob y[i] M * x[i] # 如果x_i0, 則y_i必須為0如果x_i1, y_i可以M prob y[i] 1 * x[i] # 如果x_i1, 則y_i至少為1份 # 4.3 選擇股票數(shù)量上限 prob pulp.lpSum([x[i] for i in stocks]) max_stocks_to_choose # 4.4 邏輯依賴約束如果選擇高風(fēng)險(xiǎn)S2 (x_S21)則必須選擇低風(fēng)險(xiǎn)S1 (x_S11) prob x[S2] x[S1] # 4.5 可選每支股票購買份數(shù)上限例如不超過5份 for i in stocks: prob y[i] 5步驟3求解并分析結(jié)果現(xiàn)在我們把問題丟給求解器PuLP會(huì)自動(dòng)調(diào)用它找到的求解器如CBC。# 求解問題 solver pulp.PULP_CBC_CMD(msgFalse, timeLimit30) # 安靜模式最多計(jì)算30秒 prob.solve(solver) # 打印求解狀態(tài) print(f求解狀態(tài): {pulp.LpStatus[prob.status]}) print(f最大預(yù)期總收益萬元: {pulp.value(prob.objective):.2f}) print(\n最優(yōu)投資方案) print(- * 40) total_investment 0 for i in stocks: if pulp.value(x[i]) 0.5: # 判斷是否選擇了該股票 lots int(pulp.value(y[i])) investment lots * stocks[i][min_lot] total_investment investment expected_return investment * stocks[i][return] / 100.0 print(f股票 {i}: 購買 {lots} 份 投資額 {investment} 萬元 預(yù)期收益 {expected_return:.2f} 萬元) print(- * 40) print(f總投資額: {total_investment} 萬元) print(f資金利用率: {total_investment/total_capital*100:.1f}%)步驟4解讀輸出與模型調(diào)整運(yùn)行上述代碼你可能會(huì)得到類似如下的輸出求解狀態(tài): Optimal 最大預(yù)期總收益萬元: 10.80 最優(yōu)投資方案 ---------------------------------------- 股票 S1: 購買 3 份 投資額 30 萬元 預(yù)期收益 2.40 萬元 股票 S2: 購買 2 份 投資額 40 萬元 預(yù)期收益 6.00 萬元 股票 S5: 購買 1 份 投資額 30 萬元 預(yù)期收益 2.70 萬元 ---------------------------------------- 總投資額: 100 萬元 資金利用率: 100.0%解讀與心得結(jié)果分析求解器找到了最優(yōu)解。它選擇了S1, S2, S5三支股票正好用滿100萬資金達(dá)到了約束上限。選擇S2高風(fēng)險(xiǎn)高收益的同時(shí)按規(guī)則選擇了S1低風(fēng)險(xiǎn)進(jìn)行對(duì)沖。S5作為中低風(fēng)險(xiǎn)收益的補(bǔ)充。PuLP使用技巧LpVariable的cat參數(shù)是關(guān)鍵‘Binary’表示0-1變量‘Integer’表示一般整數(shù)變量。用Big-M法y[i] M * x[i]來關(guān)聯(lián)連續(xù)整數(shù)變量和0-1變量是標(biāo)準(zhǔn)操作。M需要選得足夠大以保證當(dāng)x[i]1時(shí)y[i]能取到所有可能值但又不能太大否則會(huì)影響求解的數(shù)值穩(wěn)定性。通常取一個(gè)合理的上界如本例中用總資金估算。約束可以直接用添加到問題對(duì)象prob上非常直觀。如果求解失敗或結(jié)果奇怪檢查模型是否可行可能約束條件太嚴(yán)格互相沖突導(dǎo)致沒有解?？梢試L試逐步放松約束來排查。檢查Big-M的值如果M太小可能會(huì)錯(cuò)誤地截?cái)嗫尚薪馊绻鸐太大比如1e9可能會(huì)帶來數(shù)值計(jì)算問題導(dǎo)致求解器性能下降或結(jié)果不精確。查看求解狀態(tài)pulp.LpStatus[prob.status]如果是Infeasible不可行說明約束矛盾如果是Unbounded無界說明目標(biāo)函數(shù)可以無限大可能漏掉了關(guān)鍵約束。調(diào)整求解器或參數(shù)對(duì)于復(fù)雜問題可以嘗試換用更強(qiáng)大的商業(yè)求解器如Gurobi, CPLEX或在PuLP中設(shè)置更長的求解時(shí)間、更小的容忍間隙Gap。通過這個(gè)完整的例子你應(yīng)該能感受到將一個(gè)問題用代碼“描述”出來然后讓求解器替你完成復(fù)雜的搜索計(jì)算是一件多么高效且有成就感的事情。PuLP這樣的庫大大降低了優(yōu)化建模的門檻讓你能更專注于問題本身而非算法實(shí)現(xiàn)。5. 避坑指南整數(shù)規(guī)劃建模與求解中的常見“雷區(qū)”走過前面的路你可能已經(jīng)摩拳擦掌準(zhǔn)備用整數(shù)規(guī)劃大干一場(chǎng)了。但別急這條路雖然強(qiáng)大卻也布滿了新手容易踩進(jìn)去的坑。下面這些是我和許多同行用時(shí)間和頭發(fā)換來的經(jīng)驗(yàn)教訓(xùn)希望能幫你繞開它們。5.1 模型不可行當(dāng)約束變成“死結(jié)”這是最常見也最令人頭疼的問題之一你興沖沖地建好模型點(diǎn)擊求解結(jié)果求解器直接返回“Infeasible”不可行。這意味著在你的所有約束條件下不存在任何一個(gè)解能滿足所有要求。排查思路像偵探一樣思考逐條約束檢查法這是最笨但最有效的方法。暫時(shí)注釋掉所有約束然后一條一條地加回去每加一條就求解一次。當(dāng)某條約束加入后問題突然變得不可行那么這條約束或者它與之前約束的組合就是“罪魁禍?zhǔn)住薄Ｋ沙诜▏L試放寬一些你覺得“可能太嚴(yán)”的約束。例如把改成或把苛刻的整數(shù)約束暫時(shí)改為連續(xù)約束。如果放寬后問題變得可行那么你就找到了沖突的源頭。尋找IIS不可行沖突集高級(jí)求解器如Gurobi、CPLEX通常提供IIS功能。當(dāng)問題不可行時(shí)它可以幫你找出一組最小的、互相沖突的約束。這就像編譯器報(bào)錯(cuò)時(shí)指向具體的代碼行能極大提升調(diào)試效率。在PuLP中調(diào)用商業(yè)求解器時(shí)也可以嘗試獲取此信息。檢查數(shù)據(jù)錯(cuò)誤很多時(shí)候不可行不是模型邏輯問題而是數(shù)據(jù)輸入錯(cuò)誤。比如某個(gè)資源的需求量被誤輸入為遠(yuǎn)大于供應(yīng)量或者兩個(gè)互斥的選項(xiàng)被邏輯關(guān)系強(qiáng)制要求同時(shí)選中。仔細(xì)核對(duì)數(shù)據(jù)特別是單位是否統(tǒng)一。提示在建模初期不要一次性把約束寫得太“死”。可以先構(gòu)建一個(gè)核心的、寬松的模型確保它能出解。然后再逐步添加復(fù)雜的業(yè)務(wù)規(guī)則約束并觀察每次添加對(duì)解的影響。這是一種“增量建?！钡陌踩呗?。5.2 “維度災(zāi)難”問題規(guī)模與求解時(shí)間爆炸整數(shù)規(guī)劃是NP-Hard問題這意味著在最壞情況下求解時(shí)間隨著問題規(guī)模變量數(shù)、約束數(shù)呈指數(shù)級(jí)增長。你可能建了一個(gè)看起來不錯(cuò)的模型但一求解卻發(fā)現(xiàn)“卡死”了幾個(gè)小時(shí)都沒結(jié)果。應(yīng)對(duì)策略簡(jiǎn)化模型減少0-1變量能否用連續(xù)變量或一般整數(shù)變量替代部分0-1變量例如如果某個(gè)數(shù)量范圍不大直接用整數(shù)變量可能比用多個(gè)0-1變量組合表示更高效。收緊線性松弛好的模型公式其線性松弛的解應(yīng)該很接近整數(shù)最優(yōu)解。可以嘗試添加一些“有效不等式”來收緊可行域幫助分支定界法更快剪枝。這需要一些經(jīng)驗(yàn)和技巧。聚合約束有時(shí)多個(gè)細(xì)粒度的約束可以合并成更緊湊的表達(dá)式減少約束數(shù)量。利用問題特殊結(jié)構(gòu)你的問題是否屬于某一類特殊問題如指派問題、旅行商問題、背包問題對(duì)于這些經(jīng)典問題可能存在比通用整數(shù)規(guī)劃更高效的專用算法或啟發(fā)式算法。先用專用算法求一個(gè)優(yōu)質(zhì)解再作為初始解喂給整數(shù)規(guī)劃求解器也能加速求解。調(diào)整求解器參數(shù)與接受近似解設(shè)置時(shí)間限制對(duì)于大規(guī)模問題追求絕對(duì)最優(yōu)解可能不現(xiàn)實(shí)。設(shè)置一個(gè)合理的求解時(shí)間上限如300秒。設(shè)置容忍間隙告訴求解器找到一個(gè)與最優(yōu)解差距在1%或5%以內(nèi)的解就可以停止了。這在很多業(yè)務(wù)場(chǎng)景下是完全可接受的。提供初始解如果你能通過經(jīng)驗(yàn)或簡(jiǎn)單規(guī)則構(gòu)造一個(gè)可行的初始解將其提供給求解器可以大大縮短求解時(shí)間。分解與分層對(duì)于超大規(guī)模問題可以考慮將其分解成若干個(gè)子問題分別求解或者采用分層優(yōu)化的思路先進(jìn)行粗粒度的決策再進(jìn)行細(xì)粒度的優(yōu)化。5.3 數(shù)值穩(wěn)定性當(dāng)“Big-M”變成“Big Trouble”在建模中我們經(jīng)常使用“Big-M”法來處理邏輯條件如前文關(guān)聯(lián)x和y的約束。這個(gè)M如果選得不好會(huì)帶來嚴(yán)重的數(shù)值問題。問題如果M設(shè)置得過大比如1e9而模型中的其他系數(shù)是正常量級(jí)如1 100會(huì)造成約束矩陣的數(shù)值比例失衡。這可能導(dǎo)致求解器內(nèi)部的數(shù)值計(jì)算出現(xiàn)舍入誤差輕則求解速度變慢重則找到錯(cuò)誤的“最優(yōu)解”或者將可行問題誤判為不可行。黃金法則為每個(gè)使用Big-M的約束選擇盡可能小但足夠大的M。如何估算“足夠大”M需要保證當(dāng)邏輯條件激活時(shí)如x1關(guān)聯(lián)的變量如y能取到其所有可能的最大值。這個(gè)最大值應(yīng)該來自問題的物理或業(yè)務(wù)意義。示例在前面的投資問題中y[i]購買份數(shù)的最大值是多少它受總資金和最小起購金額限制max(y[i]) total_capital / min_lot。因此我們可以為每個(gè)股票i單獨(dú)設(shè)置M_i total_capital // stocks[i][min_lot]這比使用一個(gè)全局的巨大M要精確得多。更好的方法如果可能盡量避免使用Big-M。有時(shí)可以通過重構(gòu)模型來消除它。例如某些條件邏輯可以通過添加額外的輔助變量和約束來表達(dá)而不依賴一個(gè)很大的M。5.4 忽略對(duì)稱性求解器在“原地打轉(zhuǎn)”對(duì)稱性是指模型存在多個(gè)本質(zhì)上相同的最優(yōu)解。例如在一個(gè)選址問題中如果所有候選地點(diǎn)成本相同、覆蓋能力相同那么選擇地點(diǎn)A、B、C的方案與選擇地點(diǎn)D、E、F的方案在目標(biāo)函數(shù)值上是完全一樣的。這種對(duì)稱性會(huì)導(dǎo)致分支定界樹急劇膨脹因?yàn)榍蠼馄鲿?huì)浪費(fèi)大量時(shí)間去探索這些等價(jià)的解空間。識(shí)別與處理識(shí)別對(duì)稱性觀察你的決策變量。如果交換其中一組變量的值問題的所有約束和目標(biāo)函數(shù)值保持不變那么就存在對(duì)稱性。打破對(duì)稱性添加一些額外的約束來消除對(duì)稱解。例如在上述選址例子中我們可以強(qiáng)制要求如果選擇了某個(gè)數(shù)量的設(shè)施那么優(yōu)先選擇編號(hào)小的地點(diǎn)?？梢蕴砑蛹s束x_i x_{i1}對(duì)于按某種順序排列的候選點(diǎn)。這樣解就被“固定”在一種特定的排列上從而消除了對(duì)稱性能顯著提升求解速度。5.5 誤讀結(jié)果整數(shù)解 vs. 松弛解這是概念理解上的一個(gè)坑。初學(xué)者有時(shí)會(huì)困惑為什么我求整數(shù)規(guī)劃得到的目標(biāo)值比如最大利潤100萬比直接忽略整數(shù)約束求線性規(guī)劃得到的目標(biāo)值比如105萬要差是不是求解器出錯(cuò)了完全正常這正是整數(shù)規(guī)劃的本質(zhì)。線性松弛解因?yàn)榉潘闪思s束所以提供了一個(gè)更“樂觀”對(duì)于最大化問題的估計(jì)即最優(yōu)值的上界。整數(shù)規(guī)劃的解必須滿足所有整數(shù)約束可行域更小所以最優(yōu)值自然可能變差。這個(gè)差距被稱為“整數(shù)間隙”。建模和求解的藝術(shù)正是在于如何縮小這個(gè)間隙用可執(zhí)行的整數(shù)方案去盡可能逼近那個(gè)理想中的“天花板”。踩過這些坑你會(huì)對(duì)整數(shù)規(guī)劃有更深刻的理解。它不僅僅是一個(gè)點(diǎn)擊求解就完事的黑箱而是一個(gè)需要你精心設(shè)計(jì)模型、耐心調(diào)試參數(shù)、理性看待結(jié)果的系統(tǒng)工程。每一次對(duì)“Infeasible”的排查每一次對(duì)求解時(shí)間的優(yōu)化都是你作為建模者成長的印記。