使用 HorusLP 構建優化算法

已發表: 2022-03-11

運籌學和凸優化是應用數學的一個領域，多年來已經發現了廣泛的商業應用。隨著計算能力變得更加實惠和廣泛可用，研究人員開始構建越來越複雜的優化算法來幫助他們做出更好的決策。今天，由運籌學提供支持的應用程序支持從全球物流中的路線到能源行業中的電力生產平滑等方方面面。

隨著底層技術的複雜性增加，已經創建了一組新工具來幫助研究人員和開發人員更高效地工作。這些工具（例如 AMPL、CVXPY 和 PuLP）允許開發人員快速定義、構建和運行優化算法，並與各種求解器進行交互。

然而，儘管優化技術和業務需求不斷增長，但這些工具中的大多數都或多或少保持不變，並且發展得不夠快，無法滿足行業需求。因此，開發、管理、調試和調整這些算法通常需要大量的認知開銷，尤其是在快速發展的業務環境中。

今天，我想介紹一下 HorusLP，這是一個有助於算法開發工作流程架構的 Python 優化庫。我們將討論該工具旨在解決的問題，然後提供 Python 庫的快速概述，我們將構建一些示例優化算法。

優化算法開發人員面臨的問題

大多數開發人員面臨的長期問題之一是構建可維護、高效、慣用的軟件和在項目的時間限制內交付產品之間的平衡。無論您是在開發基於瀏覽器的應用程序、Web API 還是用戶身份驗證微服務，通常都需要在實現目標的“正確”方式和“快速”方式之間進行權衡。隨著產品複雜性的增加，這種固有的權衡變得更加突出。

在大多數學科中，開發人員可以通過選擇有助於架構的框架或庫來緩解這個問題。在面向 Web 的前端，很多開發者選擇 React 或 Angular；在 API 開發領域，軟件工程師可以選擇 Django、ASP.NET MVC 或 Play 等。但是，對於不起眼的優化算法開發人員來說，很少有架構工具可以幫助管理架構複雜性。開發人員可以自行管理變量、約束和各種目標。更重要的是，運籌學算法通常難以自省，加劇了問題。

HorusLP 的主要目的是為開發優化算法提供架構框架。通過提供結構一致性，該框架使組織更容易，並允許開發人員專注於他們最擅長的事情：構建算法。

典型的優化工作流程挑戰

開發 OR 算法時有幾個主要的複雜性來源：

變量的複雜性

通常必須添加變量以適應額外的業務需求，並且沒有簡單的方法來跟踪它們以用於模型定義和以後的報告。
相關變量需要分組和跟踪，並且沒有明顯的方法來管理它們。

約束的複雜性

需要添加和刪除約束以支持各種場景並執行調試，但是沒有明顯的地方可以添加或刪除約束。
約束通常是相互關聯/依賴的，並且沒有自然的方式來表達它們的關係。

目標的複雜性

如果客觀表達式有多個組件，它們可能會變得笨拙。如果對各個組件進行加權，則可能會加劇這種情況，並且需要根據業務需求調整權重。

調試的複雜性

在開發過程中沒有簡單的方法來查看模型的結果。開發人員必須顯式打印新變量和約束值才能看到結果。這會導致重複的代碼和較慢的開發。
當添加約束導致模型變得不可行時，約束導致模型變得不可行的原因可能並不明顯。通常，開發人員必須通過反複試驗來排除各種約束並尋找不兼容的地方

HorusLP 希望通過提供結構、工具和最佳實踐來提高開發人員的生產力和產品的可維護性，從而使這些挑戰更易於管理。

HorusLP 教程：優化算法和 API 概述

事不宜遲，讓我們深入了解 HorusLP 庫可以為您做什麼！

由於 HorusLP 基於 Python 和 PuLP，我們將希望使用 pip 安裝它們。在命令行中運行以下命令：

 Pip install horuslp pulp

安裝完成後，讓我們繼續打開一個 Python 文件。我們將實現我之前關於運籌學的文章中的背包問題。

HorusLP 庫有一個非常簡單的聲明式 API 和很少的樣板文件。讓我們從導入必要的類和變量開始：

 from horuslp.core.Variables import BinaryVariable # we will be using binary variables, so we will import the BinaryVariable class from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent # We will also need to import the constraint class, variable manager class, the main problem class, and the objective class to define the objective. from horuslp.core.constants import MAXIMIZE # since we're maximizing the resulting value, we want to import this constant

