混合整數規劃：計算決策指南

運籌學是一門使用計算機做出最佳決策的科學，已在軟件的許多領域得到應用和應用。 舉幾個例子，物流公司用它來確定從 A 點到 B 點的最佳路線，電力公司用它來確定電力生產計劃，製造公司用它來尋找工廠的最佳人員配備模式。

今天，我們將通過一個假設問題來探索運籌學的力量。 具體來說，我們將使用混合整數規劃 (MIP) 來確定假設工廠的最佳人員配置模式。

運籌學算法

在我們深入研究示例問題之前，回顧一下運籌學中的一些基本概念並了解我們今天將使用的一些工具會很有幫助。

線性規划算法

線性規劃是一種運籌學技術，用於確定數學模型中的最佳結果，其中目標和約束表示為線性方程組。 示例線性規劃模型可能如下所示：

 Maximize a + b (objective) Subject to: a <= 2 (constraint 1) b <= 3 (constraint 2)

在我們非常簡單的示例中，我們可以看到最優結果是 5，其中 a = 2 和 b = 3。雖然這是一個相當簡單的示例，但您可能可以想像一個使用數千個變量和數百個約束的線性規劃模型.

一個很好的例子可能是投資組合問題，您最終可能會得到類似下面的偽代碼：

 Maximize <expected profit from all stock investments> Subject to: <investment in the technology sector must be between 10% - 20% of portfolio> <investment in the consumer staples must not exceed investment in financials> Etc. ...

這將是相當複雜且難以通過手動或反複試驗來解決。 運籌學軟件將使用幾種算法來快速解決這些問題。 如果你對底層算法感興趣，我建議在這裡學習單純形法和內點法。

整數規划算法

整數規劃類似於線性規劃，但額外允許部分或全部變量為整數值。 雖然一開始這似乎不是一個很大的改進，但它使我們能夠解決許多單獨使用線性規劃可能無法解決的問題。

一個這樣的問題是背包問題，我們得到一組具有指定值和重量的物品，並被要求找到我們可以裝入背包的物品的最高價值組合。 線性規劃模型將無法解決這個問題，因為沒有辦法表達您可以將物品放入背包或不放入背包的想法，但您不能將物品的一部分放入背包 - 每個變量都是連續的多變的！

一個示例背包問題可能具有以下參數：

MIP 模型將如下所示：

 Maximize 5a + 7b + 2c + 10d (objective: maximize value of items take) Subject to: 2a + 4b + 7c + 10d <= 15 (space constraint)

在這種情況下，最優解是 a=0, b=1, c=0, d=1，總項的值為 17。

我們今天要解決的問題還需要整數規劃，因為工廠的員工可以安排輪班或不安排輪班——為簡單起見，您不能安排該工廠的員工輪班 2/3。

為了使整數規劃成為可能，使用了幾種數學算法。 如果你對底層算法感興趣，我建議在這裡學習切割平面算法和分支定界算法。

示例問題：調度

問題描述

今天，我們將探討一個工廠的人員配備問題。 作為工廠的管理層，我們希望盡量減少勞動力成本，但我們希望確保每個班次都有足夠的覆蓋率以滿足生產需求。

假設我們有五個班次，人員需求如下：

並且，假設我們有以下工人：

為簡單起見，讓我們暫時假設可用性和成本是唯一關心的問題。

我們的工具

對於今天的問題，我們將使用一個名為 CBC 的開源分支切割軟件。 我們將使用 PuLP 與該軟件進行交互，PuLP 是一個流行的 Python 運籌學建模庫。 您可以在此處找到有關它的信息。

PuLP 允許我們以非常 Python 的方式構建 MIP 模型，並與現有的 Python 代碼很好地集成。 這非常有用，因為一些最流行的數據操作和分析工具是用 Python 編寫的，並且大多數商業運籌學系統都需要在優化前後進行大量的數據處理。

為了展示 PuLP 的簡單性和優雅性，這裡是早期的背包問題並在 PuLP 中解決：

 import pulp as pl # declare some variables # each variable is a binary variable that is either 0 or 1 # 1 means the item will go into the knapsack a = pl.LpVariable("a", 0, 1, pl.LpInteger) b = pl.LpVariable("b", 0, 1, pl.LpInteger) c = pl.LpVariable("c", 0, 1, pl.LpInteger) d = pl.LpVariable("d", 0, 1, pl.LpInteger) # define the problem prob = pl.LpProblem("knapsack", pl.LpMaximize) # objective function - maximize value of objects in knapsack prob += 5 * a + 7 * b + 2 * c + 10 * d # constraint - weight of objects cannot exceed 15 prob += 2 * a + 4 * b + 7 * c + 10 * d <= 15 status = prob.solve() # solve using the default solver, which is cbc print(pl.LpStatus[status]) # print the human-readable status # print the values print("a", pl.value(a)) print("b", pl.value(b)) print("c", pl.value(c)) print("d", pl.value(d))

運行這個，你應該得到輸出：

 Optimal a 0.0 b 1.0 c 0.0 d 1.0

現在進入我們的調度問題！

編碼我們的解決方案

我們解決方案的編碼相當簡單。 首先，我們要定義我們的數據：

 import pulp as pl import collections as cl # data shift_requirements = [1, 4, 3, 5, 2] workers = { "Melisandre": { "availability": [0, 1, 4], "cost": 20 }, "Bran": { "availability": [1, 2, 3, 4], "cost": 15 }, "Cersei": { "availability": [2, 3], "cost": 35 }, "Daenerys": { "availability": [3, 4], "cost": 35 }, "Theon": { "availability": [1, 3, 4], "cost": 10 }, "Jon": { "availability": [0, 2, 4], "cost": 25 }, "Tyrion": { "availability": [1, 3, 4], "cost": 30 }, "Jaime": { "availability": [1, 2, 4], "cost": 20 }, "Arya": { "availability": [0, 1, 3], "cost": 20 } }

