HorusLP-Gurobi：Gurobi 的高級優化架構

已發表: 2022-03-11

隨著優化技術變得越來越複雜，商業求解器已開始在行業中發揮越來越重要的作用。 與開源求解器相比，商業解決方案往往具有更多用於求解複雜優化模型的功能，例如高級預求解、熱啟動和分佈式求解。

市場上最受歡迎的商業求解器之一是 Gurobi，以聯合創始人顧宗浩、愛德華·羅斯伯格和羅伯特·比克斯比的名字命名，他們都是商業求解器領域的先驅。 Gurobi 在近期歷史上為許多備受矚目的優化項目提供了支持，包括 FCC 的帶寬分配項目和賓夕法尼亞州監獄的囚犯重新分配項目。

今天，我們將看看 HorusLP，一個為優化建模提供高級聲明接口的軟件包，如何與 Gurobi 的 API 集成，在利用 Gurobi 最先進的功能的同時為用戶帶來直觀的建模體驗。

優化：快速復習

對於那些不熟悉優化或運籌學的人來說，優化是指一組數學技術，可以在受約束系統約束的方程組中找到變量的最佳值。 如果上面的句子聽起來有點枯燥，也許一個例子可以幫助說明。

假設你有一個承載能力為 15 磅的背包。 您面前有幾件物品，每件都有特定的重量和貨幣價值：

  1. 相機：重量 2 磅，價值 5 美元
  2. 公仔：重 4 磅，價值 7 美元
  3. 蘋果酒：重 7 磅，價值 2 美元
  4. 號角：重 10 磅，價值 10 美元。

您想選擇放入背包的物品，以使總重量保持在 15 磅以下，但價值最大化。 （如果您需要更多關於我們為何將高價值物品放入背包的背景信息，我們鼓勵您利用您的想像力進行敘述。好的候選敘述包括從火災和房地產拍賣中搶救物品……或我們的一些邪惡活動寧可不提。）

我們可以將問題表述為以下優化問題：

 Let // Each variable stands for whether we put the item into the knapsack Camera = {0, 1} Figurine = {0, 1} Cider = {0, 1} Horn = {0, 1} // Maximize dollar value Maximize 5 * camera + 7 * figurine + 2 * cider + 10 * horn // Weight must stay below 15 pounds 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

一旦我們制定了這個問題，我們就可以應用優化技術來找到最好的物品放入我們的背包。 您可以從我之前關於使用 Python 解決優化問題和使用核心 HorusLP API 解決優化問題的文章中找到解決方案的示例。

底層的數學技術非常吸引人，但超出了本文的範圍。 如果您想了解更多信息，我建議您查看此處和此處，均由 Gurobi 提供。

古羅比

雖然最早的優化問題是由使用計算器的數學家團隊解決的，但今天大多數優化問題都是使用稱為求解器的專用軟件解決的。 雖然大多數求解器通常能夠找到大多數公式化的線性和整數規劃問題的解，但一些求解器比其他求解器更有能力。 他們可以解決其他人無法解決的問題類別，通過應用尖端數學更快地解決問題，或使用分佈式計算機解決大型困難問題。 最先進的功能通常由專門構建最快、最複雜求解器的公司開發和維護的商業求解器提供。

Gurobi 是商業求解器市場的領導者之一，被優化社區的大部分人使用，包括政府、學術機構和從金融到物流等行業的公司。 在速度方面，gurobi 在用於判斷商業和開源求解器的幾個基準測試中始終表現出色。

Gurobi 還附帶了一個強大的 Python API，允許您從 Python 構建模型。 此功能使建模者可以在模型構建期間訪問所有 Python 有用的數據操作庫，這極大地幫助了他們的過程。 作為 gurobi Python API 的演示，您可以通過以下方式對背包問題進行建模：

 import gurobipy as gr m = gr.Model() camera = m.addVar(name='camera', vtype=gr.GRB.BINARY) figurine = m.addVar(name='figurine', vtype=gr.GRB.BINARY) cider = m.addVar(name='cider', vtype=gr.GRB.BINARY) horn = m.addVar(name='horn', vtype=gr.GRB.BINARY) m.addConstr(2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 , 'size constraint') m.setObjective(5 * camera + 7 * figurine + 2 * cider + 10 * horn, gr.GRB.MAXIMIZE) m.optimize() print(camera.x) print(figurine.x) print(horn.x) print(cider.x)