導入所有變量後，讓我們定義此問題所需的變量。我們通過創建一個變量管理器子類並用二進制變量填充它來做到這一點：

 class KnapsackVariables(VariableManager): vars = [ BinaryVariable('camera'), # the first argument is the name of the variable BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn') ]

現在定義了變量，讓我們定義約束。我們通過子類化主約束類並實現其“定義”功能來創建約束。

 class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

在定義函數中，您可以按名稱詢問所需的變量。框架將在變量管理器中定位變量並將其傳遞給定義函數。

約束實現後，我們就可以實現目標了。由於它是一個簡單的目標，我們將使用ObjectiveComponent ：

 class ValueObjective(ObjectiveComponent): def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn

定義函數的設置與約束類的定義函數非常相似。然而，我們不是返回一個約束表達式，而是返回一個仿射表達式。

現在已經定義了變量、約束和目標，讓我們定義模型：

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE

為了構建模型，我們創建一個作為問題類的子類的類，並指定變量、目標、約束和意義。指定問題後，我們可以解決問題：

 prob = KnapsackProblem() prob.solve()

求解後，我們可以使用問題類的print_results函數打印結果。我們還可以通過查看result_variables類來訪問特定變量的值。

 prob.print_results() print(prob.result_variables)

運行腳本，您應該會看到以下輸出：

 KnapsackProblem: Optimal camera 0.0 figurine 1.0 cider 0.0 horn 1.0 ValueObjective: 17.00 SizeConstraint: 14.00 {'camera': 0.0, 'figurine': 1.0, 'cider': 0.0, 'horn': 1.0}

您應該看到問題狀態、變量的最終值、目標值和約束表達式的值。我們還將變量的結果值視為字典。

我們有了它，我們的第一個 HorusLP 問題大約 35 行！

在接下來的示例中，我們將探索 HorusLP 庫的一些更複雜的功能。

使用變量組

有時，變量是相關的並且屬於一個邏輯組。在背包問題的情況下，所有變量都可以放入一個對象組中。我們可以重構代碼以使用變量組。確保保存上一節中的代碼，因為我們將在後續教程中引用它！

像這樣更改導入語句：

 from horuslp.core.Variables import BinaryVariableGroup from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp.core.constants import MAXIMIZE

現在我們還需要像這樣更改背包變量聲明：

 class KnapsackVariables(VariableManager): vars = [ BinaryVariableGroup('objects', [ 'camera', 'figurine', 'cider', 'horn' ]) ]

第一個參數是變量組的名稱，第二個變量是該組中變量的名稱列表。

現在我們需要更改約束和目標定義。我們不會詢問單個名稱，而是詢問變量組，它將作為字典傳入，其中鍵是名稱，值是變量。像這樣更改約束和目標定義：

 class SizeConstraint(Constraint): def define(self, objects): return 2 * objects['camera'] + 4 * objects['figurine'] + 7 * objects['cider'] + 10 * objects['horn'] <= 15 class ValueObjective(ObjectiveComponent): def define(self, objects): return 5 * objects['camera'] + 7 * objects['figurine'] + 2 * objects['cider'] + 10 * objects['horn']

現在我們可以使用相同的問題定義並運行命令：

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results() print(prob.result_variables)

您應該在輸出中看到這一點：

 KnapsackProblem: Optimal objects[camera] 0.0 objects[figurine] 1.0 objects[cider] 0.0 objects[horn] 1.0 ValueObjective: 17.00 SizeConstraint: 14.00 {'objects': {'camera': 0.0, 'figuring': 1.0, 'cider': 0.0, 'horn': 1.0}}

管理多個約束

具有單一約束的模型相對較少。處理多個約束時，最好將所有約束放在一個位置，以便輕鬆跟踪和管理它們。 HorusLP 讓這一切變得自然。

例如，假設我們想看看如果我們強制模型在我們的背包中添加一個攝像頭，結果會如何變化。我們將實施一個額外的約束並將其添加到我們的問題定義中。

回到我們在第一個教程中實現的模型。添加以下約束：

 class MustHaveItemConstraint(Constraint): def define(self, camera): return camera >= 1

要將約束添加到模型中，我們只需將其添加到問題定義中，如下所示：

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [ SizeConstraint, MustHaveItemConstraint # just add this line :) ] sense = MAXIMIZE

運行問題，您應該會看到以下輸出：

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 cider 0.0 horn 1.0 ValueObjective: 15.00 SizeConstraint: 12.00 MustHaveItemConstraint: 1.00

您應該會在標準輸出中看到打印的新約束，以及更改後的最佳變量值。

管理依賴約束和約束組

約束通常彼此相關，或者因為它們相互依賴，或者因為它們在邏輯上屬於同一組。

例如，如果要設置約束來限制一組變量的絕對值之和，則必須首先指定約束來表達預期變量之間的絕對值關係，然後再指定絕對值限制。有時，您需要對一組變量應用類似的約束，以表達變量之間的特定關係。

為了表達這些分組，我們可以使用約束定義的依賴約束特徵。要查看如何使用依賴約束功能，請重構上一個問題的SizeConstraint ，如下所示：

 class SizeConstraint(Constraint): dependent_constraints = [MustHaveItemConstraint] def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

現在為了測試依賴約束是否自動實現，讓我們將MustHaveItemConstraint排除在問題定義之外：

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [ SizeConstraint, ] sense = MAXIMIZE

再次運行代碼，您應該會在標準輸出中看到以下內容：

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 cider 0.0 horn 1.0 ValueObjective: 15.00 SizeConstraint: 12.00 MustHaveItemConstraint: 1.00

看起來MustHaveItemConstraint已實現！有關如何使用依賴約束的更複雜示例，請參閱教程末尾的人員配備示例。

管理多個加權目標

通常，在我們的優化算法的開發過程中，我們會遇到一個由多個部分組成的客觀表達式。作為我們實驗的一部分，我們可能會改變各種目標成分的權重，以使算法偏向於期望的結果。 CombinedObjective提供了一種簡潔明了的方式來表達這一點。

假設我們想讓算法偏向於選擇小雕像和蘋果酒。讓我們重構上一節中的代碼以使用CombinedObjective 。

首先，像這樣導入CombinedObjective類：

 from horuslp.core import CombinedObjective

我們可以像這樣實現一個獨立的目標組件：

 class ILoveCiderFigurineObjectiveComponent(ObjectiveComponent): def define(self, figurine, cider): return figurine + cider

現在我們可以通過實現一個CombinedObjective來組合價值目標和蘋果酒/雕像目標：

 class Combined(CombinedObjective): objectives = [ (ILoveCiderFigurineObjectiveComponent, 2), # first argument is the objective, second argument is the weight (ValueObjectiveComponent, 1) ]

現在讓我們像這樣更改問題定義：

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = Combined constraints = [SizeConstraint] sense = MAXIMIZE

運行問題，您應該會看到以下輸出：

 KnapsackProblem: Optimal camera 1.0 figurine 1.0 cider 1.0 horn 0.0 Combined: 18.00 ILoveCiderFigurineObjectiveComponent: 2.00 * 2 ValueObjectiveComponent: 14.00 * 1 SizeConstraint: 13.00 MustHaveItemConstraint: 1.00

輸出將概述組合的目標值、每個目標組件的值、權重，當然還有所有約束的值。

尋找不兼容的約束

在開發算法時，我們經常會遇到不可行的模型。如果模型很複雜，確定模型突然不可行的原因可能具有挑戰性。在這些情況下，HorusLP 有一個方便的工具可以幫助您。

假設我們正在添加約束並最終得到以下一組約束：

 class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 class SizeConstraint2(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 20 class MustHaveItemConstraint(Constraint): def define(self, cider): return cider >= 1 class IncompatibleConstraint1(Constraint): def define(self, camera): return camera >= 1 class IncompatibleConstraint2(Constraint): def define(self, camera): return camera <= 0

我們對背包中物品的總大小有幾個約束，一個要求蘋果酒必須在背包中的約束，以及一組不兼容的約束，要求相機既在背包裡又不在背包裡。（當然，在現實世界的算法中，約束通常不那麼明顯，並且涉及復雜的變量關係和約束。）

還假設約束按以下方式分組，可能會使檢測更加困難：

 class CombinedConstraints1(Constraint): dependent_constraints = [SizeConstraint2, IncompatibleConstraint1] class CombinedConstraints2(Constraint): dependent_constraints = [SizeConstraint, IncompatibleConstraint2] # MustHaveItemConstraint will be included in the problem definition independently

這是問題定義：

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [CombinedConstraints1, CombinedConstraints2, MustHaveItemConstraint] sense = MAXIMIZE

運行問題，你應該會看到以下結果：

 KnapsackProblem: Infeasible

不好了！我們做什麼？如果我們使用大多數工具，我們必須開始一個困難的調試會話，在其中我們一一縮小潛在的衝突約束。幸運的是，HorusLP 具有不兼容搜索功能，可以幫助您更快地縮小不兼容約束。使用不兼容搜索功能的最簡單方法是更改print_results調用：

 prob.print_results(find_infeasible=True)

就那麼簡單！運行代碼，現在您應該看到以下輸出：

 KnapsackProblem: Infeasible Finding incompatible constraints... Incompatible Constraints: ('CombinedConstraints1', 'CombinedConstraints2')

偉大的！現在我們已經確定MustHaveItemConstraint不是不可行的原因，問題是由於CombinedConstraints1和CombinedConstraints2造成的。

這給了我們一些信息，但是在組合約束之間有四個依賴約束。我們能否確定這四個約束中的哪一個是不相容的？嗯，是。因此修改您的print_results調用：

 prob.print_results(find_infeasible=True, deep_infeasibility_search=True)

這將使不可行搜索擴展相關約束，以便我們更詳細地了解導致不可行的原因。運行它，您應該會看到以下輸出：

 KnapsackProblem: Infeasible Finding incompatible constraints... Incompatible Constraints: ('IncompatibleConstraint1', 'IncompatibleConstraint2')

雖然每次都運行深度不可行性搜索很誘人，但對於具有大量總約束的實際問題，深度不可行性搜索可能會變得非常資源密集和耗時。因此，最好在進行一些手動調查後運行基本不可行性搜索以縮小可能性並在較小的子集上運行深度不可行性搜索。

從數據文件構建算法

在構建模型時，我們很少有機會對每個約束和變量進行硬編碼。通常，我們的程序必須足夠靈活，才能根據輸入數據更改模型。假設我們想從以下 JSON 構建我們的背包問題，而不是硬編碼輸入：

 { "items": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "figurine", "value": 7, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "horn", "value": 10, "weight": 10}, {"name": "banana", "value": 9, "weight": 2} ], "capacity": 15 }

我們可以依靠 kwargs 對我們為約束和目標實現的“定義”函數的支持來做到這一點。

讓我們從簡單的背包問題（我們在教程第 1 節中實現的問題）修改代碼。首先，讓我們將 JSON 字符串放入文件中。當然，我們通常會從外部源讀取它，但為了簡單起見，我們將所有內容保存在一個文件中。將以下內容添加到您的代碼中：

 JSON = ''' { "items": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "figurine", "value": 7, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "horn", "value": 10, "weight": 10}, {"name": "banana", "value": 9, "weight": 2} ], "capacity": 15 } '''

我們還要確保我們的程序能夠解析它。將以下內容添加到您的導入語句中：

 Import json

現在，讓我們修改我們的變量設置代碼：

 mip_cfg = json.loads(JSON) class KnapsackVariables(VariableManager): vars = [ BinaryVariable(i['name']) for i in mip_cfg['items'] ]

這將為 JSON 中的每個項目定義一個變量，並為其命名。

讓我們像這樣更改約束和目標定義：

 class CapacityConstraint(Constraint): def define(self, **kwargs): item_dict = {i['name']: i['weight'] for i in mip_cfg['items']} return sum(kwargs[name] * item_dict[name] for name in kwargs) <= mip_cfg['capacity'] class ValueObjective(ObjectiveComponent): def define(self, **kwargs): item_dict = {i['name']: i['value'] for i in mip_cfg['items']} return sum(kwargs[name] * item_dict[name] for name in kwargs)

通過請求**kwargs而不是特定的變量， define函數得到一個包含所有變量名的字典。然後約束定義函數可以訪問字典中的變量。

注意：對於變量組，它將是一個嵌套字典，其中第一級是組名，第二級是變量名。

其餘的很簡單：

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [CapacityConstraint] objective = ValueObjective sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results()

運行此程序，您應該會看到以下輸出：

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 apple 0.0 horn 1.0 banana 1.0 ValueObjective: 24.00 CapacityConstraint: 14.00

在 HorusLP 中定義自定義指標

有時，出於調試和報告的目的，我們將構建不直接在目標中表達或作為約束的自定義指標。 HorusLP 具有使指定自定義指標變得簡單的功能。

假設我們想要跟踪上一節中的模型放入背包中的水果數量。為了跟踪這一點，我們可以定義一個自定義指標。讓我們從導入 Metrics 基類開始：

 From horuslp.core import Metric

現在讓我們定義自定義指標：

 class NumFruits(Metric): name = "Number of Fruits" def define(self, apple, banana): return apple + banana

如您所見，定義的接口看起來與約束和目標組件類的接口非常相似。如果到目前為止您已經按照本教程進行操作，那麼您應該對此非常熟悉。

現在我們需要將度量添加到問題定義中。這裡的接口再次與約束定義非常相似：

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [CapacityConstraint] objective = ValueObjective metrics = [NumFruits] sense = MAXIMIZE

運行它，您應該會看到以下輸出：

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 apple 0.0 horn 1.0 banana 1.0 ValueObjective: 24.00 CapacityConstraint: 14.00 Number of Fruits: 1.00

您可以在底部看到打印的水果數量。

解決更複雜的問題：兩個背包

讓我們看一個稍微複雜一點的例子。假設我們有一個包和一個手提箱，而不是一個背包。我們還有兩類對象，耐用的和易碎的。手提箱更具保護性，可以裝易碎和耐用的物品。另一方面，袋子只能裝耐用品。還假設項目的數據在以下 JSON 中給出：

 { "fragile": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "glasses", "value": 3, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "pear", "value": 5, "weight": 3}, {"name": "banana", "value": 9, "weight": 2} ], "durable": [ {"name": "figurine", "value": 7, "weight": 4}, {"name": "horn", "value": 10, "weight": 10}, {"name": "leatherman", "value": 10, "weight": 3} ], "suitcase_capacity": 15, "bag_capacity": 20 }