接下來，我們將要定義模型：

 # define the model: we want to minimize the cost prob = pl.LpProblem("scheduling", pl.LpMinimize) # some model variables cost = [] vars_by_shift = cl.defaultdict(list) for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable("%s_%s" % (worker, shift), 0, 1, pl.LpInteger) vars_by_shift[shift].append(worker_var) cost.append(worker_var * info['cost']) # set the objective to be the sum of cost prob += sum(cost) # set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum(vars_by_shift[shift]) >= requirement

現在我們只要求它解決並打印結果！

 status = prob.solve() print("Result:", pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ "shift": shift, "workers": [var.name for var in vars if var.varValue == 1], }) for result in sorted(results, key=lambda x: x['shift']): print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']))

運行代碼後，您應該會看到以下輸出：

 Result: Optimal Shift: 0 workers: Arya_0 Shift: 1 workers: Melisandre_1, Bran_1, Theon_1, Arya_1 Shift: 2 workers: Bran_2, Jon_2, Jaime_2 Shift: 3 workers: Bran_3, Daenerys_3, Theon_3, Tyrion_3, Arya_3 Shift: 4 workers: Bran_4, Theon_4

稍微提高難度：附加約束

儘管之前的模型很有趣且有用，但它並沒有充分展示混合整數編程的威力。 我們還可以輕鬆編寫一個for循環來為每個班次找到最便宜的x工人，其中x是一個班次所需的工人數。 為了演示如何使用 MIP 來解決以命令式方式難以解決的問題，讓我們看看如果我們添加一些額外的約束會發生什麼。

附加約束

假設，由於新的勞動法規，任何工人都不能被分配到超過 2 個班次。 為了解決工作量的增加，我們聘請了 Dothraki Staffing Group 的幫助，他們將為每班提供多達 10 名 Dothraki 工人，每班 40 美元。

另外假設，由於我們工廠外一些持續的人際衝突，瑟曦和詹姆無法與丹妮莉絲或瓊恩一起輪班工作。 此外，詹姆和瑟曦無法一起輪班工作。 最後，人際關係特別複雜的艾莉亞無法與詹姆、瑟曦或梅麗珊卓一起輪班工作。

增加這兩個新的約束和資源絕不會使問題無法通過命令式方式解決，但它會使解決方案變得更加困難，因為必須考慮將工人安排到特定班次的機會成本。

解決方案

然而，對於混合整數編程，它要容易得多。 我們只需要像這樣修改我們的代碼：

定義禁止列表和一些約束：

 ban_list = { ("Daenerys", "Jaime"), ("Daenerys", "Cersei"), ("Jon", "Jaime"), ("Jon", "Cersei"), ("Arya", "Jaime"), ("Arya", "Cersei"), ("Arya", "Melisandre"), ("Jaime", "Cersei") } DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

填充用於實施禁令和最大班次約束的變量：

 for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable("%s_%d" % (worker, shift), 0, 1, pl.LpInteger) # store some variable data so we can implement the ban constraint var_data = (worker,) vars_by_shift[shift].append((worker_var, var_data)) # store vars by variable so we can implement the max shift constraint vars_by_worker[worker].append(worker_var) cost.append(worker_var * info['cost'])

添加 Dothraki 變量：

 for shift in range(len(shift_requirements)): dothraki_var = pl.LpVariable('dothraki_%d' % shift, 0, DOTHRAKI_MAX, pl.LpInteger) cost.append(dothraki_var * DOTHRAKI_COST) dothrakis_by_shift[shift] = dothraki_var

我們還需要一個稍微修改的循環來計算班次和禁令要求：

 # set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum([var[0] for var in vars_by_shift[shift]]) + dothrakis_by_shift[shift] >= requirement # set the ban requirements for shift, vars in vars_by_shift.items(): for var1 in vars: for var2 in vars: worker_pair = var1[1][0], var2[1][0] if worker_pair in ban_list: prob += var1[0] + var2[0] <= 1 # set the labor standards: for worker, vars in vars_by_worker.items(): prob += sum(vars) <= 2

最後，打印結果：

 status = prob.solve() print("Result:", pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ "shift": shift, "workers": [var[1][0] for var in vars if var[0].varValue == 1], "dothrakis": dothrakis_by_shift[shift].varValue }) for result in sorted(results, key=lambda x: x['shift']): print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']), 'dothrakis hired:', int(result['dothrakis']))

我們應該很高興。 運行代碼，您應該會看到如下輸出：

 Result: Optimal Shift: 0 workers: Arya dothrakis hired: 0 Shift: 1 workers: Melisandre, Theon, Tyrion, Jaime dothrakis hired: 0 Shift: 2 workers: Bran, Jon dothrakis hired: 1 Shift: 3 workers: Bran, Daenerys, Theon, Tyrion, Arya dothrakis hired: 0 Shift: 4 workers: Melisandre, Jaime dothrakis hired: 0

我們得到了它，這是一個尊重被禁止工人名單、遵守勞動法規並明智地使用多斯拉克工人的結果。

結論

今天，我們探索了使用混合整數規劃來做出更好的決策。 我們討論了運籌學中使用的底層算法和技術，並研究了一個代表混合整數編程在現實世界中的應用的示例問題。

我希望這篇文章能啟發你更多地了解運籌學，並讓你思考如何將這項技術應用到你的項目中。 當談到令人興奮的優化算法和運籌學世界時，我們才真正看到了冰山一角。

您可以在 GitHub 上找到與本文相關的所有代碼。 如果您想討論更多，請在下面分享您的評論！