混合整数計画法：計算上の意思決定へのガイド

オペレーションズリサーチは、コンピューターを使用して最適な意思決定を行う科学であり、ソフトウェアの多くの分野で使用および適用されています。 いくつか例を挙げると、物流会社はこれを使用して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. ...

これはかなり複雑で、手作業または試行錯誤で解決するのは困難です。 オペレーションズリサーチソフトウェアは、これらの問題を迅速に解決するためにいくつかのアルゴリズムを使用します。 基礎となるアルゴリズムに興味がある場合は、ここでシンプレックス法とここで内点法について学ぶことをお勧めします。

整数計画アルゴリズム

整数計画法は線形計画法に似ており、変数の一部またはすべてを整数値にすることができます。 これは最初は大きな改善とは思えないかもしれませんが、線形計画法だけでは解決できなかった可能性のある多くの問題を解決することができます。

そのような問題の1つは、ナップサック問題です。この問題では、値と重みが割り当てられたアイテムのセットが与えられ、ナップサックに収まるアイテムの最も高い値の組み合わせを見つけるように求められます。 アイテムをナップザックに入れることができるかどうかを表現する方法がないため、線形計画モデルではこれを解決できませんが、アイテムの一部をナップザックに入れることはできません。すべての変数は連続です。変数！

ナップサック問題の例には、次のパラメーターが含まれる場合があります。

そして、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に従業員をスケジュールすることはできません。

整数計画法を可能にするために、いくつかの数学的アルゴリズムが使用されます。 基礎となるアルゴリズムに興味がある場合は、ここで切断面アルゴリズムと分枝限定アルゴリズムを学習することをお勧めします。

問題の例：スケジューリング

問題の説明

今日は、工場の人員配置の問題を探ります。 工場の経営者としては人件費を最小限に抑えたいと考えていますが、生産需要を満たすためにシフトごとに十分なカバレッジを確保したいと考えています。

次の人員配置を必要とする5つのシフトがあるとします。

そして、次のワーカーがいるとします。

問題を単純にするために、今のところ、可用性とコストが唯一の懸念事項であると仮定しましょう。

私たちのツール

今日の問題では、CBCと呼ばれるオープンソースのブランチアンドカットソフトウェアを使用します。 Pythonの人気のあるオペレーションズリサーチモデリングライブラリであるPuLPを使用して、このソフトウェアとインターフェイスします。 あなたはそれについての情報をここで見つけることができます。

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シフトを超える労働者を割り当てることはできないと仮定します。 増加した仕事を説明するために、私たちはドスラクスタッフィンググループの助けを借りました。ドスラクスタッフィンググループは、シフトごとに40ドルの割合でシフトごとに最大10人のドスラク人労働者を供給します。

さらに、私たちの工場の外で進行中の対人対立のために、CerseiとJaimeはDaenerysまたはJonと一緒にシフトを行うことができないと仮定します。 さらに、JaimeとCerseiはシフトを一緒に行うことができません。 最後に、特に複雑な対人関係を持っているAryaは、Jaime、Cersei、またはMelisandreと同じシフトで働くことができません。

これらの2つの新しい制約とリソースを追加しても、必須の手段では問題を解決できなくなりますが、特定のシフトに労働者をスケジュールする機会費用を考慮する必要があるため、解決ははるかに困難になります。

解決

ただし、混合整数計画法を使用すると、はるかに簡単になります。 次のようにコードを修正する必要があります。

禁止リストといくつかの制約を定義します。

 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にあります。 さらに議論したい場合は、以下のコメントを共有してください！