HorusLP-Gurobi：Gurobiの高レベル最適化アーキテクチャ

公開: 2022-03-11

最適化技術がより高度になるにつれて、商用ソルバーは業界でますます重要な役割を果たし始めています。オープンソースソルバーと比較して、商用ソリューションは、高度な事前ソルバー、ウォームスタート、分散ソルバーなどの複雑な最適化モデルを解くためのより多くの機能を備えている傾向があります。

市場で最も人気のある商用ソルバーの1つは、商用ソルバー分野のパイオニアである共同創設者のZonghao Gu、Edward Rothberg、RobertBixbyにちなんで名付けられたGurobiです。 Gurobiは、FCCの帯域幅割り当てプロジェクトやペンシルベニア州刑務所の囚人再割り当てプロジェクトなど、最近の歴史の中で多くの注目を集める最適化プロジェクトに力を注いできました。

今日は、最適化モデリングのための高レベルの宣言型インターフェースを提供するソフトウェアパッケージであるHorusLPがGurobiのAPIと統合され、Gurobiの最先端機能を利用しながら直感的なモデリングエクスペリエンスをユーザーに提供する方法を見ていきます。

最適化：クイックリフレッシャー

最適化やオペレーションズリサーチに精通していない人にとって、最適化とは、連立方程式の制約を受ける連立方程式内の変数の最適値を見つける数学的手法のコレクションを指します。上記の文が少し乾燥しているように聞こえる場合は、おそらく例が説明に役立ちます。

15ポンドの環境収容力を備えたナップザックを持っていたとします。目の前にいくつかのアイテムがあり、それぞれに特定の重量と金銭的価値があります。

カメラ：重量2ポンド、値$ 5
置物：重量4ポンド、値$ 7
サイダー：重量7ポンド、値$ 2
ホーン：重量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は、商業ソルバー市場のリーダーの1つであり、政府、学術機関、金融からロジスティクスに至るまでの業界で事業を行う企業など、最適化コミュニティの大部分で使用されています。速度の点では、gurobiは、商用およびオープンソースのソルバーを判断するために使用されるいくつかのベンチマークで一貫して優れています。

Gurobiには、Pythonからモデルを構築できる強力なPythonAPIも付属しています。この機能により、モデラーはモデル構築中に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

HorusLP

HorusLPは、最適化アルゴリズムの開発経験に基づいて構築された最適化モデリングライブラリです。現在利用可能なモデリングライブラリには、オペレーションズリサーチの商用アプリケーションで通常発生する複雑で多面的な問題を処理するために必要なツールがありません。

ほとんどの最適化ライブラリは低レベルの命令型インターフェイスを提供しますが、最適化モデルがより複雑になるにつれて、複雑さを管理するためのより優れたツールが必要になります。 HorusLPは、これらの複雑さを管理するための高レベルのツールを提供するライブラリです。 HorusLPは、より迅速な開発と反復を可能にする強力なデバッグおよびレポートツールも提供します。

中核となるHorusLPは、最適化モデルに関して非常に必要とされているアーキテクチャを提供するオブジェクト指向ライブラリです。 Pythonオブジェクト指向構文を活用することにより、HorusLPライブラリは最適化モデルを最適化できる構造を提供します。その結果、分離され、モジュール化され、読みやすいコードベースが作成されます。

コードサンプルを含むコアHorusLPライブラリのより詳細な紹介が必要な場合は、ここでチュートリアルを見つけることができます。

HorusLP-Gurobi統合

HorusLPのコアAPIは、最適化モデルを構築するための便利で高レベルのAPIを提供しますが、PuLPに基づいて構築されています。これは、ソルバーとしてGurobiを利用できますが、Gurobiのより高度な機能の一部にはアクセスできません。

HorusLP-Gurobiは、GurobiのPythonAPIを使用して構築されたHorusLPAPIのバージョンです。これにより、ユーザーはHorusLP APIの一貫性を保ちながら、Gurobiの高度な機能に直接アクセスできます。

HorusLP-Gurobiの開発を導く重要な哲学の1つは、HorusLPコアAPIとの一貫性でした。 HorusLPの最小限の構造を一貫性のある状態に保つことにより、オープンソースソルバーのユーザーは、Gurobi APIをインストールし、インポートステートメントを切り替えることで、Gurobiの使用に簡単に移行できます。

単純なモデルの場合、HorusLPベースのモデルは、PythonAPIを強制的に使用するよりも多くのコード行を必要とします。ただし、開発プロセスが継続し、モデルがより複雑になるにつれて、HorusLP APIのオブジェクト指向で宣言型の設計により、デバッグと開発が容易になります。オブジェクト指向はまた、モデル定義が目的、制約、変数などを一元化して明確に描写するため、モデルをより読みやすくします。

さらに面倒なことはせずに、いくつかのコードサンプルに飛び込みましょう！

コード例

基本的なHorusLPAPI

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')

これで、constraintsクラスを使用して制約を定義できます。

 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

そして、問題をインスタンス化し、solve関数を呼び出します。ここで魔法が起こります。

 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ソルバーで、2番目の部分はHorusLPからの出力です。ご覧のとおり、アルゴリズムでは、置物とホーンを使用することを推奨しています。その結果、14ポンドのアイテムと17ドルの価値が得られます。

HorusLPをGurobiで使用する利点の1つは、「無料」で多くの情報を取得できることです。各変数の値、最終的な目標値、制約値など、開発中に通常見たいと思う多くの情報が自動的に計算され、読みやすい形式で出力されます。

HorusLPコアに関する以前の記事を読んだ場合、これはほぼ同じAPIであることに気付くでしょう。 APIをシンプルに保つために、HorusLPコアとHorsLP-Gurobiのインターフェースは同一ですが、スーパークラスの実装で抽象化されたソルバー間の違いがあります。

したがって、HorusLPの紹介はこの単純な例に任せます。 HorusLPの高度な機能を示すより複雑な例は、前の記事にあります。

グロビの特徴

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ファイルが表示されます。

このインターフェイスを使用して、IISの計算、コールバックの作成、変数ヒントの提供などの高度なGurobi機能にアクセスできます。

あなたのサービスでの高度なGurobi機能

今日は、GurobiPythonAPIの上に構築されたHorusLPライブラリのバージョンを確認しました。コアHorusLPのレポート機能とデバッグ機能に加えて、GurobiのPython APIとの統合により、シームレスにアクセスできるGurobiのすべての高度な機能にアクセスできるようになりました。

あなたが現在Gurobiユーザーであるか、Gurobi最適化の使用に興味がある人なら、HorusLPを試してみてください！ GitHubでサンプルコードを見つけたり、提案をしたり、HorusLP-Gurobiに貢献したりできます。