讓我們看看這如何改變模型。讓我們從一張白紙開始，因為模型會完全不同。從問題的設置開始：

 import json from horuslp.core.Variables import BinaryVariableGroup from horuslp.core import Constraint, VariableManager, Problem, Metric, ObjectiveComponent from horuslp.core.constants import MAXIMIZE JSON = ''' { "fragile": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "glasses", "value": 3, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "pear", "value": 5, "weight": 3}, {"name": "banana", "value": 9, "weight": 2} ], "durable": [ {"name": "figurine", "value": 7, "weight": 4}, {"name": "horn", "value": 10, "weight": 10}, {"name": "leatherman", "value": 10, "weight": 3} ], "suitcase_capacity": 15, "bag_capacity": 20 } ''' mip_cfg = json.loads(JSON)

現在讓我們設置變量。我們將為每個可能的項目/容器組合設置一個二進制變量。

 class KnapsackVariables(VariableManager): vars = [ # suitcase can hold both fragile and durable goods BinaryVariableGroup('suitcase_f', [i['name'] for i in mip_cfg['fragile']]), BinaryVariableGroup('suitcase_d', [i['name'] for i in mip_cfg['durable']]), # bag can only hold durable goods. BinaryVariableGroup('bag_d', [i['name'] for i in mip_cfg['durable']]) ]

現在我們要為手提箱和包實現重量約束。

 class SuitcaseCapacityConstraint(Constraint): def define(self, suitcase_d, suitcase_f): fragile_weight = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) durable_weight = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return fragile_weight + durable_weight <= mip_cfg['suitcase_capacity'] class BagCapacityConstraint(Constraint): def define(self, bag_d): durable_weight = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return durable_weight <= mip_cfg['bag_capacity']