運行該示例將為您提供以下輸出：

 Optimize a model with 1 rows, 4 columns and 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Coefficient statistics: Matrix range [2e+00, 1e+01] Objective range [2e+00, 1e+01] Bounds range [1e+00, 1e+00] RHS range [2e+01, 2e+01] Found heuristic solution: objective 14.0000000 Presolve time: 0.01s Presolved: 1 rows, 4 columns, 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Root relaxation: objective 1.700000e+01, 1 iterations, 0.00 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time * 0 0 0 17.0000000 17.00000 0.00% - 0s Explored 0 nodes (1 simplex iterations) in 0.01 seconds Thread count was 4 (of 4 available processors) Solution count 2: 17 14 Optimal solution found (tolerance 1.00e-04) Best objective 1.700000000000e+01, best bound 1.700000000000e+01, gap 0.0000% -0.0 1.0 1.0 -0.0

荷魯斯LP

HorusLP 是一個基於優化算法開發經驗的優化建模庫。 當前可用的建模庫缺乏處理運籌學商業應用通常遇到的複雜、多方面問題所需的工具。

雖然大多數優化庫都提供低級命令式接口，但隨著優化模型變得越來越複雜，需要更好的工具來管理複雜性。 HorusLP 是一個庫，它提供了更高級的工具來管理這些複雜性。 HorusLP 還提供了強大的調試和報告工具，可以加快開發和迭代。

HorusLP 的核心是一個面向對象的庫，它圍繞優化模型提供急需的架構。 通過利用 Python 面向對象的語法，HorusLP 庫提供了一個可以優化優化模型的結構。 結果是一個解耦、模塊化且易於閱讀的代碼庫。

如果您想通過代碼示例更詳細地介紹核心 HorusLP 庫，您可以在此處找到教程。

HorusLP-Gurobi 集成

雖然 HorusLP 的核心 API 為構建優化模型提供了方便的高級 API，但它是基於 PuLP 構建的，雖然能夠使用 Gurobi 作為求解器，但無法訪問 Gurobi 的一些更高級的功能。

HorusLP-Gurobi 是使用 Gurobi 的 Python API 構建的 HorusLP API 版本。 這允許用戶直接訪問 Gurobi 的高級功能，同時保持 HorusLP API 的一致性。

指導 HorusLP-Gurobi 開發的關鍵理念之一是與 HorusLP 核心 API 保持一致。 通過保持 HorusLP 的簡約結構一致，開源求解器的用戶可以通過安裝 Gurobi API 並切換導入語句輕鬆過渡到使用 Gurobi。

對於簡單的模型，基於 HorusLP 的模型將需要更多的代碼行，而不是簡單地使用 Python API。 然而，隨著開發過程的繼續以及模型變得越來越複雜，HorusLP API 的面向對象和聲明式設計將便於調試和開發。 面向對像也將使模型更具可讀性，因為模型定義創建集中並清楚地描述了目標、約束和變量等。

事不宜遲，讓我們深入研究一些代碼示例！

代碼示例

基本 HorusLP API

因為 HorusLP-Gurobi 保持 API 一致，所以 HorusLP 核心教程中的代碼可以通過對導入的簡單更改來移植。 但是，要使用 HoruLP-Gurobi，您需要確保已安裝 Gurobi 優化器和 Gurobi 的 Python 接口。 您可以通過在此處與他們聯繫來獲得 Gurobi。

安裝 Gurobi 後，我們可以開始使用 HorusLP-Gurobi 進行編碼！ 讓我們從安裝必要的包開始：

 Pip install horuslp horuslp-gurobi

安裝完成後，我們就可以開始使用 HorusLP-Gurobi 了！ 回想一下前面的示例背包問題。 我們可以使用 HorusLP-Gurobi 對問題進行建模，如下所示：

首先，導入相關庫。

 from horuslp_gurobi.core.Variables import BinaryVariable from horuslp_gurobi.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp_gurobi.core.constants import MAXIMIZE

定義一些變量。

 class KnapsackVariables(VariableManager): # we define variables by declaring the “vars” class variable vars = [ BinaryVariable('camera'), BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn')

