HorusLPを使用した最適化アルゴリズムの設計

公開: 2022-03-11

オペレーションズリサーチと凸最適化は応用数学の分野であり、長年にわたって幅広い商用アプリケーションが見出されています。計算能力がより手頃な価格で広く利用できるようになるにつれて、研究者はより良い決定を下すのを助けるためにますます洗練された最適化アルゴリズムを構築し始めました。今日、オペレーションズリサーチを活用したアプリケーションは、グローバルロジスティクスでのルーティングから、エネルギー業界での発電の円滑化まで、あらゆるものに電力を供給しています。

基盤となるテクノロジーが複雑になるにつれて、研究者や開発者がより生産的に作業できるように、新しいツールセットが作成されました。 AMPL、CVXPY、PuLPなどのこれらのツールを使用すると、開発者は最適化アルゴリズムをすばやく定義、構築、実行し、さまざまなソルバーとインターフェースをとることができます。

ただし、最適化テクノロジーとビジネスニーズは高度化を続けていますが、これらのツールのほとんどはほぼ同じままであり、業界のニーズを満たすのに十分な速さで進化していません。その結果、これらのアルゴリズムの開発、管理、デバッグ、および調整には、特に動きの速いビジネス環境では、多くの場合、大量の認知オーバーヘッドが必要になります。

今日は、アルゴリズム開発ワークフローのアーキテクチャーを支援するPython最適化ライブラリであるHorusLPを紹介します。ツールが解決するように設計されている問題について説明し、次にPythonライブラリの概要を簡単に説明し、最適化アルゴリズムの例をいくつか作成します。

最適化アルゴリズム開発者が直面している問題

ほとんどの開発者が直面している長年の問題の1つは、保守可能で効率的な慣用的なソフトウェアの構築と、プロジェクトの時間的制約内での製品の提供との間のバランスです。ブラウザベースのアプリケーション、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

モデルを構築するために、Problemクラスのサブクラスであるクラスを作成し、変数、目的、制約、および意味を指定します。問題を指定すると、問題を解決できます。

 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}

問題のステータス、変数の最終値、目的の値、および制約式の値が表示されます。また、変数の結果の値が辞書として表示されます。

これで、約35行で最初のHorusLP問題が発生しました。

次の例では、HorusLPライブラリのより洗練された機能について説明します。

VariableGroupsの使用

変数が関連していて、論理グループに属している場合があります。ナップサック問題の場合、すべての変数をオブジェクトグループに配置できます。変数グループを使用するようにコードをリファクタリングできます。後続のチュートリアルで参照するため、前のセクションのコードを必ず保存してください。

次のようにインポートステートメントを変更します。

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

最初の引数は変数グループの名前であり、2番目の変数はそのグループ内の変数の名前のリストです。

次に、制約と目的の定義を変更する必要があります。個々の名前を尋ねる代わりに、変数グループについて説明します。変数グループは、キーが名前で値が変数である辞書として渡されます。次のように制約と目的の定義を変更します。

 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}}

複数の制約の管理

単一の制約を持つモデルは比較的まれです。複数の制約を処理する場合は、すべての制約を1か所にまとめて、簡単に追跡および管理できるようにすることをお勧めします。 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

stdoutに新しい制約が出力され、最適な変数値が変更されていることがわかります。

依存制約と制約グループの管理

制約は、相互に依存しているため、または論理的に同じグループに属しているため、相互に関連していることがよくあります。

たとえば、一連の変数の絶対値の合計を制限する制約を設定する場合は、最初に、目的の変数間の絶対値の関係を表す制約を指定してから、絶対値の制限を指定する必要があります。変数間の特定の関係を表現するために、変数のグループに同様の制約を適用する必要がある場合があります。

これらのグループ化を表現するために、制約定義の依存制約機能を使用できます。依存制約機能の使用方法を確認するには、前の問題の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

そして、コードを再度実行すると、stdoutに次のように表示されます。

 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

大野！私たちは何をしますか？ほとんどのツールを使用している場合は、競合する可能性のある制約を1つずつ絞り込む難しいデバッグセッションに着手する必要があります。幸い、HorusLPには非互換性検索機能があり、非互換性の制約をより迅速に絞り込むことができます。非互換性検索機能を使用する最も簡単な方法は、 print_results呼び出しを次のように変更することです。

 prob.print_results(find_infeasible=True)

そのような単純な！コードを実行すると、出力として次のように表示されます。

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

すごい！これで、 MustHaveItemConstraintが実行不可能性の原因ではなく、問題がCombinedConstraints1とCombinedConstraints2に起因することが確認されました。

それは私たちにいくつかの情報を与えますが、組み合わされた制約の間に4つの依存する制約があります。 4つの制約のどれが互換性がないかを特定できますか？はい、そうです。次のように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文字列をファイルに入れましょう。もちろん、通常は外部ソースから読み取りますが、簡単にするために、すべてを1つのファイルにまとめておきましょう。コードに以下を追加します。

 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関数はすべての変数を名前で含む辞書を取得します。制約定義関数は、ディクショナリから変数にアクセスできます。

注：変数グループの場合、これはネストされたディクショナリになります。最初のレベルはグループ名で、2番目のレベルは変数名です。

残りはかなり簡単です：

 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

一番下に印刷された果物の数を見ることができます。

より複雑な問題の解決：2つのナップザック

もう少し複雑な例を見てみましょう。単一のナップザックの代わりに、バッグとスーツケースがあるとします。また、耐久性と脆弱性の2つのクラスのオブジェクトがあります。スーツケースはより保護的で、壊れやすく耐久性のある商品を収納できます。一方、バッグは耐久消費財しか収納できません。また、アイテムのデータが次の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']

次に、もう少し複雑な制約を実装する必要があります。つまり、アイテムがスーツケースとバッグの両方に入らないようにする制約です。つまり、「スーツケースの中」変数が1の場合、「バッグの中」です。変数はゼロである必要があり、その逆も同様です。もちろん、アイテムがどちらのコンテナにも入れられない場合も許可するようにします。

この制約を追加するには、すべての耐久性のあるアイテムを反復処理し、「スーツケースの中」変数と「バッグの中」変数を見つけて、これらの変数の合計が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()

これを実行すると、stdoutに次の出力が表示されます。

 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がより現実的な問題をどのように解決できるかを確認するために、もう1つの問題を一緒に検討してみましょう。前回の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

次に、変数を定義しましょう。この場合、ワーカーがシフトを実行するかどうかを決定するバイナリ変数と、シフトごとに採用するドスラキの数を決定する整数変数になります。

 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. I hope to hear from you soon!