現在我們需要實現一個稍微複雜一點的約束——確保一個物品不會同時進入手提箱和包的約束——也就是說，如果“in the suitcase”變量為 1，那麼“in the bag”變量必須為零，反之亦然。當然，我們要確保允許項目最終不在兩個容器中的實例。

要添加此約束，我們需要遍歷所有耐用物品，找到“in the suitcase”變量和“in the bag”變量，並斷言這些變量的總和小於 1。

我們可以在 HorusLP 中很容易地動態定義依賴約束：

 class UniquenessConstraints(Constraint): def __init__(self): super(UniquenessConstraints, self).__init__() # call the dependent constraint builder function for every durable item, and push them into dependent constraints. dependent_constraints = [self.define_uniqueness_constraint(item) for item in mip_cfg['durable']] self.dependent_constraints = dependent_constraints def define_uniqueness_constraint(self, item): # classes are first-class objects in python, so we can define a class within this function and return it class UQConstraint(Constraint): # we name the constraint based on the item this is for, so that debugging is easier. name = "Uniqueness_%s" % item['name'] def define(self, suitcase_d, bag_d): # the define function can access the variables much in the same way as other functions return suitcase_d[item['name']] + bag_d[item['name']] <= 1 return UQConstraint

現在定義了約束，讓我們構建目標。目標很簡單，就是我們從容器中的所有項目中獲得的所有值的總和。因此：

 class TotalValueObjective(ObjectiveComponent): def define(self, suitcase_f, suitcase_d, bag_d): fragile_value = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) durable_value_s = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) durable_value_d = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return fragile_value + durable_value_s + durable_value_d