現在，我們可以使用約束類定義約束。

 class SizeConstraint(Constraint): # implement the 'define' function, the variables will get passed in by name def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

然後我們可以以類似的方式實現目標。

 class ValueObjective(ObjectiveComponent): # implement the define function and return the objective expression def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn

最後，我們可以定義問題。

 class KnapsackProblem(Problem): # defining a problem using the Horus API is a matter of setting variables in the subclass variables = KnapsackVariables objective = ValueObjective # constraints is a list variable, since there can be multiple constraints,. constraints = [SizeConstraint] # make sure to set the sense! sense = MAXIMIZE

我們實例化問題並調用求解函數。 這就是魔法發生的地方。

 prob = KnapsackProblem() # instantiate prob.solve() # call the solve method prob.print_results() # optional: print the standard Horus debug report print(prob.result_variables) # optional: print the variable results as a list

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

 Optimize a model with 1 rows, 4 columns and 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Coefficient statistics: Matrix range [2e+00, 1e+01] Objective range [2e+00, 1e+01] Bounds range [1e+00, 1e+00] RHS range [2e+01, 2e+01] Found heuristic solution: objective 14.0000000 Presolve time: 0.01s Presolved: 1 rows, 4 columns, 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Root relaxation: objective 1.700000e+01, 1 iterations, 0.00 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time * 0 0 0 17.0000000 17.00000 0.00% - 0s Explored 0 nodes (1 simplex iterations) in 0.01 seconds Thread count was 4 (of 4 available processors) Solution count 2: 17 14 Optimal solution found (tolerance 1.00e-04) Best objective 1.700000000000e+01, best bound 1.700000000000e+01, gap 0.0000% 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}

第一部分是 Gurobi 求解器，第二部分是 HorusLP 的輸出。 如您所見，該算法建議我們使用小雕像和喇叭，從而產生 14 磅的物品，價值 17 美元。

將 HorusLP 與 Gurobi 結合使用的好處之一是您可以“免費”獲得大量信息。 在開發過程中通常希望查看的許多信息，例如每個變量的值、最終目標值和約束值，都會自動計算並以易於閱讀的格式輸出。

如果您閱讀過上一篇關於 HorusLP 內核的文章，您會注意到這幾乎是完全相同的 API。 為了保持 API 簡單，HorusLP core 和 HorsLP-Gurobi 的接口是相同的，只是在超類實現中抽像出求解器之間的差異。

因此，我們將把 HorusLP 的介紹留給這個簡單的例子； 可以在上一篇文章中找到演示 HorusLP 高級功能的更複雜示例。

Gurobi 功能

Gurobi 提供了許多用於解決複雜問題的高級功能。 大多數功能都可以通過 Model 對象訪問。 為了與 Gurobi API 完全兼容，模型對象可以從問題類中輕鬆訪問為model 。

例如，如果您想編寫背包模型的 MPS 文件，在 Gurobi 中您可以編寫類似m.write('knapsack.mps') 。 在使用 HorusLP-Gurobi 時，您可以簡單地：

 # import the problem as usual from horuslp_gurobi.core.Variables import BinaryVariable from horuslp_gurobi.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp_gurobi.core.constants import MAXIMIZE # define the constraint class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 # define the objectives as above class ValueObjective(ObjectiveComponent): def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn # define the variables used by the constraints and objectives class KnapsackVariables(VariableManager): vars = [ BinaryVariable('camera'), BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn') # define the problem as in the above example class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE # instantiate the problem. We don't need to call solve or print any reports. prob = KnapsackProblem() prob.model.write('knapsack.mps') # this is the only bit of new code!

您應該在工作目錄中看到 MPS 文件。

您可以使用此界面訪問高級 Gurobi 功能，例如計算 IIS、創建回調或提供變量提示。

為您服務的高級 Gurobi 功能

今天我們研究了基於 Gurobi Python API 構建的 HorusLP 庫版本。 除了核心 HorusLP 的報告和調試功能外，您現在還可以通過與 Gurobi 的 Python API 集成無縫訪問 Gurobi 的所有高級功能。

如果您是當前的 Gurobi 用戶或對使用 Gurobi 優化感興趣的人，希望您嘗試一下 HorusLP！ 您可以在 GitHub 上找到示例代碼、提出建議或為 HorusLP-Gurobi 做出貢獻。