一般化割り当て問題

応用数学において、最大一般化割り当て問題は、組合せ最適化における問題です。この問題は、タスクとエージェントの両方にサイズがある割り当て問題の一般化です。さらに、各タスクのサイズはエージェントごとに異なる場合があります。

この問題は、最も一般的な形では次のように表されます。複数のエージェントと複数のタスクがあります。任意のエージェントを任意のタスクに割り当てることができ、そのタスクの実行にかかる費用と利益は、エージェントとタスクの割り当てに応じて変動します。さらに、各エージェントには予算があり、割り当てられたタスクの費用の合計はこの予算を超えることはできません。すべてのエージェントが予算を超過せず、かつ割り当てによる総利益が最大化されるような割り当てを見つけることが求められます。

特別な場合

すべてのエージェントの予算とすべてのタスクのコストが1に等しい特殊なケースでは、この問題は割り当て問題に帰着します。すべてのタスクのコストと利益がエージェント間で変わらない場合、この問題は複数ナップサック問題に帰着します。エージェントが1人の場合、この問題はナップサック問題に帰着します。

定義の説明

以下では、から までのn種類のアイテムと、からまでのm種類のビンがあります。各ビンには予算 が関連付けられています。ビン では、各アイテムに利益と重量があります。ソリューションとは、アイテムをビンに割り当てることです。実行可能なソリューションとは、各ビンに割り当てられたアイテムの合計重量が最大 となるソリューションです。ソリューションの利益は、各アイテムとビンの割り当てにおける利益の合計です。目標は、利益が最大となる実行可能なソリューションを見つけることです。 ${\displaystyle a_{1}}$ ${\displaystyle a_{n}}$ ${\displaystyle b_{1}}$ ${\displaystyle b_{m}}$ ${\displaystyle b_{i}}$ ${\displaystyle t_{i}}$ ${\displaystyle b_{i}}$ ${\displaystyle a_{j}}$ ${\displaystyle p_{ij}}$ ${\displaystyle w_{ij}}$ ${\displaystyle b_{i}}$ ${\displaystyle t_{i}}$

数学的には、一般化割り当て問題は整数計画として定式化できます。

${\displaystyle {\begin{aligned}{\text{最大化}&\sum _{i=1}^{m}\sum _{j=1}^{n}p_{ij}x_{ij}.\\{\text{subject to }}&\sum _{j=1}^{n}w_{ij}x_{ij}\leq t_{i}&&i=1,\ldots ,m;\\&\sum _{i=1}^{m}x_{ij}\leq 1&&j=1,\ldots ,n;\\&x_{ij}\in \{0,1\}&&i=1,\ldots ,m,\quad j=1,\ldots ,n;\end{aligned}}}$

複雑

一般化割り当て問題はNP困難である。^[1]しかし、近似値を与える線形計画緩和法が存在する。^[2]${\displaystyle (1-1/e)}$

貪欲近似アルゴリズム

すべてのアイテムをビンに割り当てる必要がない問題の変種については、ナップサック問題のアルゴリズムをGAPの近似アルゴリズムに組み合わせ変換することでGAPを解決するアルゴリズムのファミリーがあります。^[3]

ナップサック問題に対する任意の -近似アルゴリズムALGを用いることで、残差利益の概念を用いた貪欲法によって一般化割り当て問題 に対する ( )-近似を構築することが可能となります。このアルゴリズムは、反復処理でスケジュールを構築し、反復処理中にビンに割り当てるアイテムが暫定的に選択されます。ビン の選択は、後の反復処理で他のビン に割り当てられるアイテムが再選択される可能性があるため、変更される可能性があります。ビン に割り当てられるアイテムの残差利益は、が他のビン に割り当てられていない場合は、 がビン に割り当てられている場合は–です。 ${\displaystyle \alpha}$ ${\displaystyle \alpha +1}$ ${\displaystyle j}$ ${\displaystyle b_{j}}$ ${\displaystyle b_{j}}$ ${\displaystyle x_{i}}$ ${\displaystyle b_{j}}$ ${\displaystyle p_{ij}}$ ${\displaystyle x_{i}}$ ${\displaystyle p_{ij}}$ ${\displaystyle p_{ik}}$ ${\displaystyle x_{i}}$ ${\displaystyle b_{k}}$

正式には、アルゴリズム実行中の暫定スケジュールを示すベクトルを使用します。具体的には、はアイテムがビンにスケジュールされていることを意味し、はアイテムがスケジュールされていないことを意味します。反復における残差利益は で表されます。ここで、アイテムがスケジュールされていない場合（つまり）、アイテムがビンにスケジュールされている場合（つまり）です。 ${\displaystyle T}$ ${\displaystyle T[i]=j}$ ${\displaystyle x_{i}}$ ${\displaystyle b_{j}}$ ${\displaystyle T[i]=-1}$ ${\displaystyle x_{i}}$ ${\displaystyle j}$ ${\displaystyle P_{j}}$ ${\displaystyle P_{j}[i]=p_{ij}}$ ${\displaystyle x_{i}}$ ${\displaystyle T[i]=-1}$ ${\displaystyle P_{j}[i]=p_{ij}-p_{ik}}$ ${\displaystyle x_{i}}$ ${\displaystyle b_{k}}$ ${\displaystyle T[i]=k}$

正式には：

セット${\displaystyle T[i]=-1{\text{ for }}i=1\ldots n}$

行う場合: ${\displaystyle j=1,\ldots,m}$

ALGを呼び出して、残差利益関数を用いてビンの解を求めます。選択された項目を で表します。${\displaystyle b_{j}}$ ${\displaystyle P_{j}}$ ${\displaystyle S_{j}}$

、つまりすべての に対してを使用して更新します。${\displaystyle T}$ ${\displaystyle S_{j}}$ ${\displaystyle T[i]=j}$ ${\displaystyle i\in S_{j}}$

参照

• 割り当て問題

参考文献

1. Özbakir, Lale; Baykasoğlu, Adil; Tapkan, Pınar (2010),一般化割り当て問題に対するBeesアルゴリズム, Applied Mathematics and Computation, vol. 215, Elsevier, pp.  3782– 3795, doi :10.1016/j.amc.2009.11.018。
2. Fleischer, Lisa; Goemans, Michel X.; Mirrokni, Vahab S.; Sviridenko, Maxim (2006).最大一般割り当て問題に対する厳密近似アルゴリズム. 第17回ACM-SIAM離散アルゴリズムシンポジウム - SODA '06の議事録. pp.  611– 620.
3. Cohen, Reuven; Katzir, Liran; Raz, Danny (2006). 「一般化割り当て問題に対する効率的な近似法」. Information Processing Letters . 100 (4): 162– 166. CiteSeerX 10.1.1.159.1947 . doi :10.1016/j.ipl.2006.06.003. 

さらに読む

• ケラー、ハンス。フェルシー、ウルリッヒ。デイビッド・パイシンガー (2013-03-19)。ナップザックの問題。スプリンガー。ISBN 978-3-540-24777-7。