讓我們還定義一些自定義指標，以便我們可以一目了然地看到袋子和手提箱中放入了多少重量，以及手提箱重量中有多少來自耐用品和易碎品：

 class SuitcaseFragileWeightMetric(Metric): def define(self, suitcase_f): return sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) class SuitcaseDurableWeightMetric(Metric): def define(self, suitcase_d): return sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) class BagWeightMetric(Metric): def define(self, bag_d): return sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']])

現在我們已經完成了所有部分，讓我們實例化問題並運行模型：

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [SuitcaseCapacityConstraint, BagCapacityConstraint, UniquenessConstraints] objective = TotalValueObjective metrics = [SuitcaseDurableValueMetric, SuitcaseFragileValueMetric, BagValueMetric] sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results()

運行它，您應該在標準輸出中看到以下輸出：

 KnapsackProblem: Optimal suitcase_f[camera] 1.0 suitcase_f[glasses] 1.0 suitcase_f[apple] 1.0 suitcase_f[pear] 0.0 suitcase_f[banana] 1.0 suitcase_d[figurine] 0.0 suitcase_d[horn] 0.0 suitcase_d[leatherman] 0.0 bag_d[figurine] 1.0 bag_d[horn] 1.0 bag_d[leatherman] 1.0 TotalValueObjective: 32.00 SuitcaseCapacityConstraint: 15.00 BagCapacityConstraint: 17.00 Uniqueness_figurine: 1.00 Uniqueness_horn: 1.00 Uniqueness_leatherman: 1.00 SuitcaseDurableWeightMetric: 0.00 SuitcaseFragileWeightMetric: 15.00 BagWeightMetric: 17.00

