技術

混合整数計画法：計算による意思決定のガイド

コンピュータを使用して最適な意思決定を行う科学であるオペレーションズリサーチは、ソフトウェアの多くの分野で使用および適用されてきました。いくつか例を挙げると、物流会社はこれを使用してポイントAからポイントBに到達するための最適なルートを決定し、電力会社はこれを使用して発電スケジュールを決定し、製造会社はこれを使用して工場の最適な人員配置パターンを見つけます。

混合整数計画法

今日は、仮想的な問題をウォークスルーすることにより、オペレーションズリサーチの力を探ります。具体的には、混合整数計画法（MIP）を使用して、架空の工場に最適な人員配置パターンを決定します。

オペレーションズリサーチアルゴリズム

問題の例に飛び込む前に、オペレーションズリサーチのいくつかの基本的な概念を確認し、今日使用するツールの一部を理解しておくと役に立ちます。

線形計画法アルゴリズム

線形計画法は、目的と制約が線形方程式のシステムとして表される数学モデルで最良の結果を決定するために使用されるオペレーションズリサーチ手法です。線形計画モデルの例は次のようになります。

Maximize a + b (objective) Subject to: a <= 2 (constraint 1) b <= 3 (constraint 2)

非常に単純な例では、最適な結果は5であり、a = 2およびb = 3であることがわかります。これはかなり些細な例ですが、数千の変数と数百の制約を利用する線形計画モデルを想像できます。。

良い例は、投資ポートフォリオの問題であり、疑似コードで次のような結果になる可能性があります。

Maximize Subject to: Etc. ...

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

整数計画アルゴリズム

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

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

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

オブジェクト	値（$ 10の単位）	サイズ（一般的な単位）
カメラ	5	2
不思議な置物	7	4
アップルサイダーの巨大なボトル	2	7
フレンチホルン	10	10

そして、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つのシフトがあるとします。

シフト1	シフト2	シフト3	シフト4	シフト5
1人	4人	3人	5人	2人

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

名前	可用性	シフトあたりのコスト（$）
メリザンドレ	1、2、5	20
ぬか	2. 3. 4. 5	15
サーセイ	3. 4	35
Daenerys	フォーファイブ	35
テオン	2、4、5	10
ジョン	1、3、5	25
タイリオン	2、4、5	30
ジェームズ	2、3、5	20
アリャ	1、2、4	20

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

私たちのツール

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

ラズベリーパイ3サーバープロジェクト

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

さらに、私たちの工場の外で進行中の対人対立のために、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'])

ドスラク語の変数を追加します。

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

そして、禁止された労働者のリストを尊重し、労働規制に従い、ドスラクの労働者を慎重に使用する結果が得られました。