所以相機、眼鏡、蘋果和香蕉放入手提箱的重量為 15 個單位，小雕像、喇叭和皮革人都放入包中，總共有 17 個重量單位。貨物的總價值為 32 個價值單位。有趣的是，行李箱中沒有一件耐用品，很可能是因為袋子有足夠的容量容納所有耐用品。

一個更大更現實的場景：人員配備問題

如果您在我們的 HorusLP 教程中做到了這一點，那麼恭喜！您現在對如何使用 HorusLP 有了很好的了解。

然而，到目前為止，我們一直在研究的所有示例都是背包問題的排列，並且一些要求和參數有點不切實際。讓我們一起解決一個問題，看看 HorusLP 如何解決更現實的問題。我們將解決我之前的 Toptal 文章後半部分中概述的人員配備問題。

出於時間考慮，我們將直接進入模型的最終版本（包括個人衝突、勞動法規和臨時工津貼），但最初更簡單模型的實現也可以在 GitHub 上找到。

因此，讓我們從設置問題開始：

 from horuslp.core.Variables import BinaryVariableGroup, IntegerVariableGroup from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent, CombinedObjective from horuslp.core.constants import MINIMIZE shift_requirements = [1, 4, 3, 5, 2] # the number of workers we need to staff for each shift # the availability and pay rates of each of the employees 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 } } # the following people can't work together, sadly. ban_list = { ("Daenerys", "Jaime"), ("Daenerys", "Cersei"), ("Jon", "Jaime"), ("Jon", "Cersei"), ("Arya", "Jaime"), ("Arya", "Cersei"), ("Arya", "Melisandre"), ("Jaime", "Cersei") } # Dothraki Staffing Corp will provide us with expensive temp workers DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

現在讓我們定義變量，在這種情況下，這些變量是確定工人是否應該輪班工作的二進制變量，以及確定每個輪班僱用多少 dothrakis 的整數變量：

 class StaffingVariables(VariableManager): vars = [] def __init__(self): # like dependent constraints, we can dynamically define variables in the init function super(StaffingVariables, self).__init__() # regular workers varkeys = [] for employee, availability_info in workers.items(): for shift in availability_info['availability']: varkeys.append((employee, shift)) self.vars.append(BinaryVariableGroup('employee_shifts', varkeys)) # dothrakis dothraki_keys = [i for i in range(len(shift_requirements))] self.vars.append(IntegerVariableGroup('dothraki_workers', dothraki_keys, 0, DOTHRAKI_COST))

現在讓我們實施要求我們為每個班次配備足夠人員的約束：

 class SufficientStaffingConstraint(Constraint): # we need to staff people sufficiently dependent_constraints = [] def __init__(self): super(SufficientStaffingConstraint, self).__init__() for shift_num, shift_req in enumerate(shift_requirements): self.dependent_constraints.append(self.build_shift_constraint(shift_num, shift_req)) def build_shift_constraint(self, sn, sr): class ShiftConstraint(Constraint): name = "shift_requirement_%d" % sn def define(self, employee_shifts, dothraki_workers): variables = [val for key, val in employee_shifts.items() if key[1] == sn] variables.append(dothraki_workers[sn]) return sum(variables) >= sr return ShiftConstraint

現在，我們需要實施阻止特定人員相互合作的約束：

 class PersonalConflictsConstraint(Constraint): # some people can't work together dependent_constraints = [] def __init__(self): super(PersonalConflictsConstraint, self).__init__() for person_1, person_2 in ban_list: for shift in range(len(shift_requirements)): self.dependent_constraints.append(self.build_conflict_constraint(person_1, person_2, shift)) def build_conflict_constraint(self, p1, p2, s): class ConflictConstraint(Constraint): name = "Conflict_%s_%s_%d" % (p1, p2, s) def define(self, employee_shifts): if (p1, s) in employee_shifts and (p2, s) in employee_shifts: return employee_shifts[p1, s] + employee_shifts[p2, s] <= 1 return True # returning true will make the constraint do nothing return ConflictConstraint

And finally the labor standards constraint. We'll implement this one slightly differently for demonstrative purposes:

 class LaborStandardsConstraint(Constraint): # we can make someone work more than two shifts a day. dependent_constraints = [] def __init__(self): super(LaborStandardsConstraint, self).__init__() for worker in workers.keys(): # we don't need a constraint builder function, but in those circumstances # we need to set the needed values as class variables and refer to them # via the self keyword due to how python's closure system works class LaborConstraint(Constraint): # we can't use worker directly! wk = worker name = "labor_standard_%s" % worker def define(self, employee_shifts): # we need to access the worker using self. Change self.wk to worker to see # why we need to do this worker_vars = [var for key, var in employee_shifts.items() if key[0] == self.wk] return sum(worker_vars) <= 2 self.dependent_constraints.append(LaborConstraint)

And now let's set up the objectives. The dothraki cost and regular employee costs are calculated very differently, so we'll put them in separate objective components:

 class CostObjective(ObjectiveComponent): # this is the cost function for all the named workers def define(self, employee_shifts, dothraki_workers): costs = [ workers[key[0]]['cost'] * var for key, var in employee_shifts.items() ] return sum(costs) class DothrakiCostObjective(ObjectiveComponent): # don't forget the Dothrakis def define(self, dothraki_workers): dothraki_costs = [ dothraki_workers[sn] * DOTHRAKI_COST for sn in dothraki_workers ] return sum(dothraki_costs) class TotalCostObjective(CombinedObjective): objectives = [ (CostObjective, 1), (DothrakiCostObjective, 1) ]

And now we can define and run the problem:

 class StaffingProblem(Problem): variables = StaffingVariables objective = TotalCostObjective constraints = [SufficientStaffingConstraint, PersonalConflictsConstraint, LaborStandardsConstraint] sense = MINIMIZE # we're minimizing this time, not maximizing. if __name__ == '__main__': prob = StaffingProblem() prob.solve() prob.print_results()

Run the script and you should see the following:

 StaffingProblem: Optimal employee_shifts[('Melisandre', 0)] 0.0 employee_shifts[('Melisandre', 1)] 1.0 employee_shifts[('Melisandre', 4)] 1.0 employee_shifts[('Bran', 1)] 0.0 employee_shifts[('Bran', 2)] 1.0 employee_shifts[('Bran', 3)] 1.0 employee_shifts[('Bran', 4)] 0.0 employee_shifts[('Cersei', 2)] 0.0 employee_shifts[('Cersei', 3)] 0.0 employee_shifts[('Daenerys', 3)] 1.0 employee_shifts[('Daenerys', 4)] 0.0 employee_shifts[('Theon', 1)] 1.0 employee_shifts[('Theon', 3)] 1.0 employee_shifts[('Theon', 4)] 0.0 employee_shifts[('Jon', 0)] 0.0 employee_shifts[('Jon', 2)] 1.0 employee_shifts[('Jon', 4)] 0.0 employee_shifts[('Tyrion', 1)] 1.0 employee_shifts[('Tyrion', 3)] 1.0 employee_shifts[('Tyrion', 4)] 0.0 employee_shifts[('Jaime', 1)] 1.0 employee_shifts[('Jaime', 2)] 0.0 employee_shifts[('Jaime', 4)] 1.0 employee_shifts[('Arya', 0)] 1.0 employee_shifts[('Arya', 1)] 0.0 employee_shifts[('Arya', 3)] 1.0 dothraki_workers[0] 0.0 dothraki_workers[1] 0.0 dothraki_workers[2] 1.0 dothraki_workers[3] 0.0 dothraki_workers[4] 0.0 TotalCostObjective: 335.00 CostObjective: 290.00 * 1 DothrakiCostObjective: 45.00 * 1 shift_requirement_0: 1.00 shift_requirement_1: 4.00 shift_requirement_2: 3.00 shift_requirement_3: 5.00 shift_requirement_4: 2.00 Conflict_Jon_Cersei_2: 1.00 Conflict_Jon_Jaime_2: 1.00 Conflict_Jon_Jaime_4: 1.00 Conflict_Daenerys_Cersei_3: 1.00 Conflict_Daenerys_Jaime_4: 1.00 Conflict_Arya_Jaime_1: 1.00 Conflict_Arya_Cersei_3: 1.00 Conflict_Arya_Melisandre_0: 1.00 Conflict_Arya_Melisandre_1: 1.00 Conflict_Jaime_Cersei_2: 0.00 labor_standard_Melisandre: 2.00 labor_standard_Bran: 2.00 labor_standard_Cersei: 0.00 labor_standard_Daenerys: 1.00 labor_standard_Theon: 2.00 labor_standard_Jon: 1.00 labor_standard_Tyrion: 2.00 labor_standard_Jaime: 2.00 labor_standard_Arya: 2.00

If you compare this with the problem we implemented in the previous tutorial, you should see that the results match.

包起來

Congratulations for making it through our first HorusLP tutorial! You're now a competent practitioner of HorusLP.

I hope that this article convinced you of the benefits of architecting your MIP models, and that you will make use of HorusLP in your coming projects. You can find the HorusLP source code, as well as the code for all the tutorials, on GitHub. Additional HorusLP documentation and a tutorial page will be added to GitHub very soon.

As HorusLP is a fairly new project, we would love to hear from you and incorporate your input. If you have any questions, comments, or suggestions, please drop me a line either through Toptal or using the contact information you can find on GitHub. 我希望很快能收到您